You are the president of a secret society of mathematicians with $n$ members, including yourself. No one in the society knows what $n$ is. The dictator of the world, in an effort to erase mathematics from human history, has finally managed to capture all $n$ members of the society, and has placed them in prison.
The prison has a funny design. There are $n$ identical soundproof, windowless prison cells arranged in a circle, each containing a mathematician. The cells all have a light switch the prisoners can use, but the wiring system is screwed up, so the switch controls the light bulb in the clockwise neighboring cell. Furthermore, the switch is only capable of delivering a single flash of light at noon each day. Specifically, if this switch is set to "on" at noon, it will flash the next cell, and do nothing otherwise.
The prison warden worries that the prisoners might try to communicate using the lights, so every night at midnight, he fills all of the cells with knockout gas, cleans the cells so they can't communicate by leaving messages, sets all of the light switches to "off", and rearranges the prisoners in whatever fashion he pleases (still one prisoner per cell).
One day, the warden visits your cell. He confesses that he loves mathematics, and decides to offer your society a game to win their freedom. If any of the prisoners are able to figure out what $n$ is, they may shout out loud "There are $n$ prisoners!" (the cells are monitored with security cameras/mics). If they are correct, all prisoners will go free, and if not, they will all be executed.
The warden allows you to devise a plan for everyone else to follow. He will make $n-1$ copies of this plan, and allow every other prisoner to read it. The warden of course will also read your plan, and will perform the cell rearrangements in such a way to make it fail if he can.
What plan allows the prisoners to guarantee their freedom?
Extra for Experts: Can you find a plan which doesn't require the prisoners to make random decisions?
Notes: There is no lateral thinking required to solve this. Assume the prisoners have perfect, infinite memory, including knowledge of how many days have elapsed.
It is significant that you are one of the prisoners, and that you devise the plan. It means that while all $n-1$ other prisoners must follow the same strategy, you may follow a different strategy.
I will give priority to accepting answers which fulfill the "Extra for Experts" condition. This means there must exist a function $B(n)$ such your plan is guaranteed to stop after $B(n)$ days when there are $n$ prisoners.
This is the hardest puzzle I know, but there is a solution.
Answer
This was a monster of a puzzle. But I think I got it!
The following is a solution that does not use randomness, finishes in bounded time for any given circle size, and includes a (mostly- maybe a detail or two left to the reader =)) full proof of validity. Tell me if it makes sense, or if further clarification is needed.
We first define the subroutine $fill(S,k)$. This takes in a set of people, $S,$ such that everybody knows whether they are in $S$ or not. It also takes in a paramater $k$ related to how long to run for. It works as follows
1) On round 1, everybody in set $S$ turns on their light.
2) On every round from $2$ to $k$, everyone in $S$ and everyone who has seen a light on during $fill(S,k)$ turns on their light.
3) From round $k+1$ to $2^k+k+1$, everybody who saw a light on at the end of stage 2), and in every round since then, turns on their light.
Denote $S'$ to be the set of people who saw lights on round $k$. We first claim that, if S is only the leader, then regardless of $k$, at the end of this subroutine, everyone in the circle either sees a light, or does not see a light.
To see this, note that $S'$ either contains everyone or does not contain everyone. If it contains everyone, it is clear that stage 3) of the subroutine simply involves everyone turning on their light every round, and thus everyone sees a light at the end. If it does not contain everyone, then we note that the set of lights seen in each round of stage 2) at most doubles in size. Thus, at the end of stage 2), at most $2^k$ lights are on. But it's also easy to see that, if $S'$ is not the whole circle, then the set of lights on in stage 3) decreases by at least one each round. Thus, by the end, no lights will be on.
Now, suppose $ U > n$. Then, we claim that $ fill(S, U)$ will result in every light being on if and only if $S$ is not the empty set, and every light being off otherwise. This is easy to see because, if $U > n$, then $ S'$ will have to be the entire circle, as long as $S$ was not the empty set. Otherwise, if $S$ was the empty set, then clearly nobody will ever see a light.
Okay, now we're ready to describe our strategy:
Step 1. Deduce an upper bound $U$ on $n$, as done in many other solutions. We run $fill(L, k)$, where $L$ is the leader, for increasing $k$ starting at $1$. At some point, the result will be positive, with everyone seeing a light. At this point, we can be assured that the circle contains at most $2^k$ people where $k$ was the final value used to $fill$.
Step 2. Initialize by considering the leader to be in set $S_0$, and everyone else to be in set $S_1$. Let $k = 2$ represent the number of sets at any point.
Note that currently, everybody knows which indexed set they are in, and which sets exist. We will maintain this invariant so that everyone can coordinate their strategies.
Step 3. Set $done = false$. While not $done:$
3 A) Set $done = true$. For each subset $ I \subset \{1, 2, \cdots, k\}$, other than the empty set and the entire set:
3 A i) Everybody in the set $ \bigcup_{i \in I} S_i$ turns on their light once. Let $T$ be the set of people who saw lights on this day.
3 A ii) For every set $S_j$:
3 A ii a) Run $fill(S_j \cap T, U)$.
3 A ii b) Run $fill(S_j / T, U)$.
3 A ii c) If both $fills$ return positive results, then increment $k$ by 1, let $ S_j = S_j \cap T$, $S_k = S_j / T$, and set $ done = false$.
Step 4. We will prove that, when we reach this point, everyone in the circle can deduce the circle's size.
First, we prove that we eventually reach Step 4. Note that $done$ is only set to $false$ in 3) if a new set $ S_k$ is created. Furthermore, every new set created is not empty, and no nonempty set becomes empty during the algorithm, because $ S_j$ is only split if both $ S_j \cap T$ and $ S_j / T$ are nonempty. Thus, if there are $n$ people in the circle, we can create at most $n-2$ new sets before there are $n$ total sets, one person to a set, and no further sets can be split. At this point, set $3$ must terminate with $done = true$.
Now, suppose we reach step 4. For every set $S_i$, let $x_i = |S_i|$. For any partition $(A,B)$ of the $x_i$ into two nonempty sets, there was a corresponding round in the final iteration of Step 3 in which every person corresponding to $A$ turned on their light. This then resulted, for each $S_i$, in everyone in $S_i$ seeing a light on, or everyone seeing a light off. Furthermore, at least one person in an $S_i$ represented by $B$ saw a light, or else $A$ would have to be a closed loop. The key here is that we know that the number of people in $A$ who didn't see a light must be equal to the number of people in $B$ who did. This gives us an equation in the variables $x_i$, of the form
\begin{equation} \sum_{i \in X} x_i = \sum_{i \in Y} x_i, \end{equation},
where $ X \subset A$, $ Y \subset B$, and neither $X$ nor $Y$ is empty. We say that such an equation "satisfies" the partition $(A,B)$. More generally, we say that $(A,B)$ is satisfied by any equation of the form
\begin{equation} \sum_{i \in X} r_i x_i = \sum_{i \in Y} s_i x_i, \end{equation}
where all coefficients $r_i,s_i$ are positive, and $X$ and $Y$ are nonempty subsets of $ A$ and $B$. If a set of equations satisfies every partition of a set of variables, we say that that set of variables is fully satisfied. At step 4, we thus have a set of fully satisfied variables. Thus, to prove that we can deduce the size of the circle, we show that, given any set of variables such that $x_i = 1$, along with a satisfiable and fully satisfying set of equations on those variables, we can deduce the value of every variable
We use induction. For $ k = 2$ variables, we have $ x_1 = 1$, and the partition $ (x_1, x_2)$ yields $ k_1x_1 = k_2x_2$, where $ k_1, k_2 \neq 0$, so clearly both variables are determined.
Now, consider a set of $k$ variables $ x_1, x_2, \cdots, x_k$, and assume our hypothesis holds for all sets of $k-1$ variables. We will eleminate $x_k$ from the equations to construct a set of equations which fully satisfies $ x_1, \cdots, x_{k-1}$. For each partition $(A,B)$ of the remaining $k-1$ variables, there are two partitions of the whole set of variables: $ (A \cup c, B)$, and $ (A, B \cup c)$. Both of these partitions have some satisfying equation. If either of the satisfying equations don't include $c$, then we have an equation which satisfies $(A,B)$ on the first $k-1$ variables. Otherwise, if both satsifying equations include $c$ with some weight, then we can linearly combine them to eliminate $c$ and get a new equation, which some basic algebra tells us will also satisfy $(A,B)$ in the first $k-1$ variables. Thus, by doing this for every partition, we can construct a set of fully satisfying equations for $ x_1, \cdots, x_{k-1}$, which by our inductive hypothesis determines all of their values. Finally, we can consider the partition which separates $x_k$ form the other $k-1$ variables. This partition is only satisfied by a linear equation writing $x_k$ in terms of the other variables; as these are all determined, we can also determine $x_k$. Thus all variables are determined, and we are done.
Finally, since every person in the circle knows a fully satisfying set of equations on all of the subsets $S_i$, and knows that $ |S_1| = 1$, everyone in the circle can deduce the size of each subset, and of the entire circle.
No comments:
Post a Comment