# The governor's birthday puzzle

The prison governor surveys the three petty thieves in his panopticon.

"Next week is my birthday. I've a mind to free some of you, if you can solve a little puzzle of mine."

"I'm going to put you in separate cells. Then I'll give each of you a nine digit code. If you can communicate your code to one of your fellow prisoners in a week, then I'll let you go."

"The jailer will visit each of you every day. And he'll have this bag with him".

The governor carefully counts out fifteen icosahedral (20-sided) dice and puts them into the bag.

"You can take one die from the bag and put it whichever way up you like. The jailer will show it to the next prisoner. He'll return to the first prisoner to show her the die from the third prisoner at the end of his daily round. Can you figure out a way to use the dice to communicate your code in seven days?"

"That won't work," said Annabelle. "There are three of us and seven days in the week, so we need twenty-one dice."

"That's okay," laughed the governor. "You don't have to use a dice every day. But I'll tell you what, I'll throw in a bag of pennies as well. If you don't use a die on some day you must use a penny instead. You can put the penny heads-up or tails-up."

"But its your birthday" wheedled Christine, "surely you can give us a little more help."

"Here's what I'll do. At the end of each day before my birthday I'll announce a single digit from one of your codes on the intercom. I might say that `Beatrice's first digit is a zero' or whatever. I'll tell you whose code contains the digit and I'll always give the digits (from each prisoner) in order through the code number. But you will have to wait and see whose code I pick each day. Over the week I might give you the first six digits from Annabelle, or the two digits from each of you or any other pattern I like. And that's it - no more concessions."

He lets the prisoner's discuss before sending them to their cells.

"I'm not stupid", Annabelle says. "No matter what we do it's not possible to specify a 9 digit number using six 20-sided dice and even a single coin. The coins are no good; I must use a die every day".

"Don't forget that he's going to announce some of our digits" says Christine, "that's got to help".

"You're clutching at straws" opinions Beatrice. "He doesn't have to announce any of my digits. The only way I can be sure of being free is if I use a die every day. And that's what I'm going to do."

"Me too" agree's Annabelle. "So we'll need fourteen dice between us. I hope you can take one for the team Christine, because that only leaves one die for you."

"Listen" says Christine, "if you follow my plan we'll all get out. It doesn't matter that he's listening to us planning - no matter which codes he picks, or whose digits he announces we'll still all be free".

How did Christine do it?

There are three prisoners A, B and C. Each prisoner is given an integer code $$k_i$$ with $$0 \leq k_i < 10^9$$.

On each of the days 1, 2, ..., 7, A can select a value from the set $$\{0, 1, 2, \ldots, 19, H, T\}$$ which is passed to B, B can pass a similar value to C, and C can pass a similar value back to A again. They cannot communicate in any other way (no tricks with hot coins, or changing the orientation of a dice etc.).

Although 21 messages will be sent, at most 15 of them can use a number. The other messages must use $$H$$ or $$T$$. There is no limit to the number of coins permitted.

At the end of days 1 to 6 (after the dice/coin exchange) the governor announces to everyone a single digit from one of the $$k_i$$. The governor must say whose digit it is. When the governor announced a digit for some prisoner $$X$$, the governor must give the first digit of $$X$$'s code that the governor has not previously announced. If $$k_i$$ is smaller than $$10^8$$ then the governor must pad it with leading zeros to make it into a 9 digit number.

The governor does not announce any digit on day seven. Instead after the prisoners have exchanged their dice / coins, each prisoner must describe the code for another prisoner (B gives A's code, C gives B's code and A gives C's code).

First each prisoner takes the last two digits in their code, $$k_8$$ and $$k_9$$, and converts them to binary ending up with an, at most, 7 digit number $$j$$ in base 2. On day 1 each of them uses a die to transmit $$j_1$$ and $$k_7$$ by sending $$j_1$$ as the 10s place on the die and $$k_7$$ as the 1s place (treating a 20 on the die as 00). On each subsequent day $$n$$ whoever's digit was revealed by the governor the previous night uses a coin to transmit $$j_n$$ while the other two use a die to transmit $$j_n$$ and $$k_{8-n}$$. At the end of the week each prisoner will have transmitted $$j$$ in full as well as each digit of $$k_7$$ through $$k_1$$ that the governor didn't reveal, meaning all they have to do is reconvert $$j$$ back to base 10 to recover the entirety of each $$k$$.