Problem statement: In a room there are n people, each labelled with a unique number between 1 and n. A person may either be a knight or a spy. Knights always tell the truth, while spies may lie or tell the truth as they see fit. Each person in the room knows the identity of everyone else. Apart from this, all that is known is that strictly more knights than spies are present. Asking only questions of the form: ‘Person i, what is the identity of person j?’, what is the least number of questions that will guarantee to find the true identities of all n people?
I am reading the work of Mark Wildon, which you can find here: http://www.ma.rhul.ac.uk/~uvah099/Maths/ksDRev2.pdf
What troubles me is step 1 of the Spider Interrogation Method he uses. I understand a) and that every time we are in that case at least half of the 2a examined people (the fixed one and the people we ask about him) are spies and after that they are discarded. We fix another one and repeat the procedure. Intuitively this way the spies will be discarded before the knights (because they are less than the knights) and after that only knights remain. This way we can identify the first knight. I cannot undrstand b). Any further explanation of step 1 is greatly appreciated. Thank you for your time!
Case $b)$ can be reached without all spies having been discarded. The reason that it’s enough when $\ell$ people have said the candidate is a knight, and it doesn’t require $\ell+1$ people, is that we don’t ask the candidate herself – so if the candidate is a spy, then there are at most $\ell-1$ spies among the people we ask, so if $\ell$ of them have said that she’s a knight, then it must be true.