2014 2015 2016 2017 2018

Rask vagį

Taškai: 6

O, ne! Šiandien iš muziejaus buvo pavogtas ypatingas mėlynasis deimantas: vagis vietoj jo paliko pigią žalios spalvos deimanto imitaciją.

Šiandien deimanto ekspoziciją aplankė 2000 žmonių. Jie buvo įėję į deimanto ekspozicijos kambarį vienas po kito. Inspektorius Bebras privalo rasti vagį, todėl apklausia kai kuriuos iš šių lankytojų. Jis turi 2000 ekspoziciją aplankiusių žmonių sąrašą, sudarytą ta eile, kuria jie ėjo į deimanto kambarį. Inspektorius klausia kiekvieno lankytojo to paties klausimo: Jūsų matytas deimantas buvo žalios ar mėlynos spalvos? Visi turėtų atsakyti teisingai, išskyrus vagį, kuris sakys, kad deimantas jau buvo žalias.
Inspektorius Bebras yra labai protingas. Jis naudos strategiją, kad žmonių, kuriuos reikia apklausti, skaičius būtų kuo mažesnis. Kurį iš pateiktų teiginių jis gali suformuluoti nemeluodamas?

A. Garantuoju, kad rasiu vagį apklausęs mažiau kaip 20 žmonių.

B. Neužteks apklausti 20 žmonių (nebent man pasiseks), bet tikrai pavyks atlikti darbą apklausus mažiau kaip 200 lankytojų.

C. Tai sudėtingas darbas: man reikės apklausti ne mažiau kaip 200 žmonių, gali būti, kad net 1999.

D. Nieko negaliu prognozuoti. Jei nepasiseks, man gali tekti apklausti kiekvieną lankytoją.

Paaiškinimas

Aibės kartotinio dalijimo per pusę technika yra labai populiari informatikoje. Vienas žinomiausių pavyzdžių – dvejetainė paieška, kuria ieškoma tam tikro įrašo sutvarkytame sąraše.
Mūsų atveju, ieškomas pirmas žalias elementas mėlynų ir žalių elementų sąraše, kur visi mėlyni elementai yra sąrašo pradžioje. Faktas, kad sąraše yra vagis, kuris meluos atsakydamas į klausimą, mums leidžia ieškoti spalvos pasikeitimo. Atkreipkime dėmesį, kad problema būtų neišsprendžiama, jei iš anksto nežinotume, kokios spalvos deimanto imitacija vagis pakeitė originalų deimantą.

Reikšminiai žodžiai: dvejetainė paieška.

Atsakymas

Inspektorius Bebras turės apklausti tik nedidelę dalį lankytojų, kartodamas tokius žingsnius:

Sunumeruoti lankytojus nuo 1 iki 2000 ta eile, kuria jie buvo įėję į kambarį.

  • Inspektorius Bebras pirma prašo lankytoją Nr. 1000 atsakyti, kokios spalvos buvo deimantas, kai šis jį matė.
  • Jei jis atsako, kad mėlynas, daroma išvada, kad vagis atėjo po 1000-ojo lankytojo ir turi eilės numerį nuo 1001 iki 2000.
  • Jei jis atsako, kad deimantas buvo žalias, tai vagis turės eilės numerį nuo 1 iki 1000. (Atkreipkite dėmesį, kad deimantą galėjo pavogti lankytojas, kurio numeris 1000!).

Abiem atvejais potencialių vagių skaičius sumažinamas nuo 2000 iki 1000, kitaip tariant, per pusę.

Tada inspektorius Bebras užduoda klausimą asmeniui, kuris yra likusio sąrašo viduryje (t. y. pirmu atveju – numeris 1500, antru atveju – numeris 500). Tokiu būdu inspektorius vėl galės padalyti įtariamųjų sąrašą per pusę.

Taip skaičiuodamas, inspektorius galės sumažinti įtariamųjų skaičių iki 500, 250, 125, 63, 32, 16, 8, 4 ir 2. Kai liks 2 įtariamieji, jis turės paklausti pirmojo. Jei jis atsakys „žalias“, jis ir yra vagis. Priešingu atveju vagis yra kitas įtariamasis. Taip inspektorius ras deimantą pavogusį asmenį apklausęs tik 11 žmonių.