How many prisoners?

[sfwc]

Congratulations! Your proof is pretty much the same as mine, except that my proof of the lemma is simpler.

Spoiler:

Suppose that we have two solutions a₁...a_n and b₁...b_n. Choose i such that b_i/a_i is minimal, let this minimal value be k, and for each j let c_j = b_j - k.a_j, so the c_j satisfy the same equations and are all nonnegative rationals. Let A be the set of j such that c_j = 0. A is nonempty, since it contains i. Suppose for a contradiction that A doesn't contain all the numbers up to n. Then by hypothesis we can find another set B with B \ A nonempty and such that the sum over j in B of the c_j is equal to the sum over j in A of the c_j. But the left hand side of that equation is strictly positive, and the right hand side is zero, which is the contradiction we wanted. So each c_j is zero, and so b_j = k.a_j for each j. As a₁ = b₁ = 1, we get k = 1, and so b_j = a_j for each j and so the two solutions are equal.

[skeptical scientist]

Yeah, that's a much better proof of the lemma.

So, did you hear this puzzle from someone else, or invent it yourself?

[sfwc]

I came up with it. I was tinkering around looking for a minimal constraint that would allow information to be transmitted, and I stumbled on it.

[Ankit1010]

swfc:
When the prisons are cleaned, is every switch left in the state that the prisoner who was in the cell left it in?

Also, can the warden choose which prisoner to put where, or is it always random, meaning that eventually well get to every distribution?

[sfwc]

When the prisons are cleaned, is every switch left in the state that the prisoner who was in the cell left it in?

No, each switch is left in the off position.

Also, can the warden choose which prisoner to put where, or is it always random, meaning that eventually well get to every distribution?

Yes, the warden can choose.

[Tnarg]

Once we know the upper bound we can ask questions of the group and we 1 one bit anser.
my idea is to spilt people in to groups and know the size of the group.

Spoiler:

Make group Z from A,B,C
Every one in Group W,X,Y turns there light on and every one not in a group that recive this becomes group Z



Start at the start I'm in group 1 every one else dose not have a group, we will call this state 1,???

State 1 ???
makes 2 from 1
Asks When making 2 did anyone in 1 get a signle
if yes Then sovles Anser 1
if no go to state 1 2 ???

State 1 2 ???
Make 3 from 1,2
Asks When making 3 did anyone in 1 get a signle
Asks When making 3 did anyone in 2 get a signle
if both is true then solved anser 2
if none then go to state 1, 2, 3, 3, ???
if one is true go to state 1, 2, 3, ???

state 1, 2, 3, ???
Make 4 from 1,2,3
Ask when making 4 did anyone in group 1 get a single
Ask when making 4 did anyone in group 2 get a single
Ask when making 4 did anyone in group 3 get a signle
if all true anser is 3
go to one of the folling State 1,2,3,4??? 1,2,3,4,4??? 1,2,3,4,4,4???

State 1, 2, 3, 3, ???
Make 4 from 1,2,3
Ask when making 4 did anyone in 3 get a signle
Ask when making 4 did anyone in 3 not get a signle
if differnt undefine 4 and the people in group 3 that got a signle becomes group 4 go to state 1,2,3,4???
Ask when making 4 did anyone in group 1 get a single
Ask when making 4 did anyone in group 2 get a single
if every one got a sigle then anser is 4
go to one of the folling State 1,2,3,3,4??? 1,2,3,3,4,4??? 1,2,3,3,4,4,4??? 1,2,3,3,4,4,4,4???

State 1,2,3,4???
Make 5 from 1,2,3,4
Ask when making 5 did anyone in group 1 get a single
Ask when making 5 did anyone in group 2 get a single
Ask when making 5 did anyone in group 3 get a single
Ask when making 5 did anyone in group 4 get a single
if every one got a sigle then anser is 4
go to one of the folling State 1,2,3,3,4,5??? 1,2,3,3,4,5,5??? 1,2,3,3,4,5,5,5??? 1,2,3,3,4,5,5,5,5???


State 1,2,3,4,4???
Make 5 from 1,2,3,4
Ask when making 5 did anyone in group 4 get a single
Ask when making 5 did anyone in group 4 not get a single
if differnt undefine 5 and the people in group 4 that got a signle becomes group 5 go to state 1,2,3,4,5???
Ask when making 5 did anyone in group 1 get a single
Ask when making 5 did anyone in group 2 get a single
Ask when making 5 did anyone in group 3 get a single
if every one got a sigle then anser is 5
got to one of the folling State 1,2,3,3,4,5??? 1,2,3,3,4,5,5??? 1,2,3,3,4,5,5,5??? 1,2,3,3,4,5,5,5,5??? 1,2,3,3,4,5,5,5,5,5???

Problems with this idea:

Spoiler:

Once you get to:
State 1,2,3,4,4,4???
and some of 4 recives a signle but not all you no longer know the size of the new groups, but know enuff to carry one and if you remember what you do know about the group sizes you can ask the right question to find out every thing once you got every one in a group... I think.

Sorry about the spelling, I in a rush but wanted to get this idea on to the computer before my head leeked.

[John Midnight]

Sorry about possible errors as I am new here.

This is an unfinished strategy, but it combines most of the things I have read in previous posts:
The general idea is that every labeled prisoner knows the current number of labeled prisoners. Also after each labeling, prisioners will check wether they have all been labeled.

Spoiler:

Day 1:
-A (me) leave my light on, transmiting a "1". Everyone else will transmit a "0"
If I receive a "1", it's because I'm on my own. If not, one other prisoner will have
received my bit, becoming B.

Day 2:
A new prisoner has been labeled, so we have to check wether we are on our own. The method I'm describing will always work if my strategy could be extended endlessly.
-Prisoners A and B will send "1".

Day 3:
-Prisoners A and B will send what they received the previous day.

Day 4:

If there is only two prisoners, both A and B have received "1" both days.
If there is at least one more prisoner, both will have received "0" at least one day.
That means that only if both days A receives "1" there are two prisoners.
This could be easily extended, but requires N days to check wether the number of prisioners is N.
The problem I've encountered is labeling 1 and only 1 prisoner as number "N" for N>2. Here's how I sort of got past it for N=3, which is different from anything I've read, I have no extension for N>3 and the method itself has a couple of flaws, but I thing it's worth reading:

The email will say:
"(...). On day 4 I will randomly choose a number, witch will be either 0 or 1. I will wait that many days to send a "1". So that means either tonight or tomorrow night I will be sending my bit. The receiver of this bit will become "C" If, by any chance, B receives my bit then he will transmit it the following night. So beware, if you receive a bit on days 4, 5 or 6, that means you are "C".
The catch: the email is a lie. I will not choose randomly, I will always pick "0". Neither the warden nor the other prisoners knows that.

Okay, so when the warden reads this he will have no choice but to put B after A, so that if A sends the bit, it gets to B, otherwise "C" will clearly be identified and this could easily be extended and prisoners would eventually win and be freed. So he arranges the rooms so that on day 4 A sends the bit to B.
It's day 5, and the warden knows B is going to transmit the bit, as he clearly saw how A sent a "1" to B. So he's forced to put A after B, to stop B from designing "C". However, the email, as I said before, is a lie, I will actually send a positive bit both days.
So on day 5 both B and A send a bit, but since they are in adjacent rooms (the key is to lure the warden to put them together), only one aditional prisoner will receive a bit, since it's a valid day, he will become "C".
None will send any information on day 6.... clearly.
That way we succesfully ID a third prisoner, but this would obviously be much harder to do when wanting to label a forth one.
The new aportation was to lie in the email, fooling both prisoners and, most importantly, the warden, I hope it helps somebody

[skeptical scientist]

If there is at least one more prisoner, both will have received "0" at least one day.
That means that only if both days A receives "1" there are two prisoners.

Not so. B might have received a 0 both days, in which case A will receive a 1 both days, say there are two prisoners, and everyone will be executed.

The catch: the email is a lie. I will not choose randomly, I will always pick "0". Neither the warden nor the other prisoners knows that.

Okay, so when the warden reads this he will have no choice but to put B after A.

That doesn't work, because the strategy isn't guaranteed to work, as required by the problem statement. The warden isn't forced to do what you expect him to do in response to your strategy. He might put you before someone other than B on day 1, and then again on day 2, meaning there are two people designated C rather than 1. If the warden has a strategy that would defeat yours, you can't count on lies to fool him, because he may guess what you have in mind.

[John Midnight]

Not so. B might have received a 0 both days, in which case A will receive a 1 both days, say there are two prisoners, and everyone will be executed.

Maybe I have not explained that part properly.

Spoiler:

Say there are two prisoners A and B:
A sends a "1"
B sends a "1"
Since there is just the two of them both A and B receive a "1"
So on day 2:
Both A and B send a "1", because that's what they both received.
Since there is nobody else, both receive a "1". A has received "1" both days. So has B.

If there is one more prisoner C, or many more prisoners C, D, E, F....
A and B will both send "1".
At least one of them, (it could be both), will receive a "0".
Say A gets a "0". Then either B received a "1", or B received a "0".

If B has received a "0" then both A and B have received a "0". If B has received a "1" he will transmit a "1". But it's impossible for him to receive the one, as nobody is transmitting but him. So if we look at the day history of received data for days 2 and 3:
A = "00"
B = "10"

Yet I realize I made a mistake explaining it, a prisoner who has been labeled will send "1" his first night and send a "1" as long as he receives a "1", if he receives a "0", then he will always send a "0" (until the checking is over, that is)

[John Midnight]

Not so. B might have received a 0 both days, in which case A will receive a 1 both days, say there are two prisoners, and everyone will be executed.

Maybe I have not explained that part properly.

Spoiler:

Say there are two prisoners A and B:
A sends a "1"
B sends a "1"
Since there is just the two of them both A and B receive a "1"
So on day 2:
Both A and B send a "1", because that's what they both received.
Since there is nobody else, both receive a "1". A has received "1" both days. So has B.

If there is one more prisoner C, or many more prisoners C, D, E, F....
A and B will both send "1".
At least one of them, (it could be both), will receive a "0".
Say A gets a "0". Then either B received a "1", or B received a "0".
If B has received a "0" then both A and B have received a "0". If B has received a "1" he will transmit a "1". But it's impossible for him to receive the one, as nobody is transmitting but him. So if we look at the day history of received data for days 2 and 3:
A = "00"
B = "10"

Yet I realize I made a mistake explaining it, a prisoner who has been labeled will send "1" his first night and send a "1" as long as he receives a "1", if he receives a "0", then he will always send a "0" (until the checking is over, that is)

[Tnarg]

a differant anser

Spoiler:

setup:
Every one comes up with a unique id maybe zip code+house number+room number or somthing, this is converted in to fixed lenth binary

The idea is efor every one to build a list of every ones codes we start with the list of with one entry and that being a totaly unknowen code ie

List:
????????

We work out out upper limit (L) as been posted before and we use that to asked questions of the group, Every one is working from the same list so every one knows the question. (thats why we didnt add our own number to the list because that would need different people woule have different lists) Each time we ask a question every one that ansers yes sends 1 every one that ansers no sends 0 then for the next (L) days any one who anser yes or receved 1 sends 1 This way every one know if some one ansered yes (but we dont all know if some one ansered NO)


Main loop:
if all the numbers in the list have knowen bits then count them and thats our anser


remove the first number from the list and ask the following questions:

Dose any one have a number that matchs this and the next bit is 0
if the anser is yes add that number to the bottom of the list

Dose any one have a number that matchs this and the next bit is 1
if the anser is yes add that number to the bottom of the list

goto the stat of the loop

[bigbrainkid]

I figured out a very simple solution that requires no communication, only basic geometric skills.

Spoiler:

Using only the room, it is possible to figure out how many prisoners there are.

If the cells are situated in a ring around the center, you can imagine the prison as two circles that share a center, with lines(walls) that bridge the two.
Angle A is where outer circle meets the right wall, B being where outer meets left, C being right meets inner, and D being Left meets inner. Also imagine Angle E being the central angle of the circle.

Imagine a Trapeziod connecting those points, then cut that trapezoid In half to create two right trapezoids.
To find the size of the angles use the system:
360=180+x+y
180=2x+y

When x is mAngle B and y is mAngle D

Due to geometric law, Angle D is congruent to Angle E(And Arc AB), so divide 360 degrees by mAngle D, and you'll find n, the number of prisoners, including yourself.

Sorry for any typos, this was from my mobile.

[douglasm]

It's trivial for the prison to be designed to foil that, though. Just make the inner and outer walls polygons instead of circles, make all the rooms perfect rectangles, and make the walls between rooms thicker at the outer end.

Plus, that's circumventing the puzzle, not solving the puzzle. This is the Logic Puzzles forum, not the Engineering Problems forum.

[Sabin]

I would never have gotten this. Any of it. To be honest, trying to figure out a solution might make me wish for sweet death anyway...

[tomtom2357]

Just to clarify, when there is only one person, does your light switch turn on your own light? Thanks

[sfwc]

Yes, that's what I had in mind if there's only one prisoner.

[lordofthesnails]

Impressively complicated solution, but in practice:

Spoiler:

If we have 16 prisoners (not unreasonable), the warden is strong enough that we can spend a lifetime playing this game, and have narrowed it down to somewhere in the 15 - 32768 range. I suppose it's progress.

If we have 4 prisoners, and I understand correctly, we will know we have 4-8 prisoners (because the warden is horrible and won't let it be 3-4). Unfortunately, it's taken us 20 days to find out, and it takes over 10,000 years to decide on 4.

I love it!

[sfwc]

Impressively complicated solution, but in practice:

Spoiler:

If we have 16 prisoners (not unreasonable), the warden is strong enough that we can spend a lifetime playing this game, and have narrowed it down to somewhere in the 15 - 32768 range. I suppose it's progress.

If we have 4 prisoners, and I understand correctly, we will know we have 4-8 prisoners (because the warden is horrible and won't let it be 3-4). Unfortunately, it's taken us 20 days to find out, and it takes over 10,000 years to decide on 4.

Yes, that's right. I've been thinking for ages about whether there might be a quicker solution but I can't think of anything. Any ideas?

[rpenido]

Imagine the set of prisioners [x_0 (you), x_1, x_2, x_3, .. x_{n-1}]

For the warden strategy to organize prisioners:

First round: x_0 -> x_1
Second round: x_1->x_0
Third round: x_0 -> x_1
And so on..

The Warden can do that ? Will it break any kind of communication strategy ?

[t1mm01994]

Yes, the warden can do that. And there still is a solution to the puzzle, so appearantly, it won't break all..

[rpenido]

I got it.
Its impossible to the warden break the communication into small groups.

[t1mm01994]

You got a solution, or you understand the problem? In the former case, I'm very impressed.

[tomtom2357]

I have an idea which will make the problem harder. You are told that one of the other prisoners was injured when he came in, and he can only remember what happened the night before, and not any previous nights (assume that he still read the email and remembered that though). Is the problem still solvable?

[rpenido]

You got a solution, or you understand the problem? In the former case, I'm very impressed.

Understand the problem.
Im just trying to figure out if is possible to prove that there's no solution.

I didn't fully understand the solutions found. Ill take another look.

The Warden can prevent any message sent from YOU to pass to anybody but your adjacent cell prisioner (x_1). But (x_1) still spreading his own message and YOU (x_0) still receiving messages from someone. Is this assumption right ?

[t1mm01994]

If by message you mean a light on or off, yes.

[tomtom2357]

So, can anyone solve my problem?

[skeptical scientist]

So, can anyone solve my problem?

Do you have a solution, or are you just making up random problems for other people to solve?

[tomtom2357]

I'm just making up a random problem that is harder than the original problem. I do that sometimes. Here is another, one cell has a delayed signal such that if the switch is on one night, it will be on the next night (in the next cell as always). Can you solve that!

[mathmaniac31]

it might be useless now, but i had a method for checking up til N<=4 that might be able to extend

Spoiler:

day 1
lets say you are A, everyone else is B
everyone sends 1
if A receives 0, A answers with N=1
N>=2

day 2
person who receives 1(other then A) becomes B, everyone else becomes C
A and B send 0, C sends 1

day 3
either A and/or B receive 1 if N>=3, and if they do they send 1
AB send what they just received, C sends 1
night 3
if both A and B receive 0, N=2 either one can call
else everyone received 1


N>=3

day 4
A and B send 0, C sends 1
if 3 people, A xor B gets 1, C gets 0 (100 or 010)
if 4 people, if A or B gets 0, one C has to get a 1 (1010 or 1001 or 0110 or 0101)
if C gets a 1, he says N=4
otherwise, A and B got a 1. (1100)
possible received is (100,010,1100)

day 5
ABC send what they just received
if 4 people, if A or B receive 1 again in a row, N=4
else it has to be (0011)
possible received in day4/day5
(100/010, 100/001, 010/100, 010/001, 1100/0011)

day 6(nothing needs to be sent)
if A,B,or C got 0s on both day 4 and day 5, then N=3
because for N=4, they had to alternate

day 7
only choice left is N=4
if no one called yet, N=4

what i found interesting, is that this strategy could use recursion to extend for N>4 to some degree.
if we assume max N is 5, if we can find a strategy to differ 4 from 5 to that person C in X days, we could insert the method between days4/5 and days 5/6 and again after day 7. making it days 1 to 4, method that takes X days, X+5, method that takes X days, 2X+6 to 2X+7, method that takes X days. This would complete in 3X+7 days.

Its important that if a method to differentiate between 4 and 5 days takes Y days to inform one person that it is 5 people and not 4, you could send that info to everyone else in another 5 days by spending 5 days having that person send 1 and everyone who sees a 1 permanently send 1. If at the end everyone sees 0 it is N=4, if at the end everyone see 1 it is N=5. this could simulate a to see if someone called a warden in a subroutine(that cant actually call the warden because lower numbers have not yet been dealt with).

[tomtom2357]

I have another incomplete idea for an inductive solution along the same lines as mathmaniac (I also use his notation for switching lights on or off, it reduces ambiguity). My idea is:
You are person number 1 (P1).
1st night: P1 sends 1.
If he receives 1 then N=1.
If not, then whoever receives the one is P2.
N>1:
2nd night: P1 and P2 both send 1. If N=2, then P1 and P2 both receive 1. If not, then at least one of them does not receive 1.
3rd night: If either P1 or P2 did not receive 1, then they do not send out 1. If they do receive a 1, then they send out a 1.
Now even if P1 was behind P2 (or vice versa) and P2 (or P1) receives a 1 on the 2nd night, then they are the only one sending out the signal and so they cannot receive a one on the 3rd night unless there are only 2 people. So if P1 receives a 1 on the 3rd night, then N=2. If not then N>2.
N>2:
Here I create a hypothetical person P3 to solve this. P3 is the (hypothetical) person who receives a 1 on the 3rd night. Now, if there are three people, then either P1 was behind P2, or vice versa on the second night. Therefore one of them would send out a signal on the 3rd night (in the case where N=3). However, if N>3, then P1 and P2 do not have to be next to each other on the 2nd night. My main problem here (that I have not solved) is that P1 or P2 could be P3 if the warden was clever. If you can solve that problem, then post it here!

[douglasm]

If N>=4, the Warden can trivially arrange for there to not be a P3 at all in that strategy.

[tomtom2357]

Here I create a hypothetical person P3 to solve this. P3 is the (hypothetical) person who receives a 1 on the 3rd night. Now, if there are three people, then either P1 was behind P2, or vice versa on the second night. Therefore one of them would send out a signal on the 3rd night (in the case where N=3). However, if N>3, then P1 and P2 do not have to be next to each other on the 2nd night.

I have said this already, but what I need is a solution to the problem that P1 or P2 might be P3 if the warden was clever.
Also, it might be fun to find out how long (assuming optimal email) it will take you to find out if x<=n or not and if so, then what x is. Let us call this new function f, f(1)=1,f(2)=3, I am working on f(3).

[sfwc]

one cell has a delayed signal such that if the switch is on one night, it will be on the next night (in the next cell as always). Can you solve that!

Yes.

Spoiler:

It is still possible for the prisoners to succeed. We can find a strategy for them by slightly modifying the strategy for the earlier problem. In fact, I've just taken skepticalscientist's solution and made a few small changes. First of all, note that the procedure for collectively finding an upper bound on the number of prisoners, the ping procedure, and the group division procedure all work with barely any modification.

We will need a modified version of the Lemma:

Lemma: Suppose you have unknowns a₁ to a_n, except a₁=1. Moreover, for every nonempty proper subset A of {a₁, ..., a_n}, there is another subset B with B\A nonempty, a number u which is either 0 or 1, and an equation of the form "sum of A equals sum of B plus u", and the resulting system of equations is solvable in the positive integers. Then the system of equations has a unique solution in the positive integers.

Proof: Suppose for a contradiction that we have two different solutions a₁…a_n and b₁…b_n. Then without loss of generality there is some i such that b_i < a_i. Choose i such that b_i/a_i is minimal, let this minimal value be k (so k < 1), and for each j let c_j = (b_j - k.a_j)/(1-k), so the c_j satisfy the same equations and are all nonnegative rationals. Let A be the set of j such that c_j = 0. A is nonempty, since it contains i, but A doesn't contain all the numbers up to n since the two solutions are different. So by hypothesis we can find another set B and a number u equal to 0 or 1 with B \ A nonempty and such that the sum over j in B of the c_j plus u is equal to the sum over j in A of the c_j. But the left hand side of that equation is strictly positive, and the right hand side is 0, which is the contradiction we wanted.

Now we can sketch out the prisoners' strategy.

Subsequently to initially establishing an upper bound and performing initial group division, the strategy consists of a sequence of rounds. Each round starts with the prisoners to groups G1...Gn by the group division procedure. The round will result in one of two outcomes:
1. The prisoners obtain a system of equations for the sizes of the groups which has a unique solution by the lemma. They can therefore compute the size of each group, and the total number of prisoners. (VICTORY!)
2. The prisoners obtain a new set of group memberships, such that the new memberships form a refinement of the previous set (each group is either the same as a group from the previous round, or is a proper subset of a group from the previous round, and at least one group from the previous round is split into more than one group).
Since a refinement results in an increase in the number of groups, which is bounded by the total number of prisoners, outcome 2 can only happen finitely often, and then outcome 1 must happen, resulting in victory.

Here is the round procedure:

Code: Select all

for (X a nonempty, proper subset of {G_1...G_n})
{
   nobody flicks their switch (1 night)
   everyone in a group in X flicks their switch (1 night)
   the ping procedure is run to determine whether the `delayed' switch was in the on or off position on the night when everyone in a group in X flicked their switch
   for (i=1 to n)
   {
      everyone in group i who received one of the flicks from X pings (B nights)
   }
}

perform new group divisions (call the group division procedure)


If the number of groups in the new division is more than the the number of groups in the old division, we're in outcome 2. Repeat the round procedure with the new groups. If the number of groups in the new division is the same as the number of groups in the old division, we know that for each group G, every member of G experienced exactly the same history during the round. That means when everyone in a group in X flicked their switch, either everyone in G received a flick, or nobody in G received a flick. Therefore, if Y is the set of groups which received a flick from X, we know that the total number of people in a group in Y is almost the same as the total number of people in a group in X. The only way it could differ is if the `delayed' switch was flicked when everyone in a group in X flicked their switch, in which case we know that there is just one more person in a group in X than in a group in Y. Moreover, we know that Y isn't the same as X. Therefore, this gives a system of equations as in the lemma, which the prisoners can solve to find the size of each group, hence the total number of prisoners.

You are told that one of the other prisoners was injured when he came in, and he can only remember what happened the night before, and not any previous nights (assume that he still read the email and remembered that though). Is the problem still solvable?

Yes.

Spoiler:

In fact, we can apply the solution above. If the prisoner with memory loss always sends the same message he received the previous night, then he simulates a switch with a delay.

[tomtom2357]

Is there an inductive solution to the (original) problem?

[PtrN]

I see many complicated strategies. I think I have a simpler one. This one doesn't assume anything, and doesn't require people to be able to send signals through the light other than a simple on/off state.

Spoiler:

1) Every day when a prisoner enters a cell, or after communication, they reset the switch to the "off" position
2) One prisoner, myself, will be the initiator
3) When electricity is announced as being available, I will flip my light switch
4) The other prisoners, when their light goes off, will flip their switch

Thus the number of days between when I start the communication and when my lights turn on is the number of prisoners.

[skeptical scientist]

I see many complicated strategies. I think I have a simpler one. This one doesn't assume anything, and doesn't require people to be able to send signals through the light other than a simple on/off state.

Spoiler:

1) Every day when a prisoner enters a cell, or after communication, they reset the switch to the "off" position
2) One prisoner, myself, will be the initiator
3) When electricity is announced as being available, I will flip my light switch
4) The other prisoners, when their light goes off, will flip their switch

Thus the number of days between when I start the communication and when my lights turn on is the number of prisoners.

You saw that the warden can rearrange the prisoners every day, if he wishes, right? That means your strategy won't work, because you could have e.g. three prisoners ABC, with A the initiator, but A communicates to B, then B is placed before A so B sends the signal back to A after only 2 days, even though there are 3 prisoners.

I think that every solution is going to have to be somewhat complicated, because of the constraint that the strategy has to work even when prisoners can be rearranged every day. There may be a simpler solution than the one I gave, however.

[tomtom2357]

An inductive solution would (probably) be easier to understand though!

[skeptical scientist]

An inductive solution would (probably) be easier to understand though!

Which part of my solution don't you understand?

[tomtom2357]

An inductive solution would (probably) be easier to understand though!

Which part of my solution don't you understand?

I thought that your solution was solving a class of equations to find the correct number of prisoners, and that is not inductive.

[skeptical scientist]

An inductive solution would (probably) be easier to understand though!

Which part of my solution don't you understand?

I thought that your solution was solving a class of equations to find the correct number of prisoners, and that is not inductive.

That is one step in my solution, yes. When you said that an inductive solution would be easier to understand, I assumed you meant that you found my solution hard to understand, and was wondering what was hard to understand, so that maybe I could clarify.

Also, to be honest, I'm not quite sure what you mean by an "inductive" solution.