16
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The numbers don't have to be consecutive... right? Though, from intuition, I don't think that really matters for the solution 🤔 $\endgroup$ Jun 6, 2023 at 11:29
  • 2
    $\begingroup$ @ThePuzzler-orratherAPuzzler No, they don't have to be consecutive. $\endgroup$
    – Eric
    Jun 6, 2023 at 11:35
  • 1
    $\begingroup$ Ah, I see. Guessing the answer is no (though, maybe I haven't thought far enough!) $\endgroup$ Jun 6, 2023 at 12:02

4 Answers 4

22
+100
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ +1 Excellent analysis $\endgroup$
    – Eric
    Jun 14, 2023 at 2:50
  • $\begingroup$ Congratulations! You nailed it. $\endgroup$
    – Eric
    Jun 14, 2023 at 8:36
  • $\begingroup$ "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." How? If they forgot Debbie's number, that number could be 5, too. Therer's no way to deduce from there. $\endgroup$
    – Eric
    Jun 14, 2023 at 9:31
  • $\begingroup$ Clever example! $\endgroup$
    – justhalf
    Jun 19, 2023 at 6:07
  • 1
    $\begingroup$ @Retudin: This is a [meta-knowledge] puzzle scenario. In your example, everyone knows immediately the second highest number is at least 4, but not everyone knows that everyone knows that. The level of meta-knowledge can get very nested. $\endgroup$
    – tehtmi
    Jun 22, 2023 at 1:25
6
$\begingroup$

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.)

$\endgroup$
11
  • $\begingroup$ I think your conclusion should say "After S + 1 - M rounds...". Since the lower bound for S is M-1 we want this to start on 0, not -1. $\endgroup$ Jun 6, 2023 at 14:30
  • $\begingroup$ @GoblinGuide yes, thanks! $\endgroup$ Jun 6, 2023 at 14:32
  • $\begingroup$ After the first yes, there's no need to restart the process again. Everybody knows what S is. The person with S on his forehead then knows his number is S: because he looks around and sees no S, therefore knows his number must be S, and will say yes the next round. $\endgroup$
    – Eric
    Jun 6, 2023 at 15:34
  • $\begingroup$ @Eric The process still restart after the first yes for everyone except the highest two numbers, right? During the round after the first yes, they will technically ignore the second highest number, and use the same reasoning as in this answer, but for the fourth highest number. $\endgroup$
    – justhalf
    Jun 6, 2023 at 16:41
  • 1
    $\begingroup$ Someone has given a counter-example, this answer is not correct. $\endgroup$
    – Eric
    Jun 14, 2023 at 9:33
3
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ Wait... If logician $H$ doesn't know what $N$ is, how would they know when the meta-logician has asked $N-1$ times? Am I missing something? 🤔 $\endgroup$ Jun 6, 2023 at 14:00
  • 1
    $\begingroup$ @ThePuzzler-orratherAPuzzler they don't. But once the meta-logician has asked more times than any number they see, they know theirs is the highest number (but not what it is). $\endgroup$ Jun 6, 2023 at 14:04
  • $\begingroup$ @EspeciallyLime right! So, since everyone has to answer truthfully, $H$ has to keep saying no. However, that means when the meta-logician has asked $N$ times, all the others (except $H$) would think they have the highest number... right? $\endgroup$ Jun 6, 2023 at 14:12
  • 1
    $\begingroup$ @ThePuzzler-orratherAPuzzler yes, the details here aren't quite right, but it does eventually stop. I've posted an answer explaining what the actual point where you can deduce you have the highest is. $\endgroup$ Jun 6, 2023 at 14:19
  • 1
    $\begingroup$ @Ivo you're absolutely right. H knows it earlier that he has the highest number. And as @Eric stated in a comment to another answer, everybody will then know what the second highest number S (or you call it X) is. $\endgroup$
    – theozh
    Jun 7, 2023 at 6:33
3
$\begingroup$

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".

$\endgroup$
5
  • $\begingroup$ "it can only be because they know they are the top ranked." although generally true, if the numbers are 1 to N, in the first round, the highest will say "yes", and in the second round everyone else will say "yes". $\endgroup$
    – justhalf
    Jun 6, 2023 at 16:44
  • $\begingroup$ @justhalf True, there are some corner cases that shortcuts us to the finish. Post edited to more accurately reflect the common case. $\endgroup$
    – MichaelK
    Jun 6, 2023 at 16:59
  • 2
    $\begingroup$ I have to click my mouse 13 times in order to read your solution $\endgroup$ Jun 6, 2023 at 22:38
  • 3
    $\begingroup$ @AndrewP. Yes. I reveal thing gradually, so that someone that wants to try to work it out for themselves can get hints without getting the full Monty on the first click. $\endgroup$
    – MichaelK
    Jun 6, 2023 at 22:46
  • 3
    $\begingroup$ Oh I see. I like it! $\endgroup$ Jun 7, 2023 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.