Gæt hvad jeg er på • Konstantin Knoop • Populære videnskabsopgaver på "Elements" • Matematik

Gæt hvad jeg er i stand til

opgave

Kostya udtænkte et naturligt tal K fra 1 til 2013 og er klar til at svare "ja" eller "nej" til spørgsmål, der tillader sådanne svar. Han har dog ret til at give et fejlagtigt svar ikke mere end én gang (for alle svar).

Sasha ønsker at spørge Kostya ikke mere end 15 spørgsmål, ifølge svarene, som han altid kan gætte det påtænkte nummer på. Hjælp ham til at gøre det.


Tip 1

Normalt i sådanne opgaver forsøger de at spørge "spørgsmål-sammenligninger", det vil sige "Er det rigtigt, at dit nummer er mindre end dette" (eller "mere end dette"). Men der er absolut ikke behov for, at Sasha begrænser sig til bare sådanne spørgsmål. En mere generel type spørgsmål er som følger: Sasha skriver ned et sæt tal (som indeholder nogle af tallene fra 1 til 2013) og spørger Kostya: "Er det rigtigt, at du har planlagt et af disse tal?".


Tip 2

Hvis Kostya ikke kunne fejle, ville 11 spørgsmål være tilstrækkeligt for Sasha (tænk hvorfor). Så, Sasha har fire spørgsmål "på lager", og han bør forsøge at stille spørgsmål, så hvis Kostya svar på et tidspunkt begyndte at modsige hinanden, så kunne man gætte nummeret K På standard måde halverer hver gang antallet af resterende muligheder hver gang.


Tip 3

Forsøg at komme op med sæt til de første 11 spørgsmål af Sasha, så at Sasha efter at have besvaret dem kun kunne forlade kun 12 numre på den "mistænkelige liste" – den ene gav Kostya ikke fejl og endnu et nummer for hver mulig Bone-fejl.


beslutning

Først gør vi det, der blev foreslået i tip 3.

Den nemmeste måde at gøre dette på er at bruge det binære system. Siden 2013 er mindre end 211 = 2048, så indeholder binæroptegnelsen for et af de mulige opfattede tal ikke mere end 11 cifre. Da sifferet i hvert ciffer er 0 eller 1, kan Sasha direkte stille de første spørgsmål: "Er det sandt, at figuren i jeg-m (højre) er det binære nummer for det påtænkte tal 1?"ved at gå igennem alt jeg fra 1 til 11.

Hvis Kostya ikke begår en fejl ved at besvare et af disse spørgsmål, vil Sasha finde ud af alle cifrene i det påtænkte nummer, det vil sige, han vil kende nummeret K (selvom han ikke ved, om Kostya var forkert, kan han ikke konkludere, at han kender det påtænkte nummer). Hvis Kostya gør en fejl ved at besvare et spørgsmål, vil det betyde, at det påtænkte nummer K forskellig fra knoglerne givet svar i en enkelt smule.Men sådan et tal er også kun en – og da fejlen kunne have været lavet i nogen af ​​de 11 bits, er der nøjagtigt 11 mistænkelige tal.

Angiv 12 numre fra den resulterende liste. K0, K1, … , K11 (den første – i mangel af fejl, resten – i tilfælde af en fejl ved besvarelse af det tilsvarende spørgsmål).

Hvordan skal Sasha handle nu? Hvis han spørger det næste spørgsmål (se led 1 om spørgsmålets struktur) om sæt af d tal (alligevel, men ikke inklusive K0; for eksempel K1, … , Kd) og få svaret "ja", kan det betyde en af ​​to ting: En af disse d Tal, enten Kostya var forkert i svaret på dette spørgsmål. Men hvis Kostya var forkert, kunne han kun gætte K0fordi andre muligheder Kd+1, … , K11 betyder, at Kostya allerede var forkert i svaret på nogle af de tidligere spørgsmål, og han kan ikke lave en anden fejltagelse! Så med svaret "ja" forbliver Sasha nøjagtigt d + 1 muligheder, og han forstår, at Kostya var forkert i et af de foregående svar. Siden efter dette spørgsmål har Sasha 3 yderligere spørgsmål tilbage i reserven, vil han kunne gætte det planlagte antal 8 muligheder. Derfor kan vi sætte d + 1 = 8, dvs. d = 7, og overvej kun svaret "nej" på det 12. spørgsmål.

Svaret er "nej" betyder, at Kostya virkelig ikke kunne tænke på tal. K1, … , K7 (ellers ville det være hans anden fejltagelse). Så efter et sådant svar faldt listen over mistænkelige numre til 5: K0, K8, K9, K10, K11. Argumenterer på samme måde som ovenfor, sørger vi for, at det 13. spørgsmål Sasha kan spørge om tallene K8, K9, K10: Hvis svaret er ja, skal han gætte et af de fire tal K0, K8, K9, K10hvad vil det nok være for de to resterende spørgsmål, og i tilfælde af svaret "nej" i listen over mistænkelige forbliver kun K0 og K11.

Nu (det 14. spørgsmål) er det nok at spørge om et tal K11. Som i de situationer, der er analyseret ovenfor, vil svaret "ja" betyde, at Kostya allerede har begået en fejl, og så vil Sasha gætte et af to tal til det sidste 15. spørgsmål. Nå, efter svaret "nej" på det 15. spørgsmål, kan du ikke længere spørge – Sasha kan med det samme konkludere, at Kostya har udtænkt K = K0.


efterskrift

1. Var det muligt at gøre uden brug af et binært system? Ja, selvfølgelig.

Bemærk at i hvert øjeblik af "spillet" mellem Kostya og Sasha er situationen ("spilltilstanden") beskrevet fuldt ud af to tal [en; b]: en – Antallet af numre, som Kostya kunne gætte, forudsat at han endnu ikke havde lavet fejl, men b – Antallet af numre, som Kostya kunne gætte, forudsat at han allerede havde lavet en fejl i et af de foregående svar.Spillet starter fra [2013; 0], men det skal ende i det øjeblik, hvor det "mistænkte" nummer forbliver den eneste – det vil sige enten på staten [1; 0] eller på [0; 1].

Lad Sashas første spørgsmål være relateret til sæt af d numre. Så efter svaret "ja" blev den nye tilstand af spillet [d; 2013 – d], og efter svaret "nej" – [2013 – d; d] (tænk hvorfor dette er så). Hvis Sasha deler sætet 2013-numre i to næsten lige dele, så vil han modtage en af ​​staterne [1007; 1006] og [1006; 1007]. Med det andet spørgsmål kan han dele hver af disse dele i halvdelen – og få enten [504; 1006] eller [503; 1007] (her opnås 1007 tal som følger: først, de 504 tal fra b = 1007, som Sasha inkluderede i hans sæt, og for det andet de 503 tal fra en = 1006, som han ikke inkluderede i sættet – men hvis Kostya lavede en fejl i besvarelsen af ​​dette spørgsmål, kunne disse tal have været gjort til dem).

Fortsætter med at stille spørgsmål på samme måde, vi får konsekvent

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

(eller [503; 1007] → [251; 755], som er mindre end i ovennævnte kæde. Jeg tillod straks mig selv at udelade flere lignende muligheder i denne kæde.)

Således kunne situationen "1 + 11" beskrevet i vores løsning være nået uden at nævne det binære system.Nå, så [1; 11] → ([1; 4] eller [0; 8]) → ([1; 1] eller [0; 4]) → ([1; 0] eller [0; 2]) → [0; 1].

2. Vores løsning viser, at i stedet for tal fra 1 til 2013 kunne Sasha tillade Kostya at gætte tallene fra 0 til 2047, og stadig holde op med at gætte på 15 spørgsmål. Men det efterlader ubesvaret et meget naturligt generaliserende spørgsmål. Lad Sasha få lov til at indstille ikke 15, men N spørgsmål. I hvilket område (fra 0 til M) kan han tillade Kostya at gætte tallene, så disse spørgsmål vil være tilstrækkelige til en garanteret gætte?

Det fulde svar på dette spørgsmål (mere præcist beviset på troværdigheden af ​​dette svar) er langt fra at være så simpelt som det forekommer ved første øjekast. Det kan skrives som dette: hvis (her [x] – heltalets del af nummeret x, dvs. det største heltal ikke overstiger x) klart, da M = sog hvis s mærkeligt da M = s – 1. Det er også interessant, at mere end 20 år er gået fra det øjeblik, hvor opgaven er at få sin komplette løsning!

Tilsyneladende blev gæsende problemet for evnen til at lave fejl i svarene for første gang formuleret af den bemærkelsesværdige ungarske matematiker Alfred Renyi i en artikel fra 1961 på ungarsk. Et par år senere (i sin selvbiografi "The Adventures of Mathematics") blev den populeret af den amerikanske matematiker Stanislav Ulam.

"Hawkins og I [David Hawkins, filosof, senere forfatter til den vidunderlige populærvidenskabelige bog Nature of Nature. Ca.. aut.] overvejede følgende relaterede opgave: En variation på Twenty Questions Game. En person tænker på et tal i området fra en til en million (som er lige under 220). En anden person må stille op til 20 spørgsmål, hvoraf den første deltager kun skal svare "ja" eller "nej". Selvfølgelig kan nummeret gættes, hvis du først spørger: er dette nummer i første halvdel af en million? I det næste spørgsmål igen halverer du det resulterende interval af tal osv. I sidste ende kan nummeret gættes i mindre end log21.000.000 gange Antag nu, at deltageren har ret til at ligge en eller to gange. Hvor mange spørgsmål vil det tage for at få det rigtige svar? Det er klart, at for at gætte en af ​​2n tal krævede mere n spørgsmål, for om, hvornår løgnen blev fortalt, er ukendt. Generelt er dette problem ikke løst. "

Den komplette løsning af Ulam-problemet i tilfælde af en fejl blev modtaget af Andrzej Pelz i 1986 og for to fejl i 1990. Efter yderligere 10 år formåede matematikere helt at løse problemet med "ret til tre fejl." For opgaver med bcirkaKun særskilte sager blev løst af et stort antal fejl, og der er endnu ikke fundet nogen komplette løsninger.

3. Hvis du ikke kræver optimale løsninger og et minimum antal spørgsmål, bliver alt meget lettere. Så i 1991 ved All-Union Mathematical Olympiad blev følgende problem foreslået (forfattere – A. Andzhans, I. Soloviev, V. Slitinsky.)

Undersøgeren kom med en plan for forhør af et vidne, der garanterede påvisning af en forbrydelse. Han vil stille spørgsmål, der kun er mulige til at svare "ja" eller "nej" (spørgsmålet, der bliver stillet, kan afhænge af svarene på de tidligere). Efterforskeren mener, at alle svarene vil være korrekte, beregnede han, at i en hvilken som helst variant af svar kunne der ikke stilles mere end 91 spørgsmål. Bevis at efterforskeren kan lave en plan med højst 105 spørgsmål, der sikrer løsningen af ​​forbrydelsen og i tilfælde af at et spørgsmål kan besvares forkert (men det kan være, at alle svarene er korrekte).

Løsningen på dette problem var baseret på en anden ide: hvordan man ændrer den oprindelige plan af spørgsmål ved at tilføje "kontrol spørgsmål" til det. For det første spørger efterforskeren de første 13 spørgsmål i den oprindelige plan, og spørger derefter det 14. spørgsmål "Løg du i den tidligere række spørgsmål?".Efter at have modtaget svaret "nej" kan han fortsætte med at stille en serie på 12, 11, 10, …, 1 spørgsmål i planen og gentage kontrolspørgsmålet efter hver serie (tænk hvorfor svaret "nej" på kontrolspørgsmålet garanterer, at svarene på seriens spørgsmål virkelig var sandt). Hvis svaret "ja" er modtaget til et af kontrolspørgsmålene, gentages hele den foregående serie uden yderligere spørgsmål til kontrol. Hvis svaret er "ja" er modtaget den kkontrol spørgsmål, så ud over den oprindelige plan bliver nødt til at spørge k + (14 – k) = 14 spørgsmål. Bemærk, at en løgn kunne have været i svaret på kontrolspørgsmålet – i så fald vil svarene på de gentagne serier være nøjagtigt de samme som for første gang.

Hvorfor er "planændring" ikke en optimal strategi og garanterer ikke minimalt antal spørgsmål? For eksempel, fordi den oprindelige opgave for undersøgeren var svarende til at gætte det påtænkte tal fra intervallet fra 0 til 291 – 1. Men for dette, som vi allerede ved, ikke 105, men kun 98 spørgsmål er nok: 298/99 > 298/27 = 291. Ikke desto mindre øger den foreslåede ændring i Olympiad-problemet planens længde fra N(N – 1) / 2 spørgsmål ikke mere end N, det vil sige på rækkefølgen af ​​kvadratroden på to gange den oprindelige længde. Det er generelt ikke så slemt.

4. Hvorfor har seriøse matematikere overhovedet sådanne "legetøjsopgaver"? Faktum er, at dette problem ligger meget tæt på de klassiske problemer med kodningsteori og er nært beslægtet med dem (se: Fejldetektion og korrektion, Hamming Code). I det spil, vi beskrev, kan Kostya og Sasha i forvejen være enige om (før Kostya vælger det påtænkte nummer) om listen over stillede spørgsmål (herunder at aftale hvilket spørgsmål der vil blive bedt om andet, når man svarer ja til det første spørgsmål, og hvilken svar "nej" og ligeledes enig om følgende spørgsmål). Det betyder, at Kostya bare kan sende Sasha en sekvens på 15 svar – eller, hvis du vil, en sekvens på 15 tegn "0" og "1". For hver sådan sekvens vil Sasha kunne gætte ("rekonstruere") antallet af Kostyas planer, og derfor bestemme svaret på hvilket spørgsmål Kostya var forkert. Dette er Hammings kode, der korrigerer en fejl.

R. Hammings artikel "Koder, der opdager og korrigerer fejl" blev udgivet i 1950 (originalen kan ses her, f.eks. PDF, 3,1 MB). På den tid blev de originale data i computere indlæst ved hjælp af stansede kort, og inputenhederne i stansede kort var så upålidelige, at næsten ingen tyk nok dæk kunne læses uden fejl.Lanceringen af ​​programmet, der indeholdt fejlen, led i bedste fald til et nedbrud, hvorefter beregningerne stoppede og dækket skulle læses igen og i værste fald – til et fuldstændigt stop på maskinen. Koderne opfundet af Hamming tillod ikke kun at registrere fejl, men også til automatisk at rette dem. Det var en ægte revolution!

Siden da er selvfølgelig pålideligheden af ​​edb-systemer steget mange gange, men koder korrigerende fejl er ikke blevet mindre populære på grund af dette: de udgør nu grundlaget for kommunikationsprotokoller. Kommunikationslinjer vil sikkert blive forbedret engang, men behovet for korrigerende koder vil næppe forsvinde: Fejl er de evige satellitter af enhver menneskelig aktivitet.


Like this post? Please share to your friends:
Skriv et svar

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