8
$\begingroup$

12 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 12 logicians have to truthfully answer yes or no simultaneously. There's no other communication.

In the worst case scenario, how many logcians will always remain uncertain about their ranks, saying no forever?


Related to Do you know where your number ranks among your peers?.

$\endgroup$

2 Answers 2

1
$\begingroup$

The worst case is 12, everyone says no forever.

If there is one number > 11, that numbers sees 1..11 and says yes since it knows it is highest; all others also say yes starting round 2, since this is the only case where someone can say yes in round 1.

If there are 3 or more numbers >11, everyone says no in round 1 and no one gains any information! After all: Everyone knows beforehand, whatever their number is, that the second highest number is >11. This is the worst case.

If there are exactly 2 numbers >11, those 2 do not know beforehand if the high number they see does not say yes in round 1. If they say no both get additional information, namely that their number is 12+. A no in the second round will similarly give both extra information (their number is 13+), etc. This will eventually lead to 11 or 12 persons saying yes, like in the answers to the linked question.
However this is not the worst case; and cannot be generalized to 3+ numbers >11!

$\endgroup$
4
  • 2
    $\begingroup$ I don't believe this is correct. Take the 3 numbers > 11 case. Persons A, B and C have the highest, the second highest and the third highest numbers respectively. Person A knows that if they have a number <= 11 then by round N person B is going to claim the highest number. When round N comes around without B claiming such A now knows that A also has a number > 11. Furthermore, A knows that they have the highest number, otherwise B would have been able to follow the same logic on a previous round. $\endgroup$ Jun 20, 2023 at 23:26
  • $\begingroup$ You are correct. e.g. with 3 numbers 10,20,100: Round 10, Person 20 and 100 will know they do not have number 1 or 2. I dont know yet when/if ever person 100 knows not to be 3, but the problem is more complicated than I thought (and the incorrect 'yes' answers in the linked problem suggest ) $\endgroup$
    – Retudin
    Jun 21, 2023 at 8:26
  • $\begingroup$ The answer by Especially Lime in the linked problem is correct on the highest number person being the first to know their rank after S+1-M rounds of all no's. So in your example, 100 will know their rank after 18 rounds. $\endgroup$
    – Eric
    Jun 21, 2023 at 16:21
  • $\begingroup$ After reconsidering my and the other answers: I do not think so, I will comment there. $\endgroup$
    – Retudin
    Jun 21, 2023 at 18:47
1
$\begingroup$

We know from the link in the question that when there're 4 logicians, it is possible for one of them to remain agnostic about their rank forever.

For 2 logicians to remain agnostic forever, you need at least

8 logicians, according to this analysis from reddit, which I think is correct.

The general question of how many agnostic logicians there can be in a group of $N(N\gt 8)$ is unknown.

$\endgroup$

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.