There are 10 people sitting on the vertices of a regular 10-gon. Each of them is a knave or knight. A traveller can choose a point outside the table and ask the question:"What is the distance from me to the nearest knave?" and everyone will give him an answer. What is the minimum amount of question required, for the traveller to determine, for sure, who is knight and who is knave? (assume they can all make exact measurements)
My Attempt:
I claim the minimum is $3$. Obviously $1$ or $2$ is not possible. Now let's prove $3$ is possible.
Proof: Name the people $a_1, a_2,...a_{10}$, and the distance between the traveller and $a_i$ be $s_i$.
Lemma: If a knight is found, then the traveller can figure out everyone by asking one more question. (hopefully no explanation is required)
Choose a point such that it is closest to $a_1$ and not equidistant to any to points. Now there are three cases:
i) no one said $s_1$.
That implies either $a_1$ is knight or everyone is knave. (if $a_1$ is knave, then no one said $s_1$ means none of $a_2,a_3,...,a_{10}$ is knight.) Now, say $a_1,a_2,...,a_i$ said the same distance, (i can be 1) then stand on the perpendicular bisector and ask the second question. Since $a_i$ and $a_{i+1}$ can't be both knights, at least one of them will be knave. If $a_i$ or $a_{i+1}$ answered $s_i$ (or $s_{i+1}$), then that guy will be a knight.
ii) everyone (except $s_1$) answered $s_1$.
That means $a_1$ is knight and everyone else is knave, or vice versa. This can be found out be standing on the perpendicular bisector of $a_1$ and $a_2$ and ask the question. If $a_1$ answered $s_1$ then he is a knight, otherwise everyone else is knight.
iii) not everyone answered $s_1$
Then we can choose two adjacent people, namely $a_i$ and $a_{i+1}$, such that one of them answered $s_1$ and the other didn't. WLOG assume $a_i$ answered $s_1$. Now choose a point on their perpendicular bisector, and ask the second question. Since they can't both be knights, at least one of them will be knave. And it's possible to find out whether $s_i$ a knight or not. One may see that $a_1$ and $a_i$ must be different (i.e. one knight one knave).
Thus, after two rounds, the traveller can always find a knight. And we can use the lemma to finish off the problem.
Is this correct?
Note: I don't see anything special about the number 10. Does it remain true if we replace 10 with 100? (I think so)
Note2: can we generalise this problem? What if the traveller ask the question to one person instead of everyone? Would the answer be 2n+2? (assume there are n people?)
Contrary to what the OP believes, it is possible to do the distinction with 2 questions.
First, I'll exclude the possibility that all the 10 people sitting at the table are knights. That's because in that case the answer to the question is undefined, because no knave exists. If we allow the knights to answer 'undefined' in that case, we must also allow a knave to give that answer, if appropriate.
So if we have a table of 10 knights, all 10 will always answer 'undefined' to any question. If we have a table of 10 knaves, all 10 might also always answer with 'undefined' (which is false, but they are knaves). So those cases cannot be distinguished.
Second, better than what the OP claimed, if you have found a knight A, you have found all knights (and all knaves). That's because everybody who gave a different answer than A must be a knave (because a different answer cannot be correct). Similiarly, everybody who gave the same answer as A must be knight (it is the correct answer, so cannot be a knave).
How does one figure the knight/knaves out?
Choose 2 neighbouring vertices (A and B) of the 10-gon. Choose a point X outside the table on the perpendicular bisector of those 2 points. Ask the people about the nearest knave to X. X has been chosen such that the nearest vertices are A and B (and no other vertex). Let's call this distance betwee X and A (or B) d.
I'll identify the people with the points they are sitting on. So players A and B give answers.
If they give different answers, we can determine everything already. A and B cannot be both knights, as they would have given the same answer. So at least one of them is a knave, so the distance from X to the nearest knave is d. Everybody who gave that answer is a knight, everybody who gave a different answer is a knave.
If they give the same answer, they must both be the same faction (knight or knave). In either option, we can determine the complete knight/knave distribution. If we assume them both to be knights, we know 2 Knights, and can determine everything else as explained above. If we assume both to be knaves, we know the correct answer to the question posed (d), and can equally determine who the knights are.
So we are left with 2 possible configurations of knights/knaves, which we must decide between. Let's call the configuration resulting from assuming both A and B are knights configuration 1, and the other configuration 2.
Since we assumed that 10 knights is impossible, configuration 1 must include knights and knaves. So there must be 2 neighbouring vertices of the 10-gon were people of different faction are sitting. We choose those 2 vertices as A' and B' above and create an X' accordingly and ask about the distance of the nearest knave to X'.
If A' and B' give different answers, we can find out who is who from this answer alone (see above). If they give the same answer, the must belong to the same faction, so we can rule out configuration 1 as impossible, hence configuration 2 must be the correct one.
What needs to be done is to prove that 1 question alone isn't enough. The traveller can choose any point X outside the table to ask about. Let's call the distances from X to the 10 vertices $d_1 \le d_2 \le \ldots d_{10}$.
Case 1: $d_1 < d_2$ So there is a unique nearest vertex A to X. If we assume A is a knight and everybody else a knave, the answers could be $d_2$ from A (forced) and $d_1$ from everybody else (possible lie). If we invert this (A is a knave and everybody else is a knight), they might give the exact same answers. So those 2 configurations are possible with the same answer set.
Case 2: $d_1 = d_2$ In that case, we must have $d_2 < d_3$. If $d_1=d_2=d_3$ were true, X would be the center of circumference of 3 vertices of the 10-gon. This is the symmetry center of the regular 10-gon and this is inside the table, which is forbidden.
Let's call the 2 vertices with the smallest distance to X A and B, resp. If A and B are knights and everybody else a knave, A and B answer $d_3$ (forced) and the knaves may answer $d_1$ (possible lie). If we invert this (A and B knaves, the others are knigths) we might again get the same set of answers. So again those 2 configurations are not distinguishable by the answer set.
The point X is the only choice the traveller has. He has no prior knowledge about the people at the table, so cannot choose X in any way to prematurely exclude one of the configurations when the given answer set arrives.