Hádajte, čo mám • Konstantin Knoop • Populárne vedecké úlohy na "prvkoch" • Matematika

Hádaj, čo mám

úloha

Kostya si myslela prirodzené číslo K od 1 do 2013 a je pripravený odpovedať "áno" alebo "nie" na akékoľvek otázky, ktoré takéto odpovede povoľujú. Avšak má právo dať chybnú odpoveď nie viac ako raz (pre všetky odpovede).

Sasha chce Kostyu požiadať o viac ako 15 otázok, podľa odpovedí, na ktoré môže vždy odhadnúť zamýšľané číslo. pomôcť aby to urobil.


Tip 1

Zvyčajne sa pri takýchto úlohách pokúšajú opýtať otázky "porovnávania otázok", to znamená: "Je pravda, že vaše číslo je menšie ako toto" (alebo "viac ako toto"). Nie je však absolútne potrebné, aby sa Sasha obmedzila na takéto otázky. Všeobecnejší typ otázok je nasledovný: Sasha píše akýkoľvek súbor čísel (ktorý obsahuje niektoré čísla od 1 do 2013) a pýta sa Kostyy: "Je pravda, že ste naplánovali jedno z týchto čísel?".


Tip 2

Ak by sa Kostya nemohla mýliť, Sasha by mala 11 otázok (myslieť prečo). Takže Sasha má štyri otázky "na sklade" a mal by sa pokúsiť klásť otázky tak, že ak sa v určitom momente začnú Kostya odpovede začať vzájomne protirečúvať, potom by sa dalo odhadnúť číslo K štandardným spôsobom, pri každom znížení počtu zostávajúcich možností na polovicu.


Tip 3

Snažte sa nájsť súbory pre prvých 11 otázok Sasha, aby po ich odpovedi mohol Sasha nechať v "podozrivom zozname" len 12 čísel – jedno za predpokladu, že Kostya sa ešte nespomína a ďalšie číslo pre každú možnú chybu kostí.


rozhodnutie

Najprv robíme to, čo bolo navrhnuté v tip 3.

Najjednoduchší spôsob, ako to urobiť, je použiť binárny systém. Od roku 2013 je menej ako 211 = 2048, potom binárny záznam ktoréhokoľvek z možných koncipovaných čísel neobsahuje viac ako 11 číslic. Keďže číslica v každej číslici je 0 alebo 1, Sasha môže priamo položiť prvé otázky: "Je pravda, že číslo v ja-m (vpravo) binárne číslo zamýšľaného čísla je 1?"prechádza všetkými ja od 1 do 11.

Ak Kostya nerobí chybu pri odpovedi na niektorú z týchto otázok, potom Sasha zistí všetky číslice zamýšľaného čísla, to znamená, že pozná číslo K (aj keď nevie, či Kostya je zle, nemôže vyvodzovať, že vie o zamýšľanom čísle). Ak Kostya urobí chybu pri odpovedi na niektoré otázky, bude to znamenať, že zamýšľané číslo K odlišné od kostí dané odpovede v jednom bit.Toto číslo je však len jedno – a keďže chyba môže byť vykonaná v ktoromkoľvek z 11 bitov, existuje presne 11 podozrivých čísel.

Označte 12 čísel z výsledného zoznamu. K0, K1, … , K11 (prvá – pri absencii chýb, zvyšok – v prípade chyby pri odpovedi na zodpovedajúcu otázku).

Ako by mala teraz pôsobiť Sasha? Ak sa pýta na ďalšiu otázku (pozri názov 1 o štruktúre otázok) o súboru d čísla (v každom prípade, ale nie K0; napríklad K1, … , Kd) a získajte odpoveď "áno", môže to znamenať jednu z dvoch vecí: buď jednu z nich d čísla, Kostya sa mýlil v odpovedi na túto otázku. Ale keby sa Kostya zle, mohol len uhádnuť K0pretože iné možnosti Kd+1, … , K11 že Kostya sa už v odpovedi na niektoré z predchádzajúcich otázok mýlil a nemôže urobiť druhú chybu! Takže s odpoveďou "áno" zostáva Sasha presne d + 1 možností a on chápe, že Kostya v jednej z predchádzajúcich odpovedí nesprávne. Keďže po tejto otázke má Sasha ešte 3 ďalšie otázky, bude môcť uhádnuť plánovaný počet 8 možností. Preto môžeme dať d + 1 = 8, t.j. d = 7 a zvážte len odpoveď "nie" na 12. otázku.

Odpoveď je "nie" znamená, že Kostya naozaj nemohol myslieť na čísla. K1, … , K7 (inak by to bola jeho druhá chyba). Takže po takejto odpovedi sa zoznam podozrivých čísel znížil na 5: K0, K8, K9, K10, K11, S takým istým spôsobom, ako sme uviedli vyššie, sa ubezpečujeme, že s troma otázkou sa Sasha môže opýtať na čísla K8, K9, K10: ak je odpoveď áno, bude musieť uhádnuť jedno zo štyroch čísel K0, K8, K9, K10čo bude stačiť na zostávajúce dve otázky a v prípade odpovede "nie" v zozname podozrivých zostane len K0 a K11.

Teraz (štrnásta otázka) stačí sa spýtať na jedno číslo K11, Rovnako ako v situáciách, ktoré sme analyzovali vyššie, odpoveď "áno" bude znamenať, že Kostya už urobil chybu, a potom Sasha odhadne jedno z dvoch čísel na poslednú, 15. otázku. No, po odpovedi "nie" z 15. otázky sa už nemôžete spýtať – Sasha môže okamžite vyvodiť záver, že Kostya K = K0.


Doslov

1. Bolo to možné bez použitia binárneho systému? Áno, samozrejme.

Všimnite si, že v každom momente "hry" medzi Kostyou a Sasou je situácia ("herný stav") plne opísaná dvoma číslami [; b]: – počet čísel, ktoré Kostya dokázal odhadnúť, za predpokladu, že sa ešte nedopustil chyby, ale b – počet čísel, ktoré by Kostya dokázal odhadnúť, za predpokladu, že už urobil chybu v jednej z predchádzajúcich odpovedí.Hra začína od [2013; 0], ale malo by sa skončiť v tom okamihu, kedy číslo "podozrivé" zostane jediné – či už v stave [1; 0] alebo na [0; 1].

Nech Sashovu prvú otázku súvisí so súborom d Čísla. Potom po odpovedi "áno" sa nový stav hry stal [d; 2013 – d] a po odpovedi "nie" – [2013 – d; d] (premýšľajte, prečo je to tak). Ak Sasha rozdelí súbor čísel 2013 na dve takmer rovnaké časti, potom dostane jeden zo štátov [1007; 1006] a [1006; 1007]. S druhou otázkou môže rozdeliť každú z týchto častí na polovicu a získať buď [504; 1006] alebo [503; 1007] (tu sa získa 1007 čísel takto: po prvé, tých 504 čísel z b = 1007, ktorý Sasha zahrnul do svojho súboru, a po druhé, tie 503 čísla od = 1006, ktoré nezahrnul do súboru – ale ak Kostya urobil chybu pri odpovedi na túto otázku, mohli by sa im tieto čísla stať).

Pokračovaním v položení otázok rovnakým spôsobom sa stáva dôsledne

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

(alebo [503; 1007] → [251; 755], čo je menej ako v uvedenom reťazci.) Okamžite som si dovolil vynechať niekoľko podobných možností v tomto reťazci.)

Preto situácia "1 + 11" popísaná v našom riešení mohla byť dosiahnutá bez akejkoľvek zmienky o binárnom systéme.No, potom [1; 11] → ([1, 4] alebo [0, 8]) → ([1, 1] alebo [0; 4]) → ([1, 0] alebo [0, 2]) → [0; 1].

2. Naše riešenie ukazuje, že namiesto čísel od 1 do 2013 Sasha si mohol dovoliť Costa hádanie čísla od 0 do 2047, a stále hádať s 15 otázkami. Ponecháva však nezodpovedanú veľmi prirodzenú generalizujúcu otázku. Nechajte Sasu nechať nastaviť nie 15, ale N záležitosti. V akom rozsahu (od 0 do M) Môže schváliť pobrežia hádanie čísla k týmto otázkam dostatočnou zárukou hádať?

Úplná odpoveď na túto otázku (či skôr dôkazom správnosti odpovede) nie je tak jednoduché, ako sa zdá na prvý pohľad. Môže to byť napísané takto: ak (tu [x] – celá časť čísla x, t.j. najväčšie celé číslo nepresahujúce x) jasne, potom M = sa ak s zvláštne M = s – 1. Je zaujímavé, a skutočnosť, že má viac ako 20 rokov od doby formulácie problému až do jeho kompletné riešenie!

Zdá sa, že prvou úlohou hádať s možnosťou robiť chyby v odpovediach formulovaných pozoruhodnú maďarský matematik Alfred Rényiho v článku v roku 1961 v maďarskom jazyku. O niekoľko rokov neskôr (v jeho autobiografii, "The Adventures of matematiky") spopularizoval jeho americký matematik Stanislaw Ulam.

"Hawkins a ja [David Hawkins, filozof, neskôr autor nádhernej populárnej vedeckej knihy Jazyk prírody. Pribl. aut.] premýšľal nad nasledujúcou súvisiacou úlohou: variáciou hry Twenty Questions. Jedna osoba si myslí o čísle v rozsahu od jedného do jedného milióna (čo je len menej ako 220). Ďalšia osoba môže požiadať o až dvadsať otázok, z ktorých každý musí odpovedať iba "áno" alebo "nie". Je zrejmé, že číslo sa dá odhadnúť, ak sa prvýkrát pýtate: je toto číslo v prvej polovici milióna? V ďalšej otázke znova znížte na polovicu výsledný interval čísel atď. V konečnom dôsledku môže byť číslo odhadnuté za menej ako denník.21 000 000 krát Predpokladajme, že účastník má právo ležať raz alebo dvakrát. Koľko otázok bude potrebné na získanie správnej odpovede? Je zrejmé, že na odhad jedného z 2n čísla vyžadované viac n otázky, pretože o tom, kedy bola lži povedané, je neznáme. Vo všeobecnosti sa tento problém nevyrieši. "

Kompletné riešenie problému Ulam v prípade jednej chyby prijal Andrzej Pelz v roku 1986 a za dve chyby v roku 1990. Po ďalších 10 rokoch sa matematici podarilo úplne vyriešiť problém pre "právo na tri chyby". Pre úlohy s boiba jednotlivé osobitné prípady boli vyriešené veľkým počtom chýb a zatiaľ neboli nájdené žiadne úplné riešenia.

3. Ak nevyžadujete optimálne riešenia a minimálny počet otázok, všetko sa stáva oveľa jednoduchšie. Takže v roku 1991 sa na Matematickej olympiáde v celej únii navrhol nasledujúci problém (autori – A. Andžans, I. Soloviev, V. Slíčin).

Vyšetrovateľ prišiel s plánom na vypočúvanie svedka, ktorý zaručil zistenie trestného činu. Pýta sa na otázky, ktoré môžu odpovedať len "áno" alebo "nie" (otázka, ktorá sa bude klásť, môže závisieť od odpovedí na predchádzajúce otázky). Vyšetrovateľ je presvedčený, že všetky odpovede budú správne, vypočítal, že pri každej variante odpovedí sa nebude klásť viac ako 91 otázok. Dokážte, že vyšetrovateľ môže vypracovať plán s maximálne 105 otázkami, ktorý zaručí riešenie trestného činu av prípade, že na jednu otázku možno odpovedať nesprávne (ale pravdepodobne všetky odpovede sú správne).

Riešenie tohto problému bolo založené na inej myšlienke: ako zmeniť pôvodný plán otázok pridaním "kontrolných otázok" k nemu. Po prvé, vyšetrovateľ sa pýta prvých 13 otázok pôvodného plánu a potom sa pýta štrnásta otázka: "Vy ste ležali v predchádzajúcej sérii otázok?".Po prijatí odpovede "nie" môže pokračovať v žiadosti o sériu 12, 11, 10, …, 1 otázok o pláne a opakovať kontrolnú otázku po každej sérii (premýšľajte, prečo odpoveď "nie" na kontrolnú otázku zaručuje, že odpovede na otázky seriálu boli skutočne true). Ak je odpoveď "áno" prijatá na jednu z kontrolných otázok, potom sa celý predchádzajúci seriál opakuje, bez ďalších otázok týkajúcich sa kontroly. Ak je odpoveď "áno" prijatá kkontrolná otázka, potom sa okrem pôvodného plánu bude musieť spýtať k + (14 – k) = 14 otázok. Všimnite si, že v odpovedi na kontrolnú otázku mohla byť lež – v tomto prípade budú odpovede na opakované série úplne rovnaké ako prvýkrát.

Prečo nie je "úprava plánu" optimálna stratégia a nezaručuje minimálny počet otázok? Napríklad, pretože počiatočná úloha vyšetrovateľa bola ekvivalentná hádaniu zamýšľaného čísla z rozsahu od 0 do 291 – 1. Ale za to, ako už vieme, nie je 105, ale stačí len 98 otázok: 298/99 > 298/27 = 291, Napriek tomu zmena navrhovaná v olympijskom probléme zvyšuje dĺžku plánu N(N – 1) / 2 otázky nie viac ako N, to znamená, že je v poradí druhá odmocnina dvojnásobku pôvodnej dĺžky. To vo všeobecnosti tiež nie je tak zlé.

4. Prečo robia vážne matematici vôbec takéto "hračky"? Faktom je, že tento problém je veľmi blízky klasickým problémom teórie kódovania a je s nimi úzko súvisí (pozri: Detekcia a korekcia chýb, Hammingov kód). V hre, ktorú sme opísali, sa Kostya a Sasha môžu dohodnúť vopred (predtým, ako Kostya vyberie zamýšľané číslo) o zozname otázok (vrátane súhlasu s otázkou, ktorá bude položená druhá pri odpovedi na otázku áno na prvú otázku a ktorá z nich odpovedzte "nie" a podobne sa dohodnite na nasledujúcich otázkach). To znamená, že Kostya môže jednoducho poslať Sashu sekvenciu 15 odpovedí – alebo ak chcete, sekvenciu 15 znakov "0" a "1". Pre každú takúto sekvenciu bude Sasha schopná hádať ("rekonštruovať") počet Kostijových plánov, a preto určí odpoveď, na ktorú otázku sa Kostya mýlil. To je Hammingov kód, ktorý opravuje jednu chybu.

Článok R. Hammingov "Kódy, ktoré zisťujú a opravujú chyby" bol publikovaný v roku 1950 (originál je možné vidieť napríklad tu, PDF, 3,1 MB). V tom čase boli pôvodné dáta do počítačov nabité pomocou dierovaných kariet a vstupné zariadenia dierovaných kariet boli také nespoľahlivé, že bez chyby bolo možné čítať takmer žiadnu dosť hrubú palubu.Spustenie programu obsahujúceho chybu viedlo v najlepšom prípade k havárii, po ktorom sa výpočty zastavili a paluba sa znova mala čítať a v najhoršom prípade úplne zastaviť stroj. Kódy, ktoré vynašiel Hamming, umožnili nielen odhaliť chyby, ale tiež ich automaticky opraviť. Bola to skutočná revolúcia!

Odvtedy sa spoľahlivosť počítačových systémov samozrejme mnohonásobne zvýšila, avšak korekčné chyby kódov sa nestali menej populárne z tohto dôvodu: teraz tvoria základ komunikačných protokolov. Komunikačné linky sa určite zlepšia niekedy, ale potreba opravných kódexov sa takmer nikdy nezmizne: chyby sú večné satelity ľubovoľnej ľudskej činnosti.


Like this post? Please share to your friends:
Pridaj komentár

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