User Tools

Site Tools


pow:problem1f21

Problem 1 (due Monday, September 13)

In certain village there are 333 voters. Each voter belongs to one of two parties: knights or knaves. Knaves sometimes lie and sometimes tell the truth, while knights always tell the truth. Every voter knows the party affiliation of all voters and there are more knights than knaves. You, the mathematician, arrive to the village with the task to meet a knight. You can ask each voter the following question about any voter: is she/he a knight? Find a knight by asking as few questions as you can.

Only two solutions were received: one containing a partial solution with some useful observations and one complete with the most efficient method we know (we do not know if a better procedure is possible). For details see the following link Solution.

pow/problem1f21.txt · Last modified: 2021/09/16 00:16 by nye