Brigita ir iedomājusies naturālu skaitli, kas nepārsniedz \(60\). Indra drīkst Brigitai uzdot jautājumus, uz kuriem atbilde ir "jā" vai "nē". Kā, uzdodot sešus jautājumus, Indra noteikti var uzzināt Brigitas iedomāto skaitli?
Indra domās sadala skaitļus divos vienāda apjoma intervālos: \([1; 30]\) un \([31; 60]\). Pirmais jautājums: "Vai iedomātais skaitlis pieder intervālam \([1; 30]\) ?"
Ja atbilde uz pirmo jautājumu ir "jā", tad nākamais jautājums jāuzdod par divreiz mazāku intervālu nekā tas, par kuru jau zināms, ka tajā atrodas iedomātais skaitlis, tas ir, "Vai iedomātais skaitlis pieder intervālam \([1; 15]\)?"
Ja atbilde uz pirmo jautājumu ir "nē", tad iedomātais skaitlis atrodas intervālā \([31; 60]\) un nākamais jautājums būtu jāuzdod par divreiz mazāku intervālu \([31; 45]\).
Līdzīgi Indrai jārīkojas arī turpmākajos jautājumos, tas ir, atkarībā no atbildes vienmēr jāaplūko tas intervāls, kas satur iedomāto skaitli, un šis intervāls jāsadala divos pēc apjoma vienādos intervālos (katrā no abiem intervāliem ir vai nu \(n\) skaitļi, vai arī vienā ir \(n\), bet otrā \(n+1\) skaitlis). (Skat., piemēram, 34.att., kurā parādīts, kāda apjoma intervālos notiek dalīšana.)
Šādi rīkojoties, ar sešiem jautājumiem Indra noteikti var uzzināt Brigitas iedomāto skaitli.
Piezīme. Atrisinājums balstīts uz "skaldi un valdi" algoritmu.
Tā kā Brigitas iedomātais skaitlis nepārsniedz \(60\), tad to binārajā skaitīšanas sistēmā var uzrakstīt izmantojot ne vairāk kā \(6\) ciparus. Indrai jāuzdod jautājums par katru skaitļa ciparu:
\(\ldots \)
Tā kā skaitļa binārajā pierakstā tiek izmantoti tikai cipari \(0\) un \(1\), tad šādi rīkojoties, ar sešiem jautājumiem Indra noteikti var uzzināt Brigitas iedomāto skaitli.
