One Hundred Prisoners and a Rubik's Cube

Question

Say there are 100 perfectly intelligent prisoners (who don't have incredibly good memories) who are jailed for life (and also live eternally). The warden decides to play a game with them. There is a room in the prison which has one 3x3 Rubik's Cube and a robot which can solve it. Every day, the warden chooses a prisoner at random, regardless of whether he has entered the room before or not, and leaves him there until he comes out (of his own accord). While inside, he can do anything to the 3x3 Rubik's Cube in there and let the machine solve it but is not allowed to touch anything else or to take anything in / leave with something (That includes making a visible mark on ANYTHING, though you're allowed to turn the cube).

If one prisoner comes up to the warden while in the room and correctly says, "All 100 prisoners have entered this room since the game began," all of the prisioners will be set free. However, if the prisoner is incorrect, all of them will be immediately executed. The prisoners are all confined in their own cells with no way of communication with any other prisoner. However, all the prisoners have one tool each, a permanent marker, which must not leave their cell.

The day before the game begins, the warden lets the prisioners go into the courtyard to formulate an action plan. If the prisoners all want to escape, what will their plan be?

Answer 1

The first prisoner to enter the room solves the cube, and becomes the arbitrator. On return to her cell, she makes a tally mark on the wall with her pen.

Every prisoner after that who enters the cell:

• if she has previously scrambled the cube, she does nothing.
• if the cube is already scrambled, she does nothing.
• if the cube is solved, she scrambles it.

Every time the arbitrator enters the room and finds a scrambled cube, she solves it and then goes back to her cell and makes a tally mark on the wall with her pen. The exception is if she is already up to 99, in which case she summons the warden.

This is pretty inefficient; you'd expect at least 9,901 days to pass before finishing (100 visits by the arbitrator, given that she gets first visit by definition). Sometimes there would be no new visitors between her visits, and that would waste more time. Still, the prisoners are immortal.

You can improve it by choosing your scrambling better. You can count to 3 using quarter-turns of a single level of the cube, or 15 using two levels. So then a visitor who had not previously changed the cube would increment the "count" if it was below 15, and the arbitrator would collect up to 15 tallies at a time. If you can count high enough reliably, it reduces to @ghosts_in_the_code's solution, and you don't need tally marks any more.

Answer 2

They simply decide on 98 different valid Rubik's cube states at the beginning of the game and denote them 1 to 98. On the first day, the prisoner leaves the cube in any state apart from the pre-defined 98. We can call this state 0.

After this, everyone (including the 1st prisoner) follows the same strategy. Whenever a prisoner sees the cube for the first time, he takes it from the current state to the next one. So suppose it is currently in 23rd state, he just takes it to the 24th state. If a prisoner has already seen the cube he does nothing.

If a prisoner finds the cube in the 98th state the first time he sees it, then he knows that everyone else has already seen it. Hence he can declare it.

Answer 3

The first prisoner to enter the room disassembles the Rubik's cube. That gives them 26 pieces, which they put in one corner of the room. Then they treat the spot 30cm to the left as the tens pile, and 30cm to the right as the units pile. So the first person puts a single piece in the units pile and leaves.

Each prisoner who enters the room for the first time increases the count (adding one to the units pile, and carrying to the tens pile as needed). The prisoner who increases it to 100 reassembles the cube with one corner inverted (these are criminals after all), hands it to the robot to solve, and summons the warden.

Meanwhile, each prisoner who returns to their cell knows what number they were in the queue, and uses their marker pen to draw the appropriate frame from an agreed flip-book style animation of a prisoner removing their chains and walking out a door.

I think I used everything.

Answer 4

Here is my solution:

Take any permutation with order (the amount of times you need to apply it to arrive where you started) above 100, for example this permutation I just constructed:

(R U)29

Which is the same as

(R U)15 (R U)14

This has order 105:

The first part, (R U)15 is a 7-cycle of edges, or 2 7-cycles of edge stickers. The second part, (R U)14, is a 5 cycle of corners or 3 5-cycles of corner stickers, but there is also another corner twisted in place which is a 3-cycle of cornerstickers. The order of a permutation is the least common multiple of the lengths of it's cycles, in this case: LCM(3,5,7)=105.

The first prisoner lets the cube be solved by the robot, in case they didn't get it solved, and he then has to apply the above moves 6 times (5 times to get rid of the extra 5 in 105, then once).

all the other prisoners apply the sequence once. If they get called in the room more than once they just do nothing after the first time, or maybe have a chat with the robot.

Now when a prisoner sees that his application of the sequence solves the cube he knows that the sequence has been applied 105 times to a solved cube, of which 6 by the first one, so he is number 100 and tells it to the warden.

I like this solution because the last prisoner will have a great experience. He will see the cube getting solved magically, but trough logic he knows that he's number 100. I also used everything except the marker, but it might be useful for the prisoners to write (R U)29 on their wall so they don't forget.

This solution is also as efficient as possible, the prisoners get out on the first occasion!

Answer 5

Before leaving their cell for the first time, the prisoner breaks the permanent marker and wets their finger with the ink. If they have ever left their cell before, they take no action while in the cell.

If there are no cube faces marked, they smear the ink on one and leave the cube unsolved. If there are any marked faces:

• if the cube is solved, mark a face and scramble the cube
• if the cube is scrambled, solve it

After this, if 50 faces are marked and the cube is solved, declare victory.

Answer 6

It seems that this problem needs an additional assumption for the initial configuration of the cube at the start of the game.

If the initial cube configuration is not predefined (i.e. random initialization), then there doesn't seem to be a way to know if you are "The first prisoner to enter the room" (Callidus' solution). Similarly, for any other solutions using cube states for counting (i.e. Jens Renders') the initial configuration of the cube could match any counting state, thus making the problem unsolvable in general.

So the initial state of the cube must be predefined for the problem to be solved. There are only two possible initializations for the cube:

• scrambled: then you can only use the unscrambled state to signal having entered the room, meaning you can only count up to 1. Any other configuration a prisoner applies to the cube still counts as scrambled and is therefore indistinguishable from the initial state. This version of the problem thus has no solution.

• unscrambled: then you can use cube states for counting as in Jens Renders' solution. Callidus' solution doesn't seem to work here either because again you can only count up to 1.

Answer 7

I want to build on ghosts_in_the_code and Jens Renders' ideas and provide a practical solution easy to perform and to memorize.

The problem boils down to encoding in the cube position the number of prisoners who were in the room.

Alternating R and U', like RU'RU'RU'... returns to the original position after 126 quarter turns. This gives enough different positions to encode a number from 0 to 100.
So the trick to encode a number is to do this sequence in reverse for as many moves as there were prisoners. For 1 do R'. For 2 do UR'. For 3 do R'UR'. For 11 do R'UR'UR'UR'UR'UR'. etc. You get the idea.

To "read" the number from the cube, just do the sequence RU'RU'... and count how many moves you need to get to the unscrambled position.
The first time any prisoner enters the room, he "reads" the number from the cube and adds one. If he gets to 100 he calls the warden and claims everyone was here. If not, he encodes the new number in the cube before leaving.

Note that the sequence RU'RU'... is super easy to do with the 2 index fingers.
UR'UR'... is also easy if you rotate the cube horizontally to swap left and right. It becomes UL'UL'...

Answer 8

[This puzzle just got bumped to the front page due to another answer being added, so I just saw it for the first time]

This mainly expands on ghosts_in_the_code's answer.

The prisoner who is invited into the room the first day first puts the cube to a solved state (if it is not already in such a state), which has a "cube number" of zero.

That prisoner, and each subsequent visitor on their first visit to the room, increments the "cube number" by 1.

On a repeat visit, if the plans are secret from the warden, and they don't want to give the game away, they can play with the cube and leave it in a different representation of the same number it showed when they arrived.

The "cube number" is determined by

by assigning the following scores to the squares visible on the face of the cube with a white square in the middle:
White = 0, Red = 1, Yellow = 2, Blue = 5, Green = 10, Orange = 25.

The solving machine will be particularly useful on

days that are a multiple of 5, and especially so on days that are a multiple of 25, as they can quickly return to a completely white face and put the relatively small number of non-white squares required on it.

The prisoner who, on entering the room for the first time after at least 100 days have elapsed, sees the cube scoring of 99 - e.g.

The white face looks like or ,

can either make the declaration immediately, or leave the cube showing a score of 100.

The next prisoner to visit would immediately know on looking at the cube that all 100 prisoners have been in the room at least once (and left and gone back to their cells).

This leaves 1 extra day beyond the absolute minimum, in case the warden starts being tricksy - "no, you're still in the middle of your visit, so not all 100 have visited yet.".

This scheme also allows for a check mechanism as follows - if at any time:

1. any prisoner on arriving in the room (other than on the first day) sees a score higher than the number of days elapsed since the start, or

2. a prisoner on a repeat visit sees a lower score on the cube than last time they visited, or

3. a prisoner on a repeat visit sees a score higher than the number of days elapsed since their previous visit plus the score they saw on their previous visit

They may assume that someone has been tampering with the cube - either the warden, or another prisoner who failed to follow the plan correctly (if they're not ABSOLUTELY sure they detected tampering, and the state of the cube otherwise seems valid, they should continue as normal). They can then attempt to signal this to other prisoners by leaving the cube showing a score higher than 100, or by leaving the cube solved. They can do this on any future visits too, to maximise the chance of other prisoners discovering the tampering.

Whilst the puzzle will not be able to be solved once tampering is detected, they at least avoid risking everyone being executed because one of the other prisoners made a mistake or a sabotage occurred...

The marker will be used

by each prisoner to keep track of how many days have passed, and what the last thing they saw on the cube was, in order to aid the tamper-detection strategy. ... or more simply to keep a reminder of how the scores work.