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

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 4

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 5

Here is my solution:

Take any permutation with order(the amount of times you need to aply 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 didnt get it solved, and he then has to apply the above moves 6 times (5 times to get rid of the extra 5, 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 wich 6 by the first one, so he is number 100 and tells it to the wardner.

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 usefull 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 prisonners get out on the first occasion!