U selu živi [latex]n[/latex] stanovnika, a svaki od njih je vitez (koji uvijek govori istinu) ili sluga (koji uvijek laže). Broj vitezova veći je od broja sluga i to vam je poznato. Vi možete upitati bilo kojeg stanovnika: “je li osoba [latex]X[/latex] vitez ili sluga?”, za bilo kojeg drugog stanovnika [latex]X[/latex]. Odredite minimalan ukupan broj postavljenih pitanja potreban da sa sigurnošću odredite tko je vitez, a tko sluga.
5 thoughts on “Seoska posla”
Comments are closed.
ja znam u n-1 korak, jel moze bolje?
Ne vjerujem da može bolje, premda to još nisam uspio dokazati. Kombinatoričari, imate izazov.
Ja isto imam u n-1 najbolje…
Update: upravo sam dokazao da se ne može bolje od [latex]n-1[/latex] za neparan [latex]n[/latex]. Napisat ću taj dokaz ako više ništa ne smislim.
Evo na Mathlinksu je izašlo rješenje: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=390794