[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.

[Guest]

Do they get the "one night of preperation" like in the previous ones?

[bushindo]

Do they get the "one night of preperation" like in the previous ones?

Yup, they do get the obligatory one night of preparation.

[CaptainEd]

6 prisoners can certainly complete the task. Here's a proposal, probably suboptimal, but certain to work:

Let's call the numbers 1-50 the Low numbers (L), and the numbers 51-100 the High numbers (H). And the corresponding jars are the L jars and the H jars respectively.

Prisoner 1: Sort the numbers in the L jars. Conceivably all the L numbers are there, possibly all the H numbers are there, probably some L and some H numbers are there. Don't try to put the right number in the right jar yet. Just sort them.

Prisoner 2: Sort the numbers in the H jars.

At this point there may be some L numbers in the L jars, let's say there are C of them (0 <= C <=50). Notice there are exactly C H numbers in the H jars as well. (Because there are (50-C) H numbers in L jars, and when they are moved to the H jars, they will displace exactly (50-C) L numbers in H jars. That means there are exactly C H numbers in H jars right now).

Prisoner 3: Swap the last 25 H numbers from L jars with the first 25 L numbers in H jars. If there aren't that many, do all there are. That is, when you get to L numbers in L jars, stop swapping. (If that happens, then all L are in L, all H are in H. But if it doesn't, there are more to do in the next batch) [edit: that is, starting at jars 50 and 51, if 50 has an H and 51 has an L, then (swap them and proceed to 49 and 52); if you get to an L jar with an L number, stop.]

Prisoner 4: Swap the next batch of 25 H numbers from L jars with the next batch of 25 L numbers in H jars. These are located in jars 1-25 and 76-100. If there aren't that many, do all there are. Once again, once you get to L numbers in L jars, stop swapping. Once you're done (or even if you can't get started), you're done.

[edit: that is, starting at jars 25 and 76, if 25 has an H and 76 has an L, then (swap them and proceed to 24 and 77); if you get to an L jar with an L number, stop.]

At this point, all the L numbers are in L jars, all the H numbers are in H jars.

Prisoner 5: Sort the numbers in the L jars (they are all the L numbers)

Prisoner 6: Sort the numbers in the H jars (they are all the H numbers)

The deed is done.

Edited May 19, 2009 by CaptainEd

[CaptainEd]

I think 4 prisoners can do it, we merge the first 4 rounds from my previous answer into 2:

Prisoner 1: starts swapping H for L, beginning with 1 vs. 100. Here's the process:

Lojar = 1, hijar=100;

loop

if lojar and hijar both contain H, decrement hijar and loop

if lojar and hijar both contain L, increment lojar and loop

if lojar contains H and hijar contains L, (swap contents, increment lojar, decrement hijar, and loop)

if lojar contains L and hijar contains H, increment lojar, decrement hijar and loop

P1 does this until 50 jars are opened.

Prisoner 2 finishes the process, starting at the other end! That is, lojar = 50, hijar=51;

loop

if lojar and hijar both contain H, increment hijar and loop

if lojar and hijar both contain L, decrement lojar and loop

if lojar contains H and hijar contains L, (swap contents, decrement lojar, increment hijar, and loop)

if lojar contains L and hijar contains H, decrement lojar, increment hijar and loop

At this point, all the L numbers are in L jars, all Hs in H jars.

Prisoner 3 puts the Ls in their proper places

Prisoner 4 puts the Hs in their proper places

Edited May 19, 2009 by CaptainEd

[Guest]

You memorize the alphabetical order of the prisoners, then give them a number 1-10. Reserve jars 1-10 accordingly to put the names there. Prisoner #1 goes thru jars 1-10 and swaps any name out and puts it into one of the jars 11-40. Now the first 10 jars do not contain any of the prisoners names. Prisoner #2 looks thru jars 11-40 and puts any names he finds in the correct jar (1-10). Prisoner #3 takes jars 41-80 and does the same. After prisoner #4 goes, all the names will be in order alphabetically in jars 1-10. So 4 should get the job done.

Edited May 19, 2009 by James8421

[CaptainEd]

It looks to me like the OP says that, after each prisoner has taken a turn, there must be one slip in each jar. (Also, note we don't have anybody's names, or need them, OP says there are only numbers in jars)

Separately, my recent solution has a problem

The state at P1's 50th opening (after swap, if any) will be that the open L jar contains an L, or it contains an H. If it contains an L, P2 will not have to see it again, but if it contains an H, P2 will have to open that jar again. That means there's a jar that both of them have to open, so the two of them cannot open and sort all 100. In fact, in these cases, there will be an H in an L jar and an L in an H jar when P2 is done. And we can't even predict which jars.

Back to the drawing board...

Edited May 19, 2009 by CaptainEd

[bushindo]

I think 4 prisoners can do it, we merge the first 4 rounds from my previous answer into 2:

Prisoner 1: starts swapping H for L, beginning with 1 vs. 100. Here's the process:

Lojar = 1, hijar=100;

loop

if lojar and hijar both contain H, decrement hijar and loop

if lojar and hijar both contain L, increment lojar and loop

if lojar contains H and hijar contains L, (swap contents, increment lojar, decrement hijar, and loop)

if lojar contains L and hijar contains H, increment lojar, decrement hijar and loop

P1 does this until 50 jars are opened.

Prisoner 2 finishes the process, starting at the other end! That is, lojar = 50, hijar=51;

loop

if lojar and hijar both contain H, increment hijar and loop

if lojar and hijar both contain L, decrement lojar and loop

if lojar contains H and hijar contains L, (swap contents, decrement lojar, increment hijar, and loop)

if lojar contains L and hijar contains H, decrement lojar, increment hijar and loop

At this point, all the L numbers are in L jars, all Hs in H jars.

Prisoner 3 puts the Ls in their proper places

Prisoner 4 puts the Hs in their proper places

Bravo, CaptainEd. I agree that 4 is pretty much the minimum number of turns required for guarantee a sorted array. This is is solved way too fast, I should make them harder next time.

[Guest]

Bravo, CaptainEd. I agree that 4 is pretty much the minimum number of turns required for guarantee a sorted array. This is is solved way too fast, I should make them harder next time.

I tried simulating that strategy with 10 jars and five reads. My first attempt failed. Here's what I had...

1 6
2 5
3 4
4 3
5 2
6 1
7 10
8 9
9 8
10 7

Jar  Init

I would expect a similar outcome if Jar #1 started at 51 and scaled down to 1, then filled in the remainder. If you encounter all H or all L in your first pass of 50, you don't have the option of trading an L for an H. You might easily deduce that you could swap Jars 1 and 6 in the above case (even though you don't know the contents of Jar #6), but the rules don't allow it. With only four prisoners, the first jar would still contain an H value in an L jar.

[bushindo]

I tried simulating that strategy with 10 jars and five reads. My first attempt failed. Here's what I had...

1 6
2 5
3 4
4 3
5 2
6 1
7 10
8 9
9 8
10 7

Jar  Init

I would expect a similar outcome if Jar #1 started at 51 and scaled down to 1, then filled in the remainder. If you encounter all H or all L in your first pass of 50, you don't have the option of trading an L for an H. You might easily deduce that you could swap Jars 1 and 6 in the above case (even though you don't know the contents of Jar #6), but the rules don't allow it. With only four prisoners, the first jar would still contain an H value in an L jar.

Good catch. Back to the drawing board.

[Guest]

It looks to me like the OP says that, after each prisoner has taken a turn, there must be one slip in each jar. (Also, note we don't have anybody's names, or need them, OP says there are only numbers in jars)

Separately, my recent solution has a problem

The state at P1's 50th opening (after swap, if any) will be that the open L jar contains an L, or it contains an H. If it contains an L, P2 will not have to see it again, but if it contains an H, P2 will have to open that jar again. That means there's a jar that both of them have to open, so the two of them cannot open and sort all 100. In fact, in these cases, there will be an H in an L jar and an L in an H jar when P2 is done. And we can't even predict which jars.

Back to the drawing board...

I see now I misread this one about 10 times!

[Guest]

It may take all ten because while they are switching and putting the numbers in order, they might be putting other numbers in the wrong spot, and if they assign x number of guys to take certain jars, they will not be able to communicate with the rest after they have gone thru their jars. So then the prisoners who go ahead further down the line could possibly screw up the order. because of the randomness of the number placement in the jars I'd say it could take all of them and still have a chance at failure.

[Guest]

say prisoner #1 opens jar1 and finds a 5, he then opens jar5 and sees a 30, well now he has to put the 30 in jar1 so he can put the 5 from jar1 into jar5, then has to open jar30 and he pulls out say a 21...see where this is heading? Hes not covering much ground and is having to open more jars than he is correcting. Unless he gets lucky and say pulls a 5 outta jar1 and a 1 outta jar5.

It may take all ten because while they are switching and putting the numbers in order, they might be putting other numbers in the wrong spot, and if they assign x number of guys to take certain jars, they will not be able to communicate with the rest after they have gone thru their jars. So then the prisoners who go ahead further down the line could possibly screw up the order. because of the randomness of the number placement in the jars I'd say it could take all of them and still have a chance at failure.

[Guest]

Ok so I may have misread it again , I was under the assumption that they had to swap the numbers, but I see they can open up to 50 jars and rearange them how they please. Perhaps I need to write it down on a sticky in bold letters and stick it to my computer

[Guest]

captained's strategy of 4 people i think would work but anyway the second prisoner would not know the values of high jar low jar unless u did something like leave them in the first two jars but that wouldnt workout in the end. Anyway

but sadly i could only get it to six. values are theoretical and arranged as first twenty five, second 25,...,...

1. sort first 50 (1-75,26-100,1-100,1-100)i will explain my logic on the first step

1-75 because the first 25 obviously have 25 higher now, 26-100 the second 25 have 25 lower

2. sort second 50 (1-75,26-100,1-75,26-100)

3. sort middle 50 (1-75,26-75,26-100,26-100)

4. sort first 50 (1-50,26-75,26-100,26-100)

5.sort second 50 (1-50,26-75,26-75,51-100)

6. sort middle 50

this is the final setep because the middle 50 hold 26-75 and are sorted so the first 25 must hold one through 25 and are sorted and same with last 25

[Guest]

so i cant find a flaw in this but i think there might be one

same format as above post

step

1. sort first 25 and last 25 as one group not independently (1-75,1-100,1-100,26-100)

2. sort middle 50 (1-75,1-75,26-100,26-100)

3. sort first 50 (1-50,26-75,26-100,26-100)

4. sort second 50 (1-50,26-75,26-75,50-100)

by similar logic as last time if 26-75 is in the second and third 25 then all 26-75 must be there so the first and last 25 are done

5. sort middle 50

and done let the mistake finding ensue

[CaptainEd]

OK, third time's a charm.

I'll describe the two principles, then the slight distortion that is needed in the final solution.

First, terminology:

"low" number or jar (aka "L") = between 1-50 inclusive

"high" number or jar (aka "H") = between 51-100

"plant" = put the nth number in the nth jar (e.g. put "7" into jar 7)

"hole" = a jar that has a wrong number in it; a jar that has not yet been planted.

"chain" (in permutation theory, called a "cycle") = sequence of jars, each containing the number of the next, the last one containing the number of the first.

Sorting principle:

One prisoner (P1) will open the L jars, and will plant all the Ls found there, and place the Hs into the holes, sorted ascending. Similarly, P2 will open the H jars, plant the Hs found there, and sort the Ls into the holes.

Benefits of sorting: Some numbers go into their final resting place right now, the holes show exactly where the other numbers go.

Drawbacks of sorting: After P2 has done his sorting, the L holes and the H holes act like buttons and buttonholes: the lowest L hole contains the number of the lowest H hole, which contains the number of the lowest L hole. That's cute, but nobody knows how to find the next button-buttonhole pair

Chain principle:

One prisoner will build a chain, another will follow it. We build a chain by having P2 rotate his set of sorted Ls, so that the lowest H hole contains the second-lowest L number, the 2nd-lowest H hole contains the third-lowest L number,...,highest H hole contains the lowest L number. Now, all the L holes and H holes form exactly one chain.

Benefits of a chain are: you don't have to open any unnecessary jars to clean it up; you open a jar, take out the number (n1), go to jar (n1), open it, take out the next number (n2) and replace it with (n1). continue through the entire chain, back to the original jar.

Potential drawbacks of a chain: nobody knows where to find the chain;if it's longer than 50, there will be a wasteful opening.

Distortion of principles into final solution, that maintains all the benefits and removes all the drawbacks:

Main concept is: we will guarantee that there are two chains built, one including jar 1 and one including jar 2, so that it's easy to find the chains.

Let's say there are 2*C holes (that is, there are C H-holes and C L-holes). We will build two chains of length C (or one of length (C+1)/2 and one of length (C-1)/2), if C is odd). (In what follows, "(C/2)" implies rounding up if C is odd)

P1 and P2 now follow procedures that depend on the presence or absence of numbers 1 and 2 in the L jars. Oddly enough, the cases break down into

(Case 1) either 1, 2, or both are present in the L jars

(Case 2) 1 and 2 are both missing from the L jars

(Case 1)

First, P1 opens all the L jars, plants all the Ls, sorts all the Hs into the holes. Then, if 1 and 2 are both present, P1 swaps the contents of jar 1 and the lowest hole, and swaps the contents of jar 2 and the (C/2) th hole. However, if only one of 1 or 2 is present, P1 swaps that one with the (C/2)th hole.

P2 opens all the H jars, plants all the Hs, sorts all the Ls into the holes, rotated downward by ONE SPOT: the 2nd lowest number goes into the lowest hole...highest number goes into the 2nd highest hole, lowest number goes into the highest hole.

Then, in order to divide this chain into two chains, P2 swaps the contents of the last hole with the (C/2)th hole.

(Case 2)

P1 opens all the L jars, plants all the Ls, sorts all the Hs into the holes.

P2 opens all the H jars, plants all the Hs, sorts all the Ls into the holes, rotated downward by ONE SPOT.

Then, in order to divide this chain into two chains, separating 1 and 2 into the two chains, P2 rotates the contents of 4 holes downward: first, second,(1+C/2),last. So first now contains what second contained, second contains what (1+C/2)th hole contained, (1+C/2)th hole contains what last contained, and last contains what 1st contained.

(After Case 1 or Case 2)

Now, it's easy. P3 opens jar 1, walks the chain, planting the numbers along the way, finishes the chain.

P4 does the same starting with jar 2.

We guaranteed that no chain is longer than 50, so we don't get stuck with P3 and P4 having to open the same jar. Everything not in a chain was already planted by P1 or P2, so all the jars are properly planted.

I'll add examples in next post, this is getting too big.

Edited May 20, 2009 by CaptainEd

[CaptainEd]

OK, third time's a charm

Edit: sorry, gang, I'm having trouble copying cells from an Excel spreadsheet and preserving columns. My answer (in post 17) stands, but it might be hard to follow without seeing examples. I'll get them here somehow...sometime...

Edited May 20, 2009 by CaptainEd

[CaptainEd]

Edit: sorry, gang, I'm having trouble copying cells from an Excel spreadsheet and preserving columns. My answer (in post 17) stands, but it might be hard to follow without seeing examples. I'll get them here somehow...sometime...

[font="Courier New"] 1 and 2 both present in L
Jar 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P1 Sorted 1 2 12 13 5 15 16 8 17 19
P1 swapped 12 16 1 . . . 2 . . .
P2 Sorted . . . . . . . . . . 11 4 6 14 7 9 10 18 3 20
P2 swapped . . . . . . . . . . . . . . 3 . . . 7 .
Chain1 (1,12,4,13,6,15,3)
Chain2 (2,16,9,17,10,19,7)[/font]

[font="Courier New"] 1 is in, 2 is not present in L
Jar 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P1 Sorted 1 12 13 15 5 16 17 08 19 10
P1 swapped 16 . . . . 1 . . . .
P2 Sorted . . . . . . . . . . 11 3 4 14 6 7 9 18 2 20
P2 swapped . . . . . . . . . . . . . . 2 . . . 6 .
Chain1 (1,16,7,17,9,19,6)
Chain2 (2,12,3,13,4,15,2)[/font]

[font="Courier New"] 2 is in, 1 is absent in L
Jar 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P1 Sorted 12 2 13 15 5 16 17 8 19 10
P1 swapped . 16 . . . 2 . . . .
P2 Sorted . . . . . . . . . . 11 3 4 14 6 7 9 18 1 20
P2 swapped . . . . . . . . . . . . . . 1 . . . 6 .
Chain1 (1,12,3,13,4,15)
Chain2 (2,16,7,17,9,19,6)[/font]

[font="Courier New"] 1 and 2 both absent in L
Jar 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P1 Sorted 12 13 15 16 5 17 19 8 9 10
P1 swapped . . . . . . . . . .
P2 Sorted . . . . . . . . . . 11 2 3 14 4 6 7 18 1 20
P2 swapped . . . . . . . . . . . 3 6 . . 1 . . 2 .
Chain1 (1,12,3,15,4,16)
Chain2 (2,13,6,17,7,19)
[/font]

[Guest]

[font="Courier New"] 2 is in, 1 is absent in L
Jar 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P1 Sorted 12 2 13 15 5 16 17 8 19 10
P1 swapped . 16 . . . 2 . . . .
P2 Sorted . . . . . . . . . . 11 3 4 14 6 7 9 18 1 20
P2 swapped . . . . . . . . . . . . . . 1 . . . 6 .
Chain1 (1,12,3,13,4,15)
Chain2 (2,16,7,17,9,19,6)[/font]

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

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

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

P4: . . . ???

It seems very close, but I think the attempt was foiled by jar 1's cycle containing the 2 somewhere in H (which it has no way of knowing).

[CaptainEd]

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

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

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

P4: . . . ???

It seems very close, but I think the attempt was foiled by jar 1's cycle containing the 2 somewhere in H (which it has no way of knowing).

Thanks, Phatfingers,

-Yes, this dataset fails.

-Yes, I think you did the swaps inaccurately, at a one-off location, but it fails according to (my interpretation of ) my instructions, as well.

-No, the attempt wasn't foiled by having no way of knowing where the other number was living--P1 gets to see exactly half, which means P1 (actually us, as the puppeteers) knows exactly what's in the other half, and exactly where they will go once P2 has sorted them.

The problem is, at this point, we're doing software-level bookkeeping (let's see, should that be (C+1/2) or (1+C/2)?) without my actually writing and testing the code. I apologize for that.

I'll do the code and get it right (RSN), but here is the main fact, which I suspect can be agreed upon without my specifying the precise locations:

Basic principle:

* P1 sorts and plants L jars, makes an adjustment for ensuring J1 and J2 are included in the separate chains P2 will make

* P2 sorts and plants H jars, then tweaks (in H jars only) to ensure 2 chains of any length less than 51.

* P3 follows chain starting at J1, filling roughly half of the holes

* P4 follows chain starting at J2, filling the remaining holes.

This must work, as long as we can ensure that neither chain grows to 51. The devilish details are exactly in how to link J1 into the first chain and J2 into the second.

[Guest]

it think the mistake being made is the first guy does his deal then any reasonable intelligent p2 will know exactly where all the jars are so he is the one that makes sure j1 and j2 link to separate chains. P1 just puts the lowest high number in j1 and second lowest in j2. all the others are in there right place or ascending order so as stated p2 can deduce all the locations and set up the two strings to be seperate. It might not be possible from a computer logic stand point, id have to think about it. but an intelligent person looking at a specific case could always work it out.

i like my answer tho it requires less thought and i like thinking less

[bushindo]

Credit goes to CaptainEd

This is a slight modification of CaptainEd's procedure. The key is that we don't let P1 pick the chain starters for P3 and P4. We'll let P2 do it since P2 has complete information about the entire system, given an agreed-on strategy with P1.

Procedure:

1) Let P1 open all L jars, plant all the L slips, and sort the remaining slips into the holes.

2) P2 opens the 50 H jars. He will know what numbers the 50 L jars contain, and given that he knows of P1's strategy, he'll know the exact ordering of the first 50 jars.

Now, the first 50 jars will contain 1-cycles (correctly planted jars) and/or single edges (holes) pointing into the H jars. Since P2 knows about that precise ordering, P2 can easily construct 2 cycles, each of length 50 or less. Let J99 be the start of one chain, and J100 be the start of the other chain. If slip 99 or 100 are in the H jars, let P2 place them at the end of the corresponding chain.

3) P3 start at J99 and walk the chain.

4) P4 starts at J100 and walks the chain.

Edited May 22, 2009 by bushindo

[CaptainEd]

Credit goes to CaptainEd

This is a slight modification of CaptainEd's procedure. The key is that we don't let P1 pick the chain starters for P3 and P4. We'll let P2 do it since P2 has complete information about the entire system, given an agreed-on strategy with P1.

Procedure:

1) Let P1 open all L jars, plant all the L slips, and sort the remaining slips into the holes.

2) P2 opens the 50 H jars. He will know what numbers the 50 L jars contain, and given that he knows of P1's strategy, he'll know the exact ordering of the first 50 jars.

Now, the first 50 jars will contain 1-cycles (correctly planted jars) and/or single edges (holes) pointing into the H jars. Since P2 knows about that precise ordering, P2 can easily construct 2 cycles, each of length 50 or less. Let J99 be the start of one chain, and J100 be the start of the other chain. If slip 99 or 100 are in the H jars, let P2 place them at the end of the corresponding chain.

3) P3 start at J99 and walk the chain.

4) P4 starts at J100 and walks the chain.

Yes, it's the details of creating those chains where my math errors caused problems. Actually, either P1 or P2 could take both responsibilities. Thanks for the interesting problem!

[Guest]

Thanks, Phatfingers,

-Yes, this dataset fails.

-Yes, I think you did the swaps inaccurately, at a one-off location, but it fails according to (my interpretation of ) my instructions, as well.

-No, the attempt wasn't foiled by having no way of knowing where the other number was living--P1 gets to see exactly half, which means P1 (actually us, as the puppeteers) knows exactly what's in the other half, and exactly where they will go once P2 has sorted them.

The problem is, at this point, we're doing software-level bookkeeping (let's see, should that be (C+1/2) or (1+C/2)?) without my actually writing and testing the code. I apologize for that.

I'll do the code and get it right (RSN), but here is the main fact, which I suspect can be agreed upon without my specifying the precise locations:

Basic principle:

* P1 sorts and plants L jars, makes an adjustment for ensuring J1 and J2 are included in the separate chains P2 will make

* P2 sorts and plants H jars, then tweaks (in H jars only) to ensure 2 chains of any length less than 51.

* P3 follows chain starting at J1, filling roughly half of the holes

* P4 follows chain starting at J2, filling the remaining holes.

This must work, as long as we can ensure that neither chain grows to 51. The devilish details are exactly in how to link J1 into the first chain and J2 into the second.

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

[Guest]

good job cap'n