Zgadnij, co robię • Konstantin Knoop • Popularne zadania naukowe na temat "Elementów" • Matematyka

Zgadnij, co robię

Zadanie

Kostia wymyślił liczbę naturalną K od 1 do 2013 r. i jest gotowy odpowiedzieć "tak" lub "nie" na pytania, które pozwalają na takie odpowiedzi. Ma jednak prawo udzielić błędnej odpowiedzi nie więcej niż jeden raz (dla wszystkich odpowiedzi).

Sasha chce zadać Kostii nie więcej niż 15 pytań, zgodnie z odpowiedziami, na które zawsze może odgadnąć zamierzoną liczbę. Pomoc żeby to zrobił.


Wskazówka 1

Zwykle w takich zadaniach starają się zadawać "pytania-porównania", to znaczy "Czy to prawda, że ​​twój numer jest mniejszy niż ten" (lub "więcej niż to"). Jednak Sasha absolutnie nie musi ograniczać się do takich właśnie pytań. Bardziej ogólny rodzaj pytań jest następujący: Sasha zapisuje każdy zestaw liczb (który zawiera niektóre liczby od 1 do 2013) i pyta Kostię: "Czy to prawda, że ​​zaplanowałeś jedną z tych liczb?".


Wskazówka 2

Jeśli nie można się pomylić z Kostią, dla Sashy wystarczy 11 pytań (pomyśl dlaczego). Sasha ma więc cztery pytania "na składzie" i powinien starać się zadawać pytania, aby w pewnym momencie odpowiedzi Kostii zaczęły się sprzeczać, wtedy można było odgadnąć liczbę K w standardowy sposób, za każdym razem zmniejszając o połowę liczbę pozostałych opcji.


Wskazówka 3

Spróbuj wymyślić zestawy do pierwszych 11 pytań Sashy, aby po udzieleniu odpowiedzi Sasha mógł pozostawić tylko 12 liczb na "podejrzanej liście" – jeden pod warunkiem, że Kostia nie był jeszcze zły, i jeszcze jedną liczbę dla każdego możliwego błędu Bone.


Rozwiązanie

Najpierw robimy to, co zasugerowano w punkcie 3.

Najprostszym sposobem na to jest użycie systemu binarnego. Od 2013 roku jest mniej niż 211 = 2048, wtedy binarny zapis dowolnej z możliwych liczb nie zawiera więcej niż 11 cyfr. Ponieważ cyfra w każdej cyfrze to 0 lub 1, Sasha może bezpośrednio zadać pierwsze pytania: "Czy to prawda, że ​​liczba w i-m (z prawej) binarny numer zamierzonej liczby to 1?"przechodząc przez wszystkie i od 1 do 11.

Jeśli Kostya nie popełni błędu, odpowiadając na którekolwiek z tych pytań, wtedy Sasha znajdzie wszystkie cyfry zamierzonej liczby, to znaczy, że zna numer K (chociaż, ponieważ nie wie, czy Kostia był w błędzie, nie może stwierdzić, że zna zamierzoną liczbę). Jeśli Kostia popełni błąd, odpowiadając na pewne pytanie, będzie to oznaczać zamierzoną liczbę K różni się od kości podanych odpowiedzi w jednym kawałku.Ale ta liczba jest również tylko jedna – a ponieważ błąd mógł zostać popełniony w jednym z 11 bitów, jest dokładnie 11 podejrzanych liczb.

Oznacz 12 numerów z wynikowej listy. K0, K1, … , K11 (pierwszy – w przypadku braku błędów, reszta – w przypadku błędu w odpowiedzi na odpowiednie pytanie).

Jak teraz Sasha powinien działać? Jeśli zadaje następne pytanie (patrz podpowiedź 1 na temat struktury pytań) na temat zestawu d liczby (w każdym razie, ale nie wliczając K0; na przykład K1, … , Kd) i uzyskać odpowiedź "tak", może to oznaczać jedną z dwóch rzeczy: jedną z nich d liczby, albo Kostia mylił się w odpowiedzi na to pytanie. Ale jeśli Kostya był w błędzie, mógł tylko zgadywać K0ponieważ inne opcje Kd+1, … , K11 to znaczy, że Kostia był już w błędzie w odpowiedzi na niektóre z poprzednich pytań i nie może popełnić drugiego błędu! Tak więc, z odpowiedzią "tak" Sasha pozostaje dokładnie d + 1 opcje, a on rozumie, że Kostya mylił się w jednej z poprzednich odpowiedzi. Ponieważ po tym pytaniu Sasha ma jeszcze 3 pytania pozostawione w rezerwie, będzie mógł odgadnąć planowaną liczbę 8 opcji. Dlatego możemy umieścić d + 1 = 8, tj. d = 7, i rozważ tylko odpowiedź "nie" na dwunaste pytanie.

Odpowiedź brzmi "nie" oznacza, że ​​Kostia naprawdę nie mógł myśleć o liczbach. K1, … , K7 (w przeciwnym razie byłby to jego drugi błąd). Po takiej odpowiedzi lista podejrzanych liczb spadła do 5: K0, K8, K9, K10, K11. Twierdząc w ten sam sposób co powyżej, upewniamy się, że przy pytaniu trzynastym Sasha może zapytać o liczby K8, K9, K10: jeśli odpowiedź brzmi tak, będzie musiał odgadnąć jedną z czterech liczb K0, K8, K9, K10co będzie wystarczało dla dwóch pozostałych pytań, aw przypadku odpowiedzi "nie" na liście podejrzanych pozostanie tylko K0 i K11.

Teraz (14 pytanie) wystarczy zapytać o jeden numer K11. Podobnie jak w sytuacjach opisanych powyżej, odpowiedź "tak" będzie oznaczać, że Kostia już popełnił błąd, a następnie Sasha odgadnie jedną z dwóch liczb dla ostatniego, 15 pytania. Cóż, po odpowiedzi "nie" na 15 pytanie, nie możesz już pytać – Sasha może od razu wywnioskować, że Kostia wymyślił K = K0.


Posłowie

1. Czy można było obejść się bez użycia systemu binarnego? Tak, oczywiście.

Zauważ, że w każdym momencie "gry" pomiędzy Kostią i Sashą sytuacja ("stan gry") jest w pełni opisana przez dwie liczby [a; b]: a – liczba liczb, które mógł odgadnąć Kostia, pod warunkiem, że nie popełnił jeszcze błędów, ale b – liczba liczb, które mógł odgadnąć Kostia, pod warunkiem, że popełnił już błąd w jednej z poprzednich odpowiedzi.Gra rozpoczyna się od [2013; 0], ale powinno się kończyć w tym momencie, gdy "podejrzenie" pozostaje jedynym – czyli albo na stanie [1; 0] lub w [0; 1].

Niech pierwsze pytanie Sashy będzie związane z zestawem d liczby Następnie po odpowiedzi "tak" nowy stan gry stał się [d; 2013 – d], a po odpowiedzi "nie" – [2013 r. – d; d] (pomyśl dlaczego tak jest). Jeśli Sasha podzieli zestaw liczb z roku 2013 na dwie prawie równe części, wówczas otrzyma jeden ze stanów [1007; 1006] i [1006; 1007]. Z drugim pytaniem może podzielić każdą z tych części na pół – i uzyskać albo [504; 1006] lub [503; 1007] (tutaj 1007 liczb otrzymuje się w następujący sposób: po pierwsze, te 504 liczby od b = 1007, które Sasha zawarł w swoim zestawie, a po drugie, te 503 liczby z a = 1006, którego nie uwzględnił w zestawie – ale jeśli Kostya popełnił błąd, odpowiadając na to pytanie, to numery te mogły zostać im przekazane).

Kontynuując zadawanie pytań w ten sam sposób, otrzymujemy konsekwentnie

[504; 1006] → [252; 755] → [126; 504] → [63; 315] → [32; 189] → [16; 111] → [8; 64] → [4; 36] → [2; 20] → [1; 11]

(lub [503; 1007] → [251; 755], czyli mniej niż w powyższym łańcuchu. Natychmiast pozwoliłem sobie na pominięcie kilku podobnych opcji w tym łańcuchu.)

Tak więc sytuacja "1 + 11" opisana w naszym rozwiązaniu mogła zostać osiągnięta bez jakiejkolwiek wzmianki o systemie binarnym.Cóż, wtedy [1; 11] → ([1; 4] lub [0; 8]) → ([1; 1] lub [0; 4]) → ([1; 0] lub [0; 2]) → [0; 1].

2. Nasze rozwiązanie pokazuje, że zamiast liczb od 1 do 2013, Sasha może pozwolić, aby Kostia odgadł liczby od 0 do 2047 i nadal nadąża za zgadywaniem na 15 pytań. Pozostaje jednak bez odpowiedzi bardzo naturalne pytanie generalizujące. Niech Sasha pozwoli ustawić nie 15, ale N pytania. W jakim zakresie (od 0 do M) Czy może pozwolić, aby Kostia odgadł liczby, tak aby te pytania wystarczyły dla zagwarantowanego zgadywania?

Pełna odpowiedź na to pytanie (a dokładniej dowód wierności tej odpowiedzi) nie jest tak prosta, jak na pierwszy rzut oka wydaje się. Można napisać tak: jeśli (tutaj [x] – liczba całkowita liczby x, tj. największa liczba całkowita nie przekracza x) wyraźnie M = si jeśli s dziwne M = s – 1. Interesujące jest również to, że minęło ponad 20 lat od momentu postawienia zadania na uzyskanie kompletnego rozwiązania!

Wygląda na to, że po raz pierwszy problem zgadywania ze zdolnością do popełniania błędów w odpowiedziach został sformułowany przez wybitnego węgierskiego matematyka Alfreda Renyi w węgierskim artykule z 1961 roku. Kilka lat później (w swojej autobiografii "Przygody matematyki") spopularyzował ją amerykański matematyk Stanisław Ulam.

"Hawkins i ja [David Hawkins, filozof, późniejszy autor wspaniałej popularnej książki naukowej Language of Nature. Uwaga auth.] zastanawiał się nad następującym powiązanym zadaniem: wariant gry "Dwadzieścia pytań". Jedna osoba myśli o liczbie w przedziale od jednego do jednego miliona (która jest mniejsza niż 220). Inna osoba może zadawać do dwudziestu pytań, z których każdy musi odpowiedzieć tylko "tak" lub "nie". Oczywiście, liczbę można odgadnąć, jeśli najpierw zapytasz: czy ta liczba jest w pierwszej połowie miliona? W kolejnym pytaniu ponownie pomniejsz wynikowy przedział liczb i tak dalej. Ostatecznie liczbę można odgadnąć w mniej niż dzienniku.21,000,000 razy Załóżmy teraz, że uczestnik ma prawo kłamać raz lub dwa razy. Ile pytań zajmie uzyskanie poprawnej odpowiedzi? Oczywiste jest, że w celu odgadnięcia jednego z 2n numery wymagane więcej n pytania, ponieważ o tym, kiedy kłamstwo zostało powiedziane, nie jest znane. Zasadniczo ten problem nie został rozwiązany. "

Kompletne rozwiązanie problemu Ulam w przypadku jednego błędu otrzymał Andrzej Pelz w 1986 r., A za dwa błędy w 1990 r. Po kolejnych 10 latach matematycy zdołali całkowicie rozwiązać problem "prawa do trzech błędów". Do zadań z bokołotylko pojedyncze przypadki zostały rozwiązane przez dużą liczbę błędów i nie znaleziono jeszcze pełnych rozwiązań.

3. Jeśli nie potrzebujesz optymalnych rozwiązań i minimalnej liczby pytań, wszystko staje się znacznie łatwiejsze. Tak więc w 1991 r. Podczas Ogólnopolskiej Olimpiady Matematycznej zaproponowano następujący problem (autorzy – A. Andzhans, I. Soloviev, V. Slitinsky.)

Badacz zaproponował plan przesłuchania świadka, gwarantujący wykrycie przestępstwa. Zamierza zadać pytania, na które można odpowiedzieć "tak" lub "nie" (pytanie, które zostanie zadane, może zależeć od odpowiedzi na poprzednie). Badacz uważa, że ​​wszystkie odpowiedzi będą poprawne, obliczył, że w każdym wariancie odpowiedzi nie będzie więcej niż 91 pytań. Wykazać, że badacz może wykonać plan zawierający nie więcej niż 105 pytań, gwarantujących rozwiązanie przestępstwa oraz w przypadku, gdy na jedno pytanie można odpowiedzieć nieprawidłowo (ale może być tak, że wszystkie odpowiedzi są poprawne).

Rozwiązanie tego problemu opierało się na innym pomyśle: jak zmodyfikować pierwotny plan pytań, dodając do niego "pytania kontrolne". Po pierwsze, badacz zadaje pierwsze 13 pytań z pierwotnego planu, a następnie zadaje 14. pytanie "Czy skłamałeś w poprzedniej serii pytań?".Po otrzymaniu odpowiedzi "nie", może nadal zadawać serię 12, 11, 10, …, 1 pytań z planu, powtarzając pytanie kontrolne po każdej serii (pomyśl dlaczego odpowiedź "nie" na pytanie kontrolne gwarantuje, że odpowiedzi na pytania serii były naprawdę wierny). Jeśli odpowiedź na pytanie "tak" zostanie odebrana na jedno z pytań kontrolnych, cała poprzednia seria zostanie powtórzona, bez konieczności zadawania pytań kontrolnych. Jeśli odpowiedź brzmi "tak", zostanie odebrana kpytanie kontrolne, a następnie oprócz pierwotnego planu będzie musiał zapytać k + (14 – k) = 14 pytań. Zauważ, że kłamstwo mogło być w odpowiedzi na pytanie kontrolne – w tym przypadku odpowiedzi na powtarzające się serie będą dokładnie takie same jak za pierwszym razem.

Dlaczego "modyfikacja planu" nie jest optymalną strategią i nie gwarantuje minimalnej liczby zadawanych pytań? Na przykład, ponieważ początkowe zadanie badacza było równoznaczne z odgadnięciem zamierzonej liczby z zakresu od 0 do 291 – 1. Do tego, jak już wiemy, nie 105, ale wystarczy tylko 98 pytań: 298/99 > 298/27 = 291. Niemniej modyfikacja zaproponowana w czasie Olimpiady zwiększa długość planu N(N – 1) / 2 pytania nie więcej niż N, to jest w kolejności pierwiastka kwadratowego z podwojonej pierwotnej długości. To na ogół też nie jest takie złe.

4. Dlaczego poważni matematycy w ogóle wykonują takie "zabawkowe" zadania? Faktem jest, że problem ten jest bardzo zbliżony do klasycznych problemów teorii kodowania i jest z nimi blisko powiązany (patrz: Wykrywanie i korygowanie błędów, Kod Hamminga). Rzeczywiście, w opisywanej grze, Kostya i Sasha mogą z góry zgodzić się (zanim Kostia wybierze zamierzony numer) na listę zadawanych pytań (w tym ustalić, które pytanie zostanie zadane jako drugie, odpowiadając tak na pierwsze pytanie, a które odpowiedzieć "nie" i podobnie uzgodnić następujące pytania). Oznacza to, że Kostia może po prostu wysłać Sashie sekwencję 15 odpowiedzi – lub, jeśli chcesz, sekwencję 15 znaków "0" i "1". Dla każdej takiej sekwencji Sasha będzie w stanie odgadnąć ("odtworzyć") liczbę planów Kostii, a zatem określić odpowiedź na pytanie, które Kostia mylił. To kod Hamminga korygujący jeden błąd.

Artykuł R. Hamminga "Kody wykrywające i korygujące błędy" został opublikowany w 1950 roku (oryginał można zobaczyć na przykład tutaj, PDF, 3,1 MB). W tym czasie oryginalne dane na komputery były ładowane za pomocą kart dziurkowanych, a urządzenia wejściowe z kartami dziurkowanymi były tak niewiarygodne, że prawie żadna gruby pokład nie mógł być odczytany bez błędów.Uruchomienie programu zawierającego błąd doprowadziło w najlepszym wypadku do katastrofy, po której obliczenia ustały i trzeba było ponownie przeczytać talia, a co najgorsze – całkowicie zatrzymać maszynę. Kody opracowane przez Hamminga pozwoliły nie tylko wykryć błędy, ale także automatycznie je poprawić. To była prawdziwa rewolucja!

Odtąd oczywiście niezawodność systemów komputerowych wzrosła wielokrotnie, jednak błędy korygujące kody nie stały się mniej popularne z tego powodu: stanowią teraz podstawę protokołów komunikacyjnych. Linie komunikacyjne na pewno się poprawią, ale potrzeba kodów korekcyjnych prawie nigdy nie zniknie: błędy są odwiecznymi satelitami każdej ludzkiej działalności.


Like this post? Please share to your friends:

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: