Prisoners and warden game, again?

Question

Source:

Adapted from IOI 2022: Prison Challenge

---

There are 100 prisoners in a prison. As usual, there is a warden who loves to play games, hence offers the prisoners a chance to free themselves.

He says

There is a room with a whiteboard, initially having the number 0 on it. There are also two boxes labelled A and B respectively, each with an integer from 1 to 50000 written inside it. The numbers in the two boxes are different.

You may discuss strategies among yourself before the game starts, after that no more discussions are allowed. You must decide an integer k which I will explain.

I will lead you into the room one by one in a certain order. You do not know the number of prisoners who visited the room before you. You are allowed to choose one of the boxes, and see the number inside. You may either choose to choose a box and declare that a box has a larger integer, or change the integer on the whiteboard to a positive integer less than or equal to k (you may change it to the same integer). If you choose the former, you win if you are correct, and lose if you are wrong. Note that you cannot infinitely stall because you will also lose if none of you attempts to choose a box and declare its number is larger.

I will run the game a lot of times so that you cannot use any randomized strategy. If you lose even once, you are all executed. If you win all of them, you are free. However, the k you choose must be as small as possible. If not, I will execute you all anyways.

What is the smallest possible value of k and the strategy of the prisoners?

Answer 1

Solution with k=26. Thanks Florian F and xnor for valuable input and an insight derived from retudin's answer.

I'll first introduce a basic version of the strategy lets us solve the problem with k=30, and is much more plausible that the prisoners would be able to execute it. Each prisoner will convert the numbers they see in the boxes to ternary, and communicate the digits one at a time to each other. Only 10 prisoners of the 100 are needed for this strategy.

If zero is on the board, the prisoner looks in box A and writes down 1 + the value of the first digit of the ternary representation of the number he sees.

From there, Let the current board number be x. A prisoner entering the room extracts two pieces of info from it. The ternary digit of interest is the $\lceil x/3\rceil$th, and the value of that digit that is being communicated is x-1 mod 3. If the digit is odd, the prisoner looks in box B; if it's even, he looks in box A. He compares the digit he sees with that communicated. If they differ, he states which box has the larger number, otherwise he passes along the value of the next digit of the number he saw to the next prisoner by writing down $1 + (3*digit) + value$

In the worst case scenario, the tenth prisoner writes a 30, and then the next prisoner will certainly know which box is larger. But we observe that there's no reason to write 30, since that prisoner will know that his box is larger. The same is true for 28, it must be smaller than the other box, which would let us get away with only k=28 for this basic strategy.

But in fact, at every step of the process, if a prisoner sees the lowest or highest possible value within the set of current possibilities, he can immediately answer the question and end the game. We use this insight to get a slightly smaller k of 26.

There is no longer a clean way to define the groups (in the first strategy, each group was a ternary digit dividing the numbers into 3 group), but we'll assume these prisoners are brilliant mathematicians and can figure out the exact group boundaries. At each step, including the first, the prisoners will first check if the number in the box they look in is the highest or lowest possible of the range, then they divide the remaining numbers into groups of size depending on what digit they are on. The optimal group divisions are [3, 3, 3, 3, 3, 3, 3, 2, 2, 1]. The 1 seems funny, but really it just communicates that another round of trimming the top and bottom is all that's needed.

As a brief example of the basic strategy:

Suppose the number are 49,000 in box A and 44,444 in box B. In ternary, these are 2111012211 and 2020222002 respectively.

The first prisoner goes in, he sees 0, which means he checks box A and considers only the first digit of its ternary representation, which is 2. He writes 3 on the board, which is the 1 + the digit.

The next prisoner see 3 on the board. This isn't 0, so he computes $\lceil3/3\rceil = 1$ and 3-1 mod 3 = 2. The digit, 1, is odd so he's looking in box B. He checks the first digit against the value 2, and sees they are equal. Now, for the next prisoner, he communicates that the 2nd digit of the number he sees is 0 by writing $1 + (3*digit) + value = 1 + (3*1) + 0 = 4$

The next prisoner sees 4. This isn't 0, so he computes $\lceil4/3\rceil = 2$ and 4-1 mod 3 = 0. The digit, 2, is even so he's looking in box A. He sees that the 2nd digit is 1. This is greater than the 0 that was communication, so he correctly announces that Box A has the bigger number.

For the "advanced" strategy:

The first prisoner sees a 0 and looks in box A. If it contains 1 or 50,000, he gives the answer. He divides the remaining 49,998 numbers into 3 groups: 2 to 16667, 16668 to 33333, and 33334 to 49998, and communicates which group with the number 1, 2, or 3 [He'll write 3 for the 49,000v44,444 case above].

The next prisoner sees that number and looks in box B. He notes that 44,444 is in group three, so the game goes on. He removes the highest and lowest from the range to get 33335 to 49997, and divides that into 3 groups as best he can: 33335 to 38888, 38889 to 44442, and 44443 to 49997. These don't divide perfectly evenly, but our brilliant prisoners have a consistent scheme worked out. They also have memorized a massive lookup table for figuring out the current group range. In any case, he writes down 6 since we're in the second digit, third group.

Back to box A for prisoner #3, also in group 3, so we get a 9 for prisoner #4 who sees that the number in box B, is in a lower group and so the game ends. If the numbers were closer, we might have gone to the 8th prisoner, at which point we'd begin dividing into 2 groups rather than three. If it makes it to the penultimate prisoner, he'll have 4 numbers in the range. He'll just write 26 if it's in one of the middle 2 numbers, and the final prisoner will have a range of 2 and know which is bigger once he looks in.

Answer 2

Note: the methodology is (almost) the same as kagamis's answer (and partly reused). However, backwards reasoning seems useful to mention; and makes it clear the number can be 1 lower thus this answer results in N=27

We can send partial information about the number, most significant info first.
After that is checked we only need to remember that it is checked. An trinary method works most efficient, since we then need 3 numbers to reduce the solution space by a factor 3. However, we can be a bit more efficient by calling the larger number early.

Reasoning backwards will tell us:
The last participating prisoner can end it if the group size is 2
- 0 (+group offset) is lowest
- 1 is highest
The second last can, if willing to send trinary data, handle up to group size 8
- 0 (+group offset) is lowest
- 1,2: make a unique number e.g.1
- 3,4: make number 2
- 5,6: make number 3
- 7 is highest
The third last can, if willing to send trinary data, handle up to group size 26
- 0 (+group offset) is lowest
- 1..8: make number 4
- 9..16: make number 5
- 17..24: make number 6
- 25 is highest
Earlier ones can handle group size 80 242 728 2186 6560 19682 59048

59048 is not large enough to change a trinary group into a binary one, so numbers up to 27 are needed.
59048 is large enough to keep things simple: We only need the last 2 to call out; the optimizations like 24-26 are not needed.

e.g.
Looking at the 8 (if needed zero-padded) trinary digits of A/8 or B/8:
if N=0 the turn is 1
- Look at the first trinary digit A1 of A make N = A1+25
if N=25-27 the turn is 2
Compare the first trinary digit B1 of B, with A1 (N-25).
If equal, look at the second trinary digit B2 of B make N = B2+22.
Else declare the largest.
...
if N=4-6 the turn is 9
Compare the 8th trinary digit A8 of A/8, with B8 (N-4).
If equal, look at A mod 8.
- if 0 A is smaller
- if 1,2 make N = 1
- if 3,4 make N = 2
- if 5,6 make N = 3
- if 7 A is larger
Else declare the largest.
if N=1-3 the turn is 10
Compare B mod 8 with 2xN (if and only if B mode 8 is smaller, B is smallest)

Answer 3

I can almost prove that a lower bound is

$k \ge 21$

Conditional on this statement which is reasonable, but I have not been able to prove:

For any optimal strategy, the graph whose vertices are labeled $1$ through $k$, with an edge from $n$ to $m$ if and only if a prisoner can see $n$ on the board and write $m$, is acyclic.

If a cycle can occur for some pair of numbers, this is obviously a problem because we will be stuck in an infinite loop, but I can't prove that the edges of a cycle can't occur in separate runs.

If that statement is assumed, we can renumber if necessary so that

Each prisoner will either be able to declare which box is larger, or write a larger number on the board than was seen when the prisoner entered the room.

It is also clear that

If a prisoner opens box A, the number they write on the board should instruct the next prisoner to open box B. Otherwise, the prisoner could just as easily pretend to be the next prisoner and skip one step.

Any strategy which does not satisfy this constraint can be modified to one that does without changing $k$, so we can assume that this constraint will hold.

Now, consider a transcript describing which numbers were written on the board throughout this scenario. Suppose that box A contains $2n-1$ and box B contains $2n$ for some $1 \le n \le 25000$. If the scenarios corresponding to $n$ and $m$ produce the same transcript, with $n < m$, then the same transcript would also be produced when box A contains $2m-1$ and box B contains $2n$. This would produce an incorrect answer because $2n < 2m-1$. Hence any two distinct $n$ must produce different transcripts.

Thus, there are at least 25000 possible transcripts.

How large does $k$ need to be for this?

Color a number red if a prisoner seeing that number should check box A, and blue otherwise. The number 0 (corresponding to an empty whiteboard) can be considered red. A valid transcript is an increasing sequence of numbers which alternate between blue and red, starting with blue.

It can be shown that the number of possible transcripts is maximized when all odd numbers are blue and all even numbers are red. In this way, the number of possible transcripts not exceeding some number $k$ is $F_{k+2}$, the $(k+2)$nd Fibonacci number. We must therefore have $F_{k+2} \ge 25000$.

Since $F_{22} = 17711$ and $F_{23} = 28657$, we can conclude that $k+2 \ge 23$ and thus $k \ge 21$ for any valid strategy.

Answer 4

$k=1$

Whoever goes first opens box A, finds $n$ in it, and draws a $1$ on the board consisting of $n$ dots, dot-matrix-printer style. The next person opens box B and announces the answer.