Atspėk, ką aš turiu • Konstantinas Knoopas • Populiariosios mokslinės užduotys "Elementai" • Matematika

Atspėk, ką aš turiu

Užduotis

Kostja suprato natūralų skaičių K nuo 1 iki 2013 m. ir yra pasirengusi atsakyti "taip" arba "ne" į klausimus, kurie leidžia tokius atsakymus. Tačiau jis turi teisę klaidingai atsakyti ne daugiau kaip kartą (visiems atsakymams).

Sasha nori paklausti Kostos ne daugiau kaip 15 klausimų, pagal atsakymus į kuriuos jis visada gali nuspėti numatytą numerį. Pagalba jam tai padaryti.


1 patarimas

Paprastai tokiose užduotyse jie stengiasi paklausti "klausimai-palyginimai", ty "Ar tiesa, kad jūsų numeris yra mažesnis už šį" (arba "daugiau nei šis"). Tačiau nėra poreikio, kad Sasha apsiribotų tokiais klausimais. Labiau paplitęs klausimas yra toks: Sasha rašo bet kokį skaičių rinkinį (kuris apima kai kuriuos skaičius nuo 1 iki 2013 m.) Ir klausia Kostya: "Ar tiesa, kad jūs planavote vieną iš šių skaičių?".


2 patarimas

Jei Kostya negalėtų būti klaidinga, už Sasha pakaktų 11 klausimų (galvoja kodėl). Taigi, Sasha turi keturis klausimus "sandėlyje", ir jis turėtų pabandyti užduoti klausimus, kad, jei kokiu nors metu Kostos atsakymai pradėjo prieštarauti vieni kitiems, tuomet galėjo suvokti skaičių K standartiniu būdu, kiekvieną kartą sumažindama likusių variantų skaičių perpus.


3 patarimas

Stenkitės sugalvoti pirmųjų 11 Sašo klausimų, kad, atsakydami į juos, "įtartinas" sąrašas paliktų tik 12 skaičių – vienas pateiktas, kad Kostya dar nebuvo klaidingas ir dar vienas skaičius kiekvienai galimai kaulų klaidai.


Sprendimas

Pirmiausia mes darome tai, kas buvo pasiūlyta 3 pastaboje.

Lengviausias būdas tai padaryti – naudoti dvejetainę sistemą. Nuo 2013 m. Yra mažesnis nei 211 = 2048, tada bet kurio galimo įsivaizduojamo skaičiaus dvejetainis įrašas turi ne daugiau kaip 11 skaitmenų. Kadangi kiekvieno skaitmens skaitmenis yra 0 arba 1, Sasha gali tiesiogiai užduoti pirmuosius klausimus: "Ar tiesa, kad skaičius i-m (dešinėje) numatyto numerio dvejetainis numeris yra 1?"eidamas per visus i nuo 1 iki 11.

Jei Kostya nepadarys klaidos atsakydamas į bet kurį iš šių klausimų, tada Sasha išsiaiškins visus numatytą numerį, ty jis žinos skaičių K (nors, nes jis nežino, ar Kostya buvo neteisingas, jis negali daryti išvados, kad jis žino numatytą numerį). Jei Kostya klaidingai atsakys į kai kuriuos klausimus, tai reiškia, kad numatytas numeris K skiriasi nuo kaulų, kuriems atsakymai pateikiami bet kuriuo vienu bitu.Bet toks skaičius taip pat yra tik vienas – ir kadangi klaida galėjo būti padaryta bet kuriame iš 11 bitų, yra tik 11 įtartinų skaičių.

Apibūdinkite 12 skaičių iš gauto sąrašo. K0, K1, … , K11 (pirmasis – nesant klaidų, o likusieji – tuo atveju, kai atsakymas į atitinkamą klausimą yra klaida).

Kaip turėtų veikti Sasha? Jei jis klausia kito klausimo (žr. 1 užklausų struktūros užuominą) apie rinkinį d numeriai (vistiek, bet ne K0; Pavyzdžiui K1, … , Kd) ir gauti atsakymą "taip", tai gali reikšti vieną iš dviejų dalykų: vieną iš jų d skaičiai, Kostja klaidingai atsakė į šį klausimą. Bet jei Kostja neteisingai, jis galėjo tik spėti K0nes kitos galimybės Kd+1, … , K11 reiškia, kad Kostya jau klaidingai atsakė į kai kuriuos ankstesnius klausimus ir negali padaryti antrosios klaidos! Taigi, su atsakymu "taip", Sasha išlieka tiksliai d + 1 parinktis, ir jis supranta, kad Kosty buvo neteisingas viename iš ankstesnių atsakymų. Kadangi po šio klausimo Sasha dar 3 klausimai liko rezervo, jis galės atspėti planuojamą 8 variantų skaičių. Todėl galime įdėti d + 1 = 8, t.y. d = 7 ir apsvarstyti tik atsakymą "ne" į 12 klausimą.

Atsakymas "ne" reiškia, kad Kostja tikrai negalėjo galvoti apie skaičių. K1, … , K7 (kitaip tai būtų jo antroji klaida). Taigi, po tokio atsakymo įtartinų skaičių sąrašas sumažėjo iki 5: K0, K8, K9, K10, K11. Remdamiesi tokiu pačiu būdu, kaip ir anksčiau, mes įsitikinę, kad su 13 klausimu Sasha gali paklausti apie skaičių K8, K9, K10: jei atsakymas yra "taip", jis turės atspėti vieną iš keturių skaičių K0, K8, K9, K10už ką bus užtenka dviejų likusių klausimų, o atsakymo "ne" atveju įtariamojo sąraše bus tik K0 ir K11.

Dabar (14 klausimas) pakanka paklausti apie vieną numerį K11. Kaip ir anksčiau išnagrinėtose situacijose, atsakymas "taip" reiškia, kad Kostya jau padarė klaidą, o paskui Sasha atsimins vieną iš dviejų numerių paskutiniam, 15 klausimui. Na, atsakius "ne" nuo 15-ojo klausimo, jūs jau nebegalėsite paklausti – Sasha gali iš karto padaryti išvadą, kad Kostya sukūrė K = K0.


Po žodžio

1. Ar tai buvo įmanoma be binarinės sistemos naudojimo? Taip, žinoma.

Atkreipkite dėmesį, kad kiekvienu "žaidimo" tarp "Kostya" ir "Sasha" momentu situacija ("žaidimo būklė") yra visiškai aprašyta dviem skaičiais [a; b]: a – skaičių, kuriuos Kostja galėjo atspėti, su sąlyga, kad jis dar nepadarė klaidų, bet b – numerių, kuriuos Kostja galėjo atspėti, skaičius, su sąlyga, kad jis jau padarė klaidą viename iš ankstesnių atsakymų.Žaidimas prasideda nuo [2013; 0], bet jis turėtų baigtis tuo momentu, kai "įtariamo" numeris išlieka vienintelis – tai yra arba valstybėje [1; 0] arba [0; 1].

Tegul pirmasis Sasha klausimas turi būti susijęs su rinkiniu d numeriai Tada po to, kai atsakymas "taip", nauja žaidimo būklė tapo [d; 2013 – d], o po atsakymo "ne" – [2013 – d; d] (pagalvokite, kodėl taip yra). Jei Sasha suskirsto 2013 m. Skaičių į dvi beveik lygias dalis, jis gaus vieną iš būsenų [1007; 1006] ir [1006; 1007]. Antruoju klausimu jis gali padalinti visas šias dalis per pusę ir gauti arba [504; 1006] arba [503; 1007] (čia 1007 numeriai gaunami taip: pirma, tie 504 skaitmenys iš b = 1007, kurį Sasha įtraukė į savo rinkinį, ir, antra, tie 503 skaičiai iš a = 1006, kurio jis neįtraukė į rinkinį – bet jei Kostja padarė klaidą, atsakydamas į šį klausimą, tuomet jie galėjo būti tokie skaičiai).

Tęsdami užduoti klausimus taip pat, mes nuolat

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

(arba [503; 1007] → [251; 755], kuris yra mažesnis nei minėtoje grandinėje. Aš tuoj pat leido sau praleisti keletą panašių variantų šioje grandinėje.)

Taigi "1 + 11" situacija, apibūdinta mūsų sprendime, galėjo būti pasiekta be paminėtos dvejetainės sistemos.Na, tada [1; 11] → ([1; 4] arba [0; 8]) → ([1; 1] arba [0; 4]) → ([1; 0] arba [0; 2]) → [0; 1].

2. Mūsų sprendimas rodo, kad vietoj skaičių nuo 1 iki 2013 m. Sasha galėjo leisti Kostį nuvykti nuo 0 iki 2047 ir vis dar nepastebėti 15 klausimų. Tačiau jis neatsako natūraliai apibendrinantis klausimas. Leisk Sasha leisti nustatyti ne 15, bet N klausimai. Kurioje diapazone (nuo 0 iki M) Ar jis gali leisti Kostiui sugaiti skaičių, kad šiems klausimams pakaktų už garantuotą spėliojimą?

Visiškas atsakymas į šį klausimą (tiksliau, šio atsakymo ištikimybės įrodymas) yra toli gražu ne taip paprasta, kaip atrodo iš pirmo žvilgsnio. Tai gali būti parašyta taip: jei (čia [x] – skaitinė dalis x, t.y. didžiausias sveikasis skaičius neviršija x) aiškiai, tada M = sir jei s tada keista M = s – 1. Taip pat įdomu, kad praėjo daugiau nei 20 metų nuo užduoties sukūrimo iki visiško sprendimo!

Akivaizdu, kad pirmą kartą spėjama problema, susijusi su galimybe klaidingai atsakyti, buvo išdėstyta žymiame Vengrijos matematikyje Alfred Renyi 1961 m. Straipsnyje vengrų kalba. Po kelerių metų (savo autobiografijoje "Matematikos nuotykiai"), jis buvo populiarus amerikiečių matematikas Stanislavas Ulamas.

"Hawkinsas ir aš [Filosofas Dovydas Hawkinsas, paskui nuostabios populiariosios knygos" Gamtos kalba "autorius. Pastaba auth] apsvarstė tokią susijusią užduotį: žaidimo "dvidešimt klausimų" variantas. Vienas žmogus mano, kad skaičius yra nuo vieno iki vieno milijono (tai yra tik mažiau nei 220) Kitu asmeniu leidžiama paklausti iki dvidešimt klausimų, kurių kiekvienas pirmasis dalyvis turi atsakyti tik "taip" ar "ne". Akivaizdu, kad numeris gali būti atspėjamas, jei pirmą kartą klausiate: ar šis numeris yra pirmoje milijono pusėje? Kitu klausimu vėl perpus sumažinti gautų skaičių intervalą ir pan. Galiausiai, skaičių galima spėti mažiau nei žurnale.21.000.000 kartų Tarkime dabar dalyvis turi teisę meluoti vieną ar du kartus. Kiek klausimų reikės, kad gautumėte tinkamą atsakymą? Akivaizdu, kad norint atspėti vieną iš 2n numeriai reikalingi daugiau n klausimai, nes apie tai, kada buvo pasakyta melas, nežinoma. Paprastai ši problema neišspręsta. "

1986 m. Andrzej Pelz gavo pilną Ulamo problemos sprendimą dėl vienos klaidos ir dėl dviejų klaidų 1990 m. Po dar 10 metų, matematikai sugebėjo visiškai išspręsti problemą "nuo trijų klaidų". Užduotys su bapietik atskiri konkretūs atvejai buvo išspręstos daugybe klaidų, tačiau iki šiol nebuvo rasti išsamūs sprendimai.

3. Jei jums nereikia optimalaus sprendimo ir minimalaus klausimų skaičiaus, viskas tampa daug lengviau. Taigi, 1991 m. Visų союзной matematinės olimpiadoje buvo pasiūlyta tokia problema (autoriai – A. Andžansas, I. Соловьев, V. Слитинский.)

Tyrėjas parengė liudytojo apklausos planą, užtikrinantį nusikaltimo aptikimą. Jis ketina užduoti klausimus, į kuriuos galima atsakyti tik "taip" arba "ne" (klausimas, kuris bus užduotas, gali priklausyti nuo atsakymų į ankstesnius). Tyrėjas mano, kad visi atsakymai bus teisingi, jis apskaičiavo, kad bet kokiuose atsakymų variantuose bus klausiama ne daugiau kaip 91 klausimą. Įrodykite, kad tyrėjas gali parengti planą, kuriame pateikiami ne daugiau kaip 105 klausimų, užtikrinančių nusikaltimo sprendimą, ir jei į vieną klausimą galima atsakyti neteisingai (bet gali būti, kad visi atsakymai yra teisingi).

Šios problemos sprendimas buvo grindžiamas kita idėja: kaip pakeisti originalų klausimų planą, pridedant jam "kontrolės klausimus". Pirma, tyrėjas pateikia pirmuosius 13 pirminio plano klausimų ir pateikia 14 klausimą "Ar jūs gulėjote ankstesnėse klausimų serijose?".Gavęs atsakymą "ne", jis gali ir toliau paprašyti 12, 11, 10, …, 1 plano klausimų serijos, kartodamas kontrolinį klausimą po kiekvienos serijos (pagalvokite, kodėl atsakymas "ne" į kontrolinį klausimą garantuoja, kad atsakymai į serijos klausimus tikrai buvo tikintis). Jei atsakymas "taip" gaunamas vienam iš kontrolinių klausimų, tada kartojama visa ankstesnė serija, kurioje nereikalaujama jokių kontrolinių klausimų. Jei atsakymas yra "taip", gautas kkontrolės klausimas, tada be pradinio plano reikės paklausti k + (14 – k) = 14 klausimų. Atkreipkite dėmesį į tai, kad atsakymas į kontrolinį klausimą gali būti melas – šiuo atveju atsakymai į pakartotinę seriją bus tokie patys kaip ir pirmas kartas.

Kodėl "plano pakeitimas" nėra optimali strategija ir negarantuoja minimalaus užduotų klausimų skaičiaus? Pavyzdžiui, kadangi pradinė tyrėjo užduotis buvo lygiavertė numanomo skaičiaus spėliojimui nuo 0 iki 291 – 1. Bet tai, kaip mes jau žinome, ne 105, bet tik 98 klausimai yra pakankamai: 298/99 > 298/27 = 291. Vis dėlto olimpiados problemoje siūloma modifikacija padidina plano trukmę nuo N(N – 1) / 2 klausimų ne daugiau kaip N, tai yra, kvadratinės šaknies iš dvigubo originalaus ilgio tvarka. Tai apskritai taip pat nėra taip blogai.

4. Kodėl rimti matematikai atlieka tokias "žaislo" užduotis? Faktas yra tas, kad ši problema yra labai artima klasikinėms teorijos kodavimo problemoms ir yra glaudžiai susijusi su jais (žiūrėkite: Klaidų aptikimas ir taisymas, Hammingo kodas). Iš tiesų, žaidime, kurį mes apibūdinome, Kostya ir Sasha gali iš anksto (kol Kostya pasirenka numatytą numerį), apie klausimą sąrašą (įskaitant susitarimą, į kurį klausimą bus atsakyta antrą kartą, atsakant į pirmąjį klausimą, o kuris iš jų atsakykite "ne" ir panašiai sutinkate su šiais klausimais). Tai reiškia, kad "Kostya" gali tiesiog siųsti Sasha 15 atsakymų seka – arba, jei jums patinka, 15 simbolių seka "0" ir "1". Dėl kiekvienos tokios sekos, Sasha sugebės atspėti ("rekonstruoti") Kostya planų skaičių ir nustatyti atsakymą, į kurį klausimą Kosty buvo klaidinga. Tai yra Hammingo kodas, taisantis vieną klaidą.

R. Hammingo straipsnis "Kodai klaidų aptikimui ir taisymui" buvo paskelbtas 1950 m. (Originalą galima pamatyti, pavyzdžiui, čia, PDF, 3,1 MB). Tuo metu originalūs duomenys į kompiuterius buvo pakraunami perforuotosiomis kortele, o perforacinių kortelių įvesties įrenginiai buvo tokie nepatikimi, kad beveik be storio pakankamai denio negalėjo būti skaitomos be klaidų.Programos, kurioje pateikiama klaida, paleidimas geriausiai atsitrenkė į avariją, po kurio skaičiavimai buvo sustoję, o denis turėjo būti perskaitomas dar kartą, o blogiausiu atveju – visiškai sustabdyti mašiną. Hammingo išradingi kodai leido ne tik aptikti klaidas, bet ir juos automatiškai ištaisyti. Tai buvo tikroji revoliucija!

Nuo to laiko, žinoma, kompiuterinių sistemų patikimumas daug kartų išaugo, tačiau kodų koregavimo klaidos dėl to nepadarė: dabar jos sudaro ryšių protokolų pagrindą. Kai kuriais atvejais ryšių linijos tikrai bus tobulinamos, bet korekcinių kodų poreikis vargu ar niekada nebebus išnyks: klaidos yra amžinas bet kurios žmogaus veiklos palydovas.


Like this post? Please share to your friends:
Parašykite komentarą

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