State diagram:

Code: Select all

` [Z]<--(0,1)--[I]--(1,0)-->[?]--(1,0)-->[*]--(1,0)-->[Exit]`

^----(0,1)--[X]<-(0,1)---/

You start at I. Edges are labelled with (input, output) pairs. Non-labelled inputs loop back to the same state with (x,x) edges.

The game is pretty simple.

You start with one 1 in your stomach. By default, you eat 1s, and dumping 1s on zeroes. If you have 3 1s in your stomach at any time, you refuse to dump 1s anymore. If you ever dump a 1, you stop eating 1s.

The first person dumps a 1. They are now "out of the game" (in state Z for Zero). The first person being assigned to show up by the warden no longer matters.

The second person sees that one and eats it. We'll call this state [Z][?]0. They are now in state [?], or in an intermediate state. We have two branches: one in which the second person repeats before the third person arrives (S+), and one where the second person doesn't (S-).

If [?] visits before anyone else, we end up in [Z][X]1, which is stable. So these are the two possible states before person #3 is introduced to the room.

Case S+: 3rd person visits [Z][X]1

The third person arrives to a 1. The third person transitions to [?], giving us a state of [Z][X][?]0.

Case S-: 3rd person visits [Z][?]0

The third person arrives to a 0. The third person transitions to a [Z], giving us a state of [Z][Z][?]1.

S+ can transition to S- if [X] is the next one to visit.

S+ can transition to S+- if [?] visits next:

Case S+-:

[?] visits after S+. State is now [Z][X][X]1.

Before the 4th prisoner shows up, no visit can exit these 3 states.

So we have to worry about [Z][X][?]0, [Z][Z][?]1 and [Z][X][X]1.

The 4th prisoner visits each of these states, giving us the following possible states:

A: [Z][Z][X][?]1

B: [Z][Z][?][?]0

C: [Z][X][X][?]0

In A, the only state transition possible is [?] visiting. So it evolves as follows (all evolution is forced):

[Z][Z][X][*]0 -> [Z][Z][Z][*]1 -> [Z][Z][Z][EXIT]0

In B, either [?] visiting is a state change, which ... sends us to state A:

[Z][Z][X][?]1 -> [Z][Z][X][*]0 -> [Z][Z][Z][*]1 -> [Z][Z][Z][EXIT]0

In C, there are two initial branches. If [X] visits, we end up ... in state A.

If [?] visits, we end up ... crashing:

[Z][X][X][X]1

We lose.

Lets reverse engineer the route to failure shall we?

0 -> [Z]1 -> [Z][?]0 -> [Z][X]1 -> [Z][X][?]0 -> [Z][X][X]1 -> [Z][X][X][?]0 -> [Z][X][X][X]1

Ie, the first person puts a 1 on the track. Each person after that picks it up and drops it off again, entering the "nulled" state of [X]. We end up with a bunch of prisoners who all think that picking up the 1 is someone else's responsibility.