Do you know where your number ranks among your peers?

Question

A group of logicians each have a number written on their foreheads, visible to all but themself. One day, a meta-logician comes by and remarks, "I see all the numbers are distinct natural numbers." She then proceeds to repeatedly ask them the question:

Do you know where your number ranks among your peers?

And each time, the logicians have to truthfully answer yes or no simultaneously. There's no other communication.

True or false: Everybody eventually knows their rank, regardless of the size of the group or the combination of their numbers.

Answer 1

I tried this problem without looking at the answers first. But I came to a different conclusion to the other answers. So I'm posting another answer here.

The answer to the question is

False. In some cases, some of the logicians will never discover their rank

We can demonstrate this answer using the following reasoning.

To show that the answer is false it suffices to show a single example in which one logician is unable to determine their rank.

We will suppose that there are four logicians: Alice, Bob, Charles and Debbie. Their hats state [1, 2, 4, 5] in order. We suppose that 0 is not a natural number. Note that the second largest number is 4. We claim that Alice cannot deduce her rank regardless of the number of rounds of questioning.

In round 1 none of the logicians will see [1, 2, 3] so all four logicians will answer no.

In round 2, Debbie will see [1, 2, 4]. Since she knows from round 1 that her hat is not 3, she will conclude that it must be larger than 4, so she will answer yes. As explained in Especially Lime's answer the other three logicians will not be able to deduce their rank, and so will reply no. At the end of round 2 all of the logicians will now know, based on Debbie's answer that 4 is the value on the second largest hat.

In round 3 Debbie will still know her rank and will say yes again. Charles cannot see the 4, and so can deduce that he must be wearing it. So he will know he is ranked second and so will say yes. Bob will see [1, 4, 5] and know that his number must be less than 4. So Bob will conclude his hat must be 2 or 3, and in either case his rank must be third. So Bob will also say yes. We will come back to Alice in a little bit.

Now consider a different scenario, in which Alice's hat is 3 not 1, but nothing else is changed. Observe that all four logicians will give the same responses in rounds 1 and 2 as in the previous scenario. In round 3, Debbie and Charles are in the same situation as before and so will also say yes again. For this scenario in round 3 Bob will know that his number is less than 4 and cannot be 3 (since he can see 3). So Bob will know that he must have 1 or 2 and in either case he must be ranked last. So Bob will say yes in round 3.

Now consider Alice's perspective. In both scenarios Alice will see the same hats [2, 4, 5] and in both scenarios the other three logicians will give the same answers in the first three rounds. The other logicians will continue to say yes in every subsequent round. So the two scenarios will look totally identical to Alice and she cannot distinguish them. But in the first scenario Alice is ranked last and in the second one she is ranked second to last. So Alice will never be able to determine her ranking. She will have to continue to say no for all subsequent rounds.

The flaw in the reasoning given for the other answers is that

The other answers all correctly prove that after sufficient rounds one of the logicians must be able to deduce their rank. But they then assert that by "repeating" or "restarting" the others will eventually be able to deduce their ranks. But the question says that the logicians must answer truthfully. As soon as a logician determines their rank, possibly via a shortcut, then the logician must say yes. Bob has two different ways of immediately determining his status once he knows that '4' is the second largest hat number. But Alice cannot determine which way Bob utilised. If the logicians were only allowed to use the knowledge that Debbie has the highest number, but forgot what number it was then they would eventually be able to deduce all of the rankings.

Answer 2

I'll assume that everyone has the same definition of "natural number", which for ease of notation doesn't include $0$, and this is common knowledge. This is not true in practice.

To explain what's going on in more detail (and correct the actual times at which people say "yes"):

Say there are $M$ logicians, and let $S$ be the second-highest number. If $S=M-1$, then someone can see $1,\ldots, M-1$ and will immediately know they have the largest. So after one round of all "no", this can't be the case. Now if $S=M$, someone will see nothing higher than $M$ and will know they can't have the missing number. So after two rounds of all "no", everyone knows that $S\geq M+1$. Then if $S=M+1$, someone will see nothing higher than $M+1$ and deduce that they have the highest, and so on.

So after $S+1-M$ rounds of all "no", whoever has the highest number will say "yes". Now the process restarts and the remaining logicians deduce based on the second-highest number remaining. (Until there is only one logician left who knows they have the lowest number.)

Answer 3

This is no secret: In the group of M logicians, there is a highest number N and there is a logician H who has that highest number.

All logicians except H, see that number N, so for sure they have to say "No" at least until the meta-logician has asked the Nth time, because they don't know themselves whether they have a higher number.

Logician H only sees lower numbers than his/her own number (which is N, but he/she doesn't know yet). So, if the meta-logician has asked the (N-1)th time and still everybody has said "No", logician H knows that he/she has the highest number. And if the meta-logician asks the Nth time, logician H will say "Yes".

The "game" starts over with a group of M-1 people (logician H will be ignored and there will be a new logician H).

So, the answer is yes: at some point everybody will know his/her rank. If I am not wrong, this would require asking something like N*(N+1)/2 times.

Answer 4

The answer is...

True

This is because...

...the moment that one(1) answers "Yes", it can only be because they know they are the top ranked. These are then removed from consideration, and we can start rank the remaining logicians. Repeat until there is only one left.

Here is how to do it...

There are M logicians. The highest number anyone of them has is N.

Let us start with the assumption that...

N = M

If this is true, then when asked...

...one logician will see that everyone else has numbers that are lower than N, meaning their number must be N or higher, which makes them answer "Yes".

Now everybody else know that this logician is top ranked. This logician is therefore removed from consideration.

Hence, we have a new set of logicians, and can start from the top again.

Repeat until there is only one left.

But if everyone answers...

"No", this means that N cannot be M, and so we increase N by 1.

Now we ask again. If anyone says...

"Yes", this can only be because they see a combination of numbers that were all less than N. Again, they know their number is N or higher, they are top ranked and say "Yes".

They are removed from further consideration. We can start over, with a new set of logicians.

If everyone says "No", increase N by one, and so on.

---

So, the answer is

True, everyone will — eventually — know their rank among the others.

---

Note

In some corner cases, this can go a lot faster, and several people can say "yes" at the same time. For example, if numbers are 1 to M, then on the first run, the one with the number M will say "Yes", and on the second run, everyone else will say "Yes".