Autonomiczne najnowszy zestaw łamigłówek przedstawiała skromną wagę z dwoma szalkami, historycznie symbol handlu i rządu, sztuki i nauki. Wagi wagowe są również popularne w matematyce rekreacyjnej. Zagadki równowagi wymagają jasnego, logicznego rozumowania i dobrze nadają się do matematycznego uogólnienia. Zobaczmy jak Quanta czytelnicy zrównoważyli te cechy w poniższych zagadkach.
Łamigłówka 1
Masz osiem identycznie wyglądających monet. Jeden jest podrobiony i lżejszy od pozostałych, które mają identyczną wagę. Znajdź złą monetę w dwóch wagach. Znajdź ogólny wzór na maksymalną liczbę monet, dla których możesz znaleźć fałszywą w x ważenia.
Rozwiązanie prostej wersji problemu często ujawnia klucz do rozwiązania. W tym przypadku wyobraź sobie, że masz tylko trzy monety, z których jedna jest lżejsza od pozostałych. Jeśli zważysz którykolwiek z nich z drugim, albo się zrównoważą, albo nie. Jeśli nie, wiesz, który jest lżejszy. Jeśli zachowują równowagę, to trzecia jest lekka. Potrzebujesz tylko jednego ważenia.
Tak więc w tej zagadce, jeśli potrafisz wyizolować grupę trzech (lub mniej) monet zawierających jasną monetę w pierwszym ważeniu, będziesz potrzebować jeszcze jednego ważenia. Możesz to zrobić, równoważąc dowolne trzy z dowolnymi innymi trzema. Jeśli dwie grupy są niezrównoważone, znalazłeś grupę zawierającą jasną i możesz postępować jak wyżej przy drugim ważeniu. Jeśli się zrównoważą, po prostu zważ ze sobą pozostałe dwie monety, a znajdziesz tę jasną.
Zauważ, że działa to również, jeśli w grupie nieważonej są trzy, więc mogliśmy zacząć od dziewięciu monet. Zgodnie z tą logiką i zaczynając od trzech monet, za każde dodatkowe ważenie możemy znaleźć jasną monetę w liczbie trzykrotnej liczby monet, które mieliśmy poprzednio. Wzór dający nam maksymalną liczbę monet n in w ważenie jest zatem n = 3w.
Łamigłówka 2
Masz 12 identycznie wyglądających monet. Jeden jest albo cięższy, albo lżejszy od pozostałych, które mają identyczną wagę.
-
Znajdź złą monetę w trzech ważeniach.
-
Jaka jest maksymalna liczba monet, dla których można znaleźć złą w czterech ważeniu? Opisz, jak znalazłbyś fałszywą monetę.
Rozwiązanie tej zagadki zostało dobrze opisane przez Ted, który również wykazał, że złą monetę można wykryć wśród 13 monet w trzech ważeniach. Oto rozwiązanie Teda (z wcięciami do oddzielenia trzech ważeń w każdym przypadku):
Zacznij od zważenia 4 monet kontra 4 monety.
Przypadek 1: W przypadku niezrównoważenia, do drugiego ważenia połóż po 2 z cięższej strony po obu stronach wagi oraz po 1 z lżejszej strony.
1a: W przypadku braku równowagi, złą monetą są albo 2 monety nadal po ciężkiej stronie, albo pojedyncza moneta nadal po jasnej stronie.
Zważ 2 możliwe ciężkie monety, zła jest albo cięższa z dwóch, albo pojedyncza lekka, jeśli są zrównoważone.
1b: Jeśli drugie ważenie jest zrównoważone, zła moneta jest jedną z 2 niewykorzystanych z jaśniejszej strony pierwszego ważenia.
Zważ je ze sobą, lżejszy jest zły.
Przypadek 2: Jeśli zbilansowana, zła moneta jest jedną z 5 pozostałych. Odważ 3 z tych 3 z dowolnymi XNUMX już zważonymi (o których wiadomo, że są dobre).
Przypadek 2a: Jeśli jest niezrównoważony, wiesz, że zła moneta jest jedną z tych 3 i czy jest lekka, czy ciężka.
Trzecie ważenie to dowolne 2 z nich w stosunku do siebie — jeśli niesymetryczne, to identyfikuje złą monetę, jeśli zbalansowane jest to ostatnia z trzech.
Przypadek 2b: Jeśli drugie ważenie jest zrównoważone, zła moneta jest jedną z pozostałych 2.
Porównaj jeden z nich ze znaną dobrą monetą. Jeśli ten wynik jest niezrównoważony, ta nowa moneta jest zła i wiesz, czy jest ciężka, czy lekka. Jeśli ten wynik jest zrównoważony, 13. moneta jest zła, ale nie wiadomo, czy jest ciężka, czy lekka (o czym nie musimy wiedzieć, więc skończyliśmy).
Ted wykazał również, że maksymalna liczba monet na cztery ważenia wynosi 40. Wzór na tę układankę to: n = (3w − 1)/2.
W przypadku pozostałych zagadek uogólnione formuły są nadal badane przez zawodowych matematyków i są przedmiotem publikowanych artykułów, z których część była cytowana przez Rainer z wiosny. Ograniczę się do rozwiązań dotyczących małej liczby monet, które rozważamy w łamigłówkach, i wspomnę tylko o uogólnieniach, które wynikają naturalnie z metod stosowanych w tych przypadkach.
Łamigłówka 3
To jest odmiana łamigłówki 1. Znowu masz osiem identycznie wyglądających monet, z których jedna jest lżejsza od pozostałych. Jednak teraz masz trzy skale. Dwie ze skal działają, ale trzecia jest zepsuta i daje losowe wyniki (czasem jest słuszna, a czasami nie). Nie wiesz, która skala jest zepsuta. Ile ważeń zajmie znalezienie lekkiej monety?
Jak widzieliśmy w zadaniu 1, wymaga to tylko dwóch ważenia z dobrą wagą. Wiemy również, że dwie dobre wagi zawsze będą się zgadzać, więc jeśli po prostu powtórzymy każde ważenie na wszystkich trzech wagach, otrzymamy odpowiedź w sześciu ważeniach, jak zasugerował czytelnik. Jeśli spróbujemy to zrobić w mniejszej liczbie ważeń, będzie to trochę trudne. Nie możemy zidentyfikować dobrej wagi tylko poprzez ważenie tych samych monet na dwóch wagach, ponieważ nawet jeśli się zgadzają, którakolwiek z nich może nadal być złą wagą. (Pokazuje to również, jak łatwo dezinformacja lub przypadkowe informacje mogą zaciemnić prawdę.)
W rzeczywistości ten problem można rozwiązać, bardzo sprytnie, w zaledwie czterech ważeniach! Rainer z wiosny opublikował rozwiązanie za pomocą nowomodnej notacji, która wydaje się być stworzona dla tej zagadki. Ale zanim tam pójdziesz, wyobraź sobie scenariusz, który, mam nadzieję, sprawi, że wszystko będzie bardziej intuicyjne.
Wyobraź sobie, że jesteś detektywem prowadzącym śledztwo w sprawie potrącenia i ucieczki w maleńkim kraju, którego samochody mają dwucyfrowe tablice rejestracyjne zawierające tylko cyfry 0, 1 i 2. Incydent obserwowały trzy osoby, A, B i C. Dwóch z nich zawsze poprawnie odpowiada na trzy pytania do wyboru, a jeden daje zupełnie losowe odpowiedzi. Nie wiesz, kto jest odpowiedzią losową. Musisz zadać każdemu z nich jedno pytanie z trzech wyborów, a następnie wybrać to, które zdecydowanie mówi prawdę, aby uzyskać więcej informacji.
Oto jak to robisz. Zapytaj A, czy pierwsza cyfra to 0, 1 lub 2. Powiedzmy, że A mówi 2. Zapytaj B, czy druga cyfra to 0, 1 lub 2. Powiedzmy, że B to 1. Następnie poproś C, aby wybrał między tymi trzema stwierdzeniami:
- Tylko A mówi prawdę.
- Tylko B mówi prawdę.
- Obaj mówią prawdę.
Możesz uwierzyć w to, do którego mówi C, i zapytać tę osobę o drugą cyfrę. Aby zobaczyć dlaczego, rozważ, że jeśli A kłamie, to C jest wiarygodny i powie, że B mówi prawdę. Druga cyfra będzie w rzeczywistości równa 1, a następnie możesz zapytać B o pierwszą cyfrę. Podobnie, jeśli B kłamie, to C znów jest wiarygodne i powie, że A mówi prawdę. Wtedy pierwsza cyfra to tak naprawdę 2 i możesz zapytać A o drugą cyfrę. Wreszcie, jeśli C kłamie, to zarówno A, jak i B są wiarygodne, więc nadal możesz wierzyć i wybierać kogo C mówi. (A jeśli C mówi, że zarówno A, jak i B mówią prawdę, to oboje muszą być.) Kluczem jest tutaj to, że twój wybór pytań nie pozwala C kłamać w taki sposób, aby poddawać w wątpliwość zarówno A, jak i B. Ponieważ przynajmniej jedno z A i B musi być wiarygodne, zawsze możesz wybrać tę, z którą C się zgadza, nawet jeśli jest to tylko losowa odpowiedź. Jeśli wszystkie trzy się zgadzają, to masz już obie cyfry tablicy rejestracyjnej.
Oto jak przełożyć tę opowieść z powrotem na naszą układankę. Skale to A, B i C. Dwie cyfry z tablicy rejestracyjnej można przełożyć na monety w następujący sposób: 01 to moneta 1, 02 to moneta 2, 10 to moneta 3, 11 to moneta 4, 12 to moneta 5, 20 to moneta 6, 21 to moneta 7, a 22 to moneta 8. Wnikliwi czytelnicy rozpoznają, że jest to system liczbowy o podstawie 3 (lub trójskładnikowy). Zwróć też uwagę, że istnieje dodatkowa możliwa liczba 00, której możesz użyć do dziewiątej monety, dla której ta technika również zadziała, jak w układance 1.
Przy pierwszym ważeniu dzielisz monety przez ich pierwszą (podstawową 3) cyfrę, więc Twoje trzy grupy będą monetami [1, 2], [3, 4, 5] i [6, 7, 8]. Zważ [3, 4, 5] z [6, 7, 8] na wadze A. Jeśli A działa dobrze, będziesz miał prawidłową pierwszą grupę cyfr jak w zagadce 1. Podobnie, dla drugiego ważenia na wadze B twoje grupy będą te z tą samą drugą cyfrą: [1, 4, 7], [2, 5, 8] i [3]. Jeśli B działa dobrze, będziesz mieć poprawną drugą cyfrę. Przy trzecim ważeniu, na skali C, ważysz grupę zidentyfikowaną przez A z grupą, którą zrobił B. Zgodnie z naszym przykładem, dla 6, grupy będą [21, 6, 7] i [8, 1, 4]. Monety 7 nie można położyć po obu stronach jednocześnie, więc pomijamy ją i ważymy [7, 6] i [8, 1] ze sobą. Zauważ, że jeśli A i B są wiarygodne, to 4 jest w rzeczywistości poprawną odpowiedzią i nie ma znaczenia, która strona wyjdzie lżej na C. Jeśli przypadkiem ważenie na C jest zrównoważone, wszystkie trzy wagi są zgodne i masz odpowiedź (moneta 7) w zaledwie trzech ważeń. Jeśli A jest wiarygodne, a B nie, lżejsza moneta znajduje się w [7, 6], co potwierdzi skala C, a jeśli B jest wiarygodne, a A nie, to lżejsza moneta znajduje się w [8, 1], w której skali C również potwierdzi.
Tak więc w trzech ważeniach albo zidentyfikowaliśmy jasną monetę, albo zawęziliśmy ją do grupy dwóch, a także zidentyfikowaliśmy wagę roboczą. Czwarte ważenie na wadze A lub na wadze B (w zależności od uzgodnionej wagi C) zajmie się resztą.
To rozwiązanie wydaje mi się niesamowicie piękne!
Tę metodę można uogólnić, aby znaleźć lekką monetę wśród 32x monety w 3x + 1 ważenia z danym zestawem wag. Tak więc potrzebujesz siedmiu ważeń na 81 monet. W przypadku większej liczby monet (>~1,000), jeszcze mocniejsze rozwiązanie istnieje.
Łamigłówka 4
Masz 16 monet, z których osiem jest ciężkich i tej samej wagi. Pozostałe osiem są lekkie i tej samej wagi. Nie wiesz, które monety są ciężkie czy lekkie. Monety wyglądają identycznie, z wyjątkiem jednej, która ma specjalne oznaczenia. Czy za pomocą jednej dobrej wagi możesz dowiedzieć się, czy specjalna moneta jest lekka, czy ciężka w trzech wagach? Od jakiej maksymalnej liczby monet możesz zacząć i skutecznie rozwiązać ten problem w czterech ważeniach?
Na pierwszy rzut oka ta zagadka wydaje się prawie niemożliwa do wykonania w trzech ważeniach, jak podsumował jeden z naszych czytelników. Niemniej jednak przy odrobinie sprytu da się to zrobić i jedno i drugie Ted i Rainer z wiosny podał prawidłowe rozwiązania. Ted podał kilka bezcennych ogólnych zasad, na które warto zwrócić uwagę.
Po pierwsze, dopóki nie uzyskasz niezrównoważonego wyniku ważenia, nie będziesz mieć wystarczających informacji, aby określić, czy specjalna moneta jest ciężka, czy lekka. Musisz więc spróbować wymusić niezrównoważony wynik.
Po drugie, jeśli uzyskasz zrównoważony wynik (powiedzmy, że specjalna moneta A równoważy monetę B), możesz połączyć zbilansowane monety i zważyć je z dwoma kolejnymi monetami, C i D. Jeśli są niezrównoważone, masz odpowiedź; w przeciwnym razie podwoiłeś teraz liczbę podobnych monet, co może pomóc w uzyskaniu niezrównoważonej odpowiedzi podczas następnego ważenia. Możesz również przeprowadzić ten proces w odwrotnej kolejności z liczbami monet, które są potęgami dwójki (4, 8 itd.), jeśli masz początkowy niezrównoważony wynik, jak widać w poniższym rozwiązaniu.
Poniżej znajduje się cała procedura, która może zidentyfikować rodzaj monety specjalnej A we wszystkich przypadkach w trzech ważeniach. (B, C i D to trzy monety umieszczone po tej samej stronie co A o wadze 1 (W1); X i Y to dwie monety nieużywane w W1.)
Ta zagadka została wymyślona przez rosyjskiego matematyka Konstanty Knop, światowy autorytet w łamigłówkach na monety. Wiele jego prac jest po rosyjsku, ale na blog jego współpracownika Tanya Khovanova.
Co do uogólnienia, zostawię tobie, aby sprawdzić, czy ta sama metoda działa w celu znalezienia typu specjalnej monety wśród 32 monet, z których 16 jest ciężkich, a 16 lekkich.
Łamigłówka 5
Ty masz n identycznie wyglądające monety, z których niektóre są fałszywe i lżejsze niż inne. Wiesz tylko, że istnieje co najmniej jedna fałszywa moneta i że normalnych monet jest więcej niż fałszywych. Twoim zadaniem jest wykrycie wszystkich fałszywych monet.
Fakt, że istnieje co najmniej jedna jasna moneta i że zwykłych monet jest więcej niż jasnych, sprawia, że ta zagadka jest mniej skomplikowana, niż się wydaje, przynajmniej dla małych liczb. Przyjrzyjmy się liczbom ważeń dla jednej do ośmiu monet.
W przypadku jednej i dwóch monet w drugim warunku nie mogą być monety lekkie, więc nie jest wymagane ważenie.
Trzy monety: Tylko jedna jasna moneta. Wymagane jest jedno ważenie na układankę 1.
Cztery monety: Tylko jedna jasna moneta. Wymagane jest jedno dodatkowe ważenie, więc w = 2.
Pięć monet: od jednej do dwóch lekkich monet. To pierwszy interesujący przypadek. Pytanie brzmi: czy powinniśmy ważyć jedną monetę przeciwko jednej, czy dwie monety przeciwko dwóm?
Jeśli zważymy jeden przeciwko jednemu, możemy mieć:
- Dwa niezrównoważone ważenia: Odkryto dwie monety; skończyliśmy.
- Jedno zbilansowane ważenie z dwóch: Zbilansowane monety muszą być normalne, więc ostatnia moneta wymaga kolejnego ważenia, w = 3.
- Dwa ważenia wyważone: W trzecim ważeniu zważ jedną monetę z każdego poprzedniego ważenia względem drugiej. Jeśli są zrównoważone, wszystkie cztery są normalne, a moneta 5 jest lekka. Skończyliśmy; w = ponownie 3. Jeśli są niezrównoważone, znaleźliśmy dwie lekkie monety i kończymy trzy ważenia.
Jeśli zamiast tego ważymy dwa przeciw dwóm, nadal potrzebujemy trzech ważeń, ponieważ musimy rozróżnić możliwości, że monety mogą być różne lub podobne po obu stronach. Wydaje się, że ważenie z użyciem niewielkiej liczby monet zgrupowanych razem nie ma żadnej przewagi nad ważeniami z użyciem pojedynczych monet.
Uznaje się to za:
Sześć monet: od jednej do dwóch lekkich monet; w = 4.
Siedem monet: od jednej do trzech lekkich monet; w = 5.
Osiem monet: od jednej do trzech lekkich monet; w = 6. To rozwiązanie ma prostą strukturę:
- Najpierw wykonaj cztery ważenia jednej monety przeciwko drugiej. Wszystkie monety są używane.
- W najgorszym przypadku: wszystkie cztery ważenia są zrównoważone (są dwie lekkie monety, które się równoważą).
- Kolejne dwa ważenia: zważ monetę z ważenia 1 z monetą z ważenia 2; podobnie zważ monetę o wadze 3 z monetą o wadze 4.
- Jedna z tych ważeń będzie niezrównoważona, co spowoduje zidentyfikowanie dwóch jasnych monet. Robimy sześć ważeń.
Przepraszamy, nasza sekwencja 0, 0, 1, 2, 3, 4, 5, 6 z pewnością nie jest wystarczająco interesująca, aby poddać się On-line encyklopedia ciągów liczb całkowitych!
As Jonasa Tøgersena Kjellstadli wskazał, rozwiązaniem wydaje się być w = n − 2 dla małych liczb, ale nie udowodniliśmy, że nie zmieni się to dla większych liczb. Na niektóre n, użycie wielu ważeń monet może zacząć działać lepiej lub więcej ważeń niż n − 2 może być wymagane. Możemy po prostu uogólnić rozwiązanie dla ośmiu monet na wszystkie potęgi 2, dając n − 2 jako górna granica liczby ważeń dla wszystkich potęg 2.
Mark Pearson omówił podobieństwo tego problemu do kodów korygujących błędy i zasugerował zastosowanie podejścia opartego na teorii informacji w oparciu o liczbę możliwych wyników. Stosując takie podejście, Mike Roberts opublikował dolną granicę dla bardziej ogólnego przypadku, który Rainer z wiosny wyprowadził przybliżenie dla. Rainer również opublikował an Górna granica z opublikowanego artykułu, ale zauważył, że granice nie są ostre dla niskich n i dlatego nie jest pomocny w przypadku małych liczb, które rozważaliśmy powyżej. Tak więc dla siedmiu monet przytoczone granice dają zakres od 4 do 16, pomiędzy którymi mieści się nasza odpowiedź, 5. J. Payette daje dodatkowe odniesienia matematyczne i granice dla wszystkich łamigłówek.
Dziękujemy wszystkim, którzy uczestniczyli. Nagroda Insights za ten miesiąc trafia wspólnie do Teda i Rainera aus dem Spring. Gratulacje!
Do zobaczenia następnym razem na nowe Insights.
