[bushindo]

This topic is inspired by previous prisoners on a death row problems.

There are 10 prisoners. The warden implements a simple game. He will put 100 slips, numbered from 1-100, randomly into 100 identical jar. Each prisoner will be able to open 50 jars and shuffle their contents. The prisoners will each do this individually, and in sequential order. The waiting room and the shuffling room are separate, so those prisoners waiting their turns can't see the jars being opened.

Each prisoner does not have to open the 50 jar sequentially. Each prisoner can remove the 50 slips from the jar and place them back in any order he desired. However, at the end, each jar must contain exactly 1 slip and no modification can be made to the jars' appearances, placement, orientation, etc.

After open and closing the 50 jars, the prisoner will be moved to a new room and have no communication with the ones who have yet to have their turn.

What is the minimum number of turns it takes to guarantee a sorted array of jars? Describe the strategy.

[CaptainEd]

You're right. I didn't see at first, but P1 would know exactly what P2 has in his set to sort, and P2 could as easily know what P1 had. As long they could guarantee the creation of exactly two chains, then four prisoners would suffice.

I'm still not 100% sure of the instructions necessary to meet that goal under any conditions, but I do accede the 2-chain strategy is attainable with 4 prisoners (the planting by P1 and P2 is a nice frill). Nicely done!

BTW, I really enjoyed your detailed explanations.

-- P

Thank you, Phatfingers.

The two cases, as before:

(Case 1) L contains either 1 or 2 or both: J1 (or J2) is to be swapped with the (1+Ceil(C/2)) L-hole. I got P2 right: P2 rotates, and swaps with the (Ceil(C/2)) H-hole.

(Case 2)L contains neither 1 nor 2: As described before, P2 rotates four H-holes (first, second (1+Ceil(C/2)), last).

So with your dataset

{ 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

P1 sort: { 1, 12, 13, 14, 15, 16, 17, 18, 19, 20, -- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

There are 9 holes, so ceil(C/2) = 5, 1+ceil(C/2) = 6, we swap with the 6th hole.

P1 swap: {17, 12, 13, 14, 15, 16, 1, 18, 19, 20, -- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

P2 sort: {17, 12, 13, 14, 15, 16, 1, 18, 19, 20, -- 11, 2, 3, 4, 5, 6, 7, 8, 9, 10}

P2 rotate: {17, 12, 13, 14, 15, 16, 1, 18, 19, 20, -- 11, 3, 4, 5, 6, 7, 8, 9, 10,2}

This is Case 1, so P2 swaps with ceil(c/2) = 5th hole

P2 swap: {17, 12, 13, 14, 15, 16, 1, 18, 19, 20, -- 11, 3, 4, 5, 6, 2, 8, 9, 10,7}

resulting chains: {1,17,8,18,9,19,10,20,7} and {2,12,3,13,4,14,5,15,6,16}

Edited May 22, 2009 by CaptainEd