Uzminiet, kas es esmu uz • Konstantin Knoop • Populāras zinātnes uzdevumi par "Elementi" • Matemātika

Uzminiet, ko es esmu uz augšu

Uzdevums

Kostja ieguva dabisku skaitu K no 1. līdz 2013. gadam un ir gatavs atbildēt "jā" vai "nē" uz jautājumiem, kas pieļauj šādas atbildes. Tomēr viņam ir tiesības sniegt kļūdainu atbildi ne vairāk kā vienu reizi (visām atbildēm).

Sasha vēlas uzdot Kostjojam ne vairāk kā 15 jautājumus, atbilstoši atbildēm, uz kurām viņš vienmēr var uzminēt paredzēto numuru. Palīdzība viņam to darīt.


1. padoms

Parasti šādos uzdevumos viņi mēģina uzdot "jautājumus-salīdzinājumus", tas ir, "Vai ir taisnība, ka jūsu numurs ir mazāks par šo" (vai "vairāk par šo"). Tomēr Sasha nav absolūti nepieciešams aprobežoties tikai ar šādiem jautājumiem. Vispārīgāks jautājumu veids ir šāds: Sasha raksta visus numurus (kas ietver dažus numurus no 1. līdz 2013. gadam) un jautā Kostjē: "Vai tas ir taisnība, ka jūs plānojāt kādu no šiem numuriem?".


2. padoms

Ja Kostjas nevarētu kļūdīties, par Sasha pietiek ar 11 jautājumiem (domāju, kāpēc). Tātad, Sasha ir četri jautājumi "krājumā", un viņam vajadzētu mēģināt uzdot jautājumus, lai, ja kādu laiku Kostjas atbildes sāka pretrunā, tad varēja uzminēt numuru K standarta veidā, katru reizi samazinot atlikušo iespēju skaitu uz pusi.


3. padoms

Mēģiniet nākt klajā ar komplektiem pirmajiem 11 Sasha jautājumiem, lai pēc tam, kad uz tiem atbildētu, Sasha varēja atstāt tikai 12 numurus "aizdomīgā sarakstā" – viens no tiem Kostja nebija nepareizi, un vēl viens cipars par katru iespējamo kaulu kļūdu.


Šķīdums

Vispirms mēs darām to, kas tika ieteikts 3. tipā.

Vieglākais veids, kā to izdarīt, ir izmantot bināro sistēmu. Kopš 2013. gada ir mazāks par 211 = 2048, tad jebkura iespējamā radītā skaitļa binārajā ierakstā ir ne vairāk kā 11 cipari. Tā kā katra cipara cipars ir 0 vai 1, Sasha var tieši uzdot pirmajos jautājumos: "Vai ir taisnība, ka šis skaitlis ir i-m (pa labi) paredzētā numura binārais numurs ir 1?"iet caur visiem i no 1 līdz 11.

Ja Kostja neizdodas kļūdīties, atbildot uz kādu no šiem jautājumiem, tad Sasha uzzina visus paredzētā numura ciparus, proti, viņš uzzina numuru K (lai gan, tā kā viņš nezina, vai Kostja bija nepareizi, viņš nevar secināt, ka viņš zina paredzēto numuru). Ja Kostja pieļāvis kļūdu, atbildot uz kādu jautājumu, tas nozīmēs, ka plānotais numurs K atšķiras no kauliem, kuriem sniegtas atbildes vienā bitu.Bet šis skaitlis ir arī tikai viens – un, tā kā kļūdu var izdarīt kādā no 11 bitiem, ir tieši 11 aizdomīgie skaitļi.

Nosauciet 12 ciparus no iegūta saraksta. K0, K1, … , K11 (pirmais – bez kļūdām, pārējais – ja rodas kļūda, atbildot uz attiecīgo jautājumu).

Kā Sasha jārīkojas tagad? Ja viņš uzdod nākamo jautājumu (sk. Jautājumus struktūru uz mājienu 1) par kopu d cipari (jebkurā gadījumā, bet neieskaitot) K0; piemēram K1, … , Kd) un saņemt atbildi "jā", tas var nozīmēt vienu no divām lietām: vai nu vienu no tām d vai nu Kostja bija kļūdījies atbildē uz šo jautājumu. Bet, ja Kostja būtu nepareizi, viņš varēja tikai uzminēt K0jo citas iespējas Kd+1, … , K11 nozīmē, ka Kostja jau kļūdījās atbildē uz dažiem iepriekšējiem jautājumiem, un viņš nevar izdarīt otru kļūdu! Tātad, ar atbildi "jā", Sasha paliek tieši tāpat d + 1 iespējas, un viņš precīzi saprot, ka vienā no iepriekšējām atbildēm Kostja bija nepareizi. Tā kā pēc šī jautājuma Saša ir rezervējusi vēl 3 jautājumus, viņš varēs uzminēt plānoto skaitu 8 variantu. Tāpēc mēs varam nodot d + 1 = 8, t.i. d = 7 un apsver tikai atbildi "nē" uz 12. jautājumu.

Atbilde ir "nē", ka Kostja patiešām nevarēja iedomāties ciparus. K1, … , K7 (pretējā gadījumā tā būtu viņa otrā kļūda). Tātad pēc šādas atbildes aizdomīgo skaitļu saraksts samazinājās līdz 5: K0, K8, K9, K10, K11. Argumentējot tāpat kā iepriekš, mēs pārliecināmies, ka ar 13. jautājumu Saša var jautāt par skaitļiem K8, K9, K10: ja atbilde ir "jā", viņam būs jāzina viens no četriem numuriem K0, K8, K9, K10kādam tam būs pietiekami, lai divi atlikušie jautājumi tiktu saglabāti tikai gadījumā, ja atbilde "nē" aizdomīgo sarakstā K0 un K11.

Tagad (14. jautājums) ir pietiekami jautāt par vienu numuru K11. Tāpat kā iepriekš analizētajās situācijās, atbilde "jā" nozīmē, ka Kostja jau ir pieļāvusi kļūdu, un pēc tam Sasha uzminēs vienu no diviem numuriem pēdējam, 15. jautājumam. Nu, pēc atbildes "nē" no 15. jautājuma jūs vairs nevarat jautāt – Sasha var uzreiz secināt, ka Kostja ir iecerējusi K = K0.


Pēcvārds

1. Vai tas bija iespējams bez binārās sistēmas izmantošanas? Jā, protams.

Ievērojiet, ka katrā spēļu laikā starp Kostju un Sasha situāciju ("spēles stāvokli") pilnībā raksturo divi skaitļi [a; b]: a – to numuru skaits, kurus Kostja varēja uzminēt, ar nosacījumu, ka viņš vēl nav pieļāvis kļūdas, bet b – to numuru skaits, kurus Kostja varēja uzminēt, ar nosacījumu, ka viņš jau ir pieļāvis kļūdu vienā no iepriekšējām atbildēm.Spēle sākas no [2013; 0], bet tam vajadzētu beigties tajā brīdī, kad "aizdomās turētais" skaitlis paliek vienīgais – tas ir, vai nu stāvoklī [1; 0] vai [0; 1].

Ļaujiet Sasha pirmais jautājums būt saistīts ar komplektu d cipari Pēc tam, kad atbilde bija "jā", jaunā spēles stadija kļuva par [d; 2013 – d] un pēc atbildes "nē" – [2013. – d; d] (domāju, kāpēc tas tā ir). Ja Sasha sadalīs 2013. gada skaitļu kopumu divās gandrīz vienādās daļās, tad viņš saņems vienu no valstīm [1007; 1006] un [1006; 1007]. Ar otro jautājumu viņš var sadalīt katru no šīm daļām pusi un iegūt vai nu [504; 1006] vai [503; 1007] (šeit 1007 cipari iegūti šādi: pirmkārt, tie 504 skaitļi no b = 1007, kuru Sasha iekļāva viņa komplektā, un, otrkārt, šie 503 skaitļi no a = 1006, ko viņš neiekļāva komplektā – bet, ja Kostja pieļāva kļūdu, atbildot uz šo jautājumu, tad šos skaitļus viņiem varēja uzrādīt).

Turpinot uzdot jautājumus tādā pašā veidā, mēs pastāvīgi

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

(vai [503; 1007] → [251; 755], kas ir mazāks nekā iepriekšminētajā ķēdē. Es uzreiz atļāvau izlaist vairākas līdzīgas iespējas šajā ķēdē.)

Tādējādi mūsu risinājumā aprakstītā "1 + 11" situācija varētu tikt sasniegta bez bināra sistēmas pieminēšanas.Nu, tad [1; 11] → ([1; 4] vai [0; 8]) → ([1; 1] vai [0; 4]) → ([1; 0] vai [0; 2]) → [0; 1].

2. Mūsu risinājums parāda, ka, nevis skaitļiem no 1 līdz 2013. gadam, Sasha varētu ļaut Kostjei uzminēt skaitļus no 0 līdz 2047, un joprojām pastāv līdzi par 15 uzdotajiem jautājumiem. Tomēr tas neatstāj jautājumu par ļoti dabisku vispārēju jautājumu. Ļaujiet Sasha noteikt ne 15, bet N jautājumi Kādā diapazonā (no 0 līdz M) Vai viņš var ļaut Kostjam uzminēt numurus, lai šiem jautājumiem pietiktu par garantētu atsaukšanu?

Pilnīga atbilde uz šo jautājumu (precīzāk, šīs atbildes uzticības pierādījums) nav tik vienkārši, kā šķiet pirmajā mirklī. To var rakstīt šādi: ja (šeit [x] – skaitļa vesela skaitļa daļa xt.i., lielākais vesels skaitlis, kas nepārsniedz x) skaidri, pēc tam M = sun ja s tad dīvaini M = s – 1. Ir arī interesanti, ka no problēmas izziņošanas brīža līdz pilnīga risinājuma saņemšanai ir pagājuši vairāk nekā 20 gadi!

Acīmredzot pirmo piemēru Ungārijas ievērojamajā matemātikā Alfrēdam Renī (André Renyi) formulēja domu problēma, kas ļāva kļūdīties atbildēs, ungāru valodā 1961. gadā. Dažus gadus vēlāk (autobiogrāfijā, "Matemātika piedzīvojumi") to popularizēja amerikāņu matemātiķis Stanislavs Ulams.

"Hawkins un es [Dāvids Hokinss, filozofs, vēlāk brīnišķīgās tautas zinātniskās grāmatas" Dabas valoda "autore. Piezīme auth] pārdomāja šādu saistīto uzdevumu: variācijas spēle "Divdesmit jautājumi". Viena persona domā par numuru diapazonā no viena līdz vienam miljonam (kas ir tikai mazāk par 220) Citā personā ir atļauts uzdot ne vairāk kā divdesmit jautājumus, no kuriem katram pirmajam dalībniekam ir jāatbild tikai "jā" vai "nē". Protams, numuru var uzminēt, ja vispirms jautā: vai šis numurs ir miljonā pirmajā pusē? Nākamajā jautājumā atkal, uz pusi jāsamazina iegūtais skaitļu intervāls utt. Galu galā, numuru var uzminēt mazāk nekā žurnālā.21.000.000 reizes Pieņemsim, ka dalībniekam ir tiesības gulēt vienu vai divas reizes. Cik daudz jautājumu būs nepieciešams, lai iegūtu pareizo atbildi? Ir skaidrs, ka, lai uzminētu vienu no 2n cipariem nepieciešams vairāk n Jautājumi, jo par to, kad tika teikts par meliem, nav zināms. Kopumā šī problēma nav atrisināta. "

Pilns Ulam problēmas risinājums vienas kļūdas gadījumā tika saņemts Andrzej Pelz 1986.gadā un divām kļūdām 1990. gadā. Pēc vēl 10 gadiem matemātiķiem izdevās pilnībā atrisināt problēmu "no trim līdz trim kļūdām". Uzdevumiem ar bpartikai atsevišķi konkrēti gadījumi tika atrisināti ar daudzām kļūdām, un vēl nav atrasts pilnīgs risinājums.

3. Ja jums nav nepieciešami optimāli risinājumi un minimālais jautājumu skaits, tad viss kļūst daudz vieglāk. Tātad, 1991. gadā All-Union Mathematical Olympiad piedāvāja šādu problēmu (autori – A. Andžans, I. Solovjevs, V. Slitiņskis.)

Izmeklētājs ir izstrādājis liecinieku nopratināšanas plānu, kas garantē nozieguma atklāšanu. Viņš gatavojas uzdot jautājumus, par kuriem ir iespējams atbildēt tikai "jā" vai "nē" (jautājums, kuru uzdod, var būt atkarīgs no atbildēm uz iepriekšējiem). Pētnieks uzskata, ka visas atbildes būs pareizas, viņš aprēķināja, ka jebkurā atbildes variantā netiks uzdots ne vairāk kā 91 jautājums. Pierādiet, ka pētnieks var izstrādāt plānu ar ne vairāk kā 105 jautājumiem, kas garantē noziedzīgā nodarījuma atrisināšanu, un gadījumā, ja uz vienu jautājumu var atbildēt nepareizi (bet var būt, ka visas atbildes ir pareizi).

Šīs problēmas risinājums bija balstīts uz citu ideju: kā mainīt sākotnējo jautājumu plānu, pievienojot tam "kontroljautājumus". Pirmkārt, izmeklētājs uzdod sākotnējos 13 sākotnējā plāna jautājumus un pēc tam uzdod 14. jautājumu: "Vai jūs gulēja iepriekšējo jautājumu sērijā?".Saņemot atbildi "nē", viņš var turpināt uzdot 12, 11, 10, …, 1 plāna jautājumus, atkārtojot kontroles jautājumu pēc katras sērijas (domājiet, kāpēc atbilde "nē" kontroljautājumam garantē, ka atbildes uz sērijas jautājumiem tiešām bija uzticīgs) Ja atbilde "jā" tiek saņemta uz vienu no kontroljautājumiem, tiek atkārtota visa iepriekšējā sērija, un vairs netiek uzdoti kontroles jautājumi. Ja atbilde ir "jā", tiek saņemta kkontroles jautājums, tad papildus sākotnējam plānam būs jālūdz k + (14 – k) = 14 jautājumi. Ņemiet vērā, ka atbildes uz kontroljautājumu jautājumam varēja būt meli – šajā gadījumā atbildes uz atkārtotām sērijām būs tieši tādas pašas kā pirmajā reizē.

Kāpēc "plāna grozīšana" nav optimāla stratēģija un negarantē minimālu jautājumu skaitu? Piemēram, tā kā sākotnējais pētnieka uzdevums bija līdzvērtīgs domātam, ka plānotais numurs ir no 0 līdz 291 – 1. Bet, kā jau zinām, tas nav 105, bet pietiek tikai 98 jautājumi: 298/99 > 298/27 = 291. Tomēr olimpiādes problēmu ierosinātā izmaiņa palielina plāna ilgumu no N(N – 1) / 2 jautājumi, ne vairāk kā N, tas ir, kvadrātsaknes kārtībā, kas ir divreiz lielāka par sākotnējo garumu. Tas vispār arī nav tik slikti.

4. Kāpēc nopietni matemātiķi dara šādus "rotaļlietu" uzdevumus vispār? Fakts ir tāds, ka šī problēma ir ļoti tuvu kodēšanas teorijas klasiskajām problēmām un ir cieši saistīta ar tiem (sk. Kļūdu noteikšana un korekcija, Hamminga kods). Patiešām, spēlē mēs aprakstījām, Kostja un Sasha var iepriekš (pirms Kostya izvēlas paredzēto numuru) par jautājumu sarakstu (ieskaitot piekrišanu, kurš jautājums tiks uzdots otrs, atbildot ar jā uz pirmo jautājumu un kurš atbildi "nē" un līdzīgi vienojas par sekojošiem jautājumiem). Tas nozīmē, ka Kostja var vienkārši nosūtīt Sasha 15 atbilžu secību – vai, ja vēlaties, 15 rakstzīmju virkne "0" un "1". Katrai šādai secībai Sasha varēs uzminēt ("rekonstruēt") Kostjas plānu skaitu un tādējādi noteikt atbildi, uz kuru jautājumu Kostja kļūdījās. Tas ir Hammija kods, kas labo vienu kļūdu.

R. Hammina raksts "Kodi, kas atklāj un labo kļūdas" tika publicēts 1950. gadā (oriģinālu var redzēt, piemēram, šeit, PDF 3,1 MB). Tajā laikā sākotnējie dati datoros tika ielādēti ar perforētām kartēm, un perforatoru karšu ievades ierīces bija tik neuzticamas, ka gandrīz bez biezas klāja nevarēja nolasīt bez kļūdām.Programmas, kas satur šo kļūdu, uzsākšana labākajā gadījumā izraisīja avāriju, pēc kuras aprēķini tika pārtraukti un klāja vajadzēja atkal lasīt, un sliktākajā gadījumā – pilnībā apturēt mašīnu. Hamminga izdomātie kodi ļāva ne tikai atklāt kļūdas, bet arī automātiski tos labot. Tā bija īsta revolūcija!

Kopš tā laika, protams, datorsistēmu uzticamība ir daudzkārt palielinājusies, tomēr kodi, kas koriģē kļūdas, vēlāk nav kļuvuši tik populāri: tagad tie veido saziņas protokolu pamatu. Sakaru līnijas, protams, dažkārt uzlabosies, bet korektīvo kodu nepieciešamība gandrīz nekad nebūs pazudusi: kļūdas ir ikviens cilvēka darbības mūžīgais satelīts.


Like this post? Please share to your friends:
Atbildēt

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