U selu živi
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
vitez ili sluga?", za bilo kojeg drugog stanovnika
. Odredite minimalan ukupan broj postavljenih pitanja potreban da sa sigurnošću odredite tko je vitez, a tko sluga.
![](https://mnm.hr/wp-content/plugins/latex/cache/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif)
![](https://mnm.hr/wp-content/plugins/latex/cache/tex_02129bb861061d1a052c592e2dc6b383.gif)
![](https://mnm.hr/wp-content/plugins/latex/cache/tex_02129bb861061d1a052c592e2dc6b383.gif)
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
za neparan
. 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