Prisoners in Limbo

[Ermes Marana]

20 people are sent to Limbo. Before they can go to heaven, they must complete the following task: At noon each day, one person is chosen (uniformly at random) to go to a room with 2 switches, each with 2 states.They must switch exactly one switch. The nature of the switches is unknown beforehand (no "left and right, on and off" they can agree on), they may not be identical, and they may not appear the same to different prisoners (for example, prisoners may see colors differently or the room might always flip upside down for some of them) but will always be the same for the same prisoner.

Eventually, a prisoner must state that not only has everyone been to the room, but the last 20 people sent to the room included all 20 prisoners. If they are correct, everyone goes to heaven. If they are wrong, everyone goes to hell.

The prisoners know the above scenario. Before the task the prisoners have time to gather and make a strategy, but during the task they cannot communicate other than by the switches. They are able to keep track of time and know when the task will begin.

How can they go to heaven with probability 1?

[skeptical scientist]

Some very similar puzzles have already been posted (in some cases, long ago!)
http://forums.xkcd.com/viewtopic.php?f=3&t=73
http://forums.xkcd.com/viewtopic.php?f=3&t=13669
http://forums.xkcd.com/viewtopic.php?f=3&t=69986
It's true that the other puzzles talk about one switch with agreed "on" and "off" positions, rather than two switches without no agreement about which orientation is "on".

Assuming the two switches are identical,

Spoiler:

they can just treat both switches in the same orientation as "on", and in different orientations as "off", and carry on as in the other solutions.

I'll have to think about what the prisoners can do if the switches are not identical.

[tomtom2357]

Since the solution has already been posted there, I will pose a more difficult problem. This is identical to the original except that you don't know how many people there are. Has anyone here solved that before? If you want to make it even harder, the prisoner also has to say how many prisoners there are.

[Ermes Marana]

Assuming the two switches are identical,

Spoiler:

they can just treat both switches in the same orientation as "on", and in different orientations as "off", and carry on as in the other solutions.

The switches may not be identical, so this doesn't work.

I don't see how it would work even if they were identical though since

Spoiler:

you are forced to switch exactly one switch, so if they were the same you would have to make them different, and vice versa.

[skeptical scientist]

Hmm, read "must" as "may".

[mfb]

Since the solution has already been posted there, I will pose a more difficult problem. This is identical to the original except that you don't know how many people there are. Has anyone here solved that before? If you want to make it even harder, the prisoner also has to say how many prisoners there are.

Please, find a solution for your own problems before you present them as puzzle. This is not limited to this thread.
This is impossible, as for every switch state, there may be one person who never visited the room. As this person did not influence anything in the setup, it is not possible to know about it.


As for the original puzzle:

Spoiler:

Each prisoner can define a parity of the switches (equivalent to "in the same state" and "in different states"). They know that it has to change each day, so by counting days they know the initial parity at day 0 as soon as they enter the room once. Define this as parity 0 (and the other as 1). Each day, the prisoner has the choice between two states, which he names as "A" and "B". So we have the following 4-state-system:
A0 A1
B1 B0
Each prisoner has to make a vertical or horizontal transition in this system. There are 4 ways to assign A and B to the states, it is always along rows or columns. And here is where I am stuck. It is not possible to transmit information reliably over more than 1 day without an agreement about the definitions of A and B - or at least I do not see how. Assuming all agree what A and B are: Divide the time in slices of 20 days each, switch it to A at the beginning of each slice. If a prisoner visits the room twice in this interval, it is switched to B. If it is still on A after 20 visits, call out that in the last 20 days, all prisoners visited the room. Assuming random visits, this tactic is a factor of ~20 away from a perfect communication, but 20!/20^20 is a small number anyway (~100.000 years).

[Yakk]

An amusing solution:

Spoiler:

The prisoners give themselves numbers from 0 to 19.

There are two orientations of the switches. When they enter the room, they pick an orientation.

They thus generate 2^20 different states, which describe a bit mask that determines if they are to "reverse" their orientation. We then play 2^20 games, with possible resets of each.

On each of these equivalence classes, they apply the mask, extract our bit (corresponding to our number), and play the game with that as our assumption.

We know the initial state of the switch, so we know that it swapped each day, so we can cancel that out, and treat the two remaining states as 0 and 1.

The game we play in each of the sub games is "pass the mark". The first time you see the switch as off, you "drop your existence" onto the switch and set it to 1. In every other situation, you leave it alone.

Player number 0 acts differently. Player number 0 picks up 1s, and converts them to zero, and leaves zeros alone. Player number thinks the game is over if she has picked up at least 19 1s.

On the particular 2^20 game that everyone happens to agree with the orientation, Player number 0 gets 19s only if every other player has been in the room.

On the other games, Player number 0 sometimes gets a random message sent to him in the "incorrect" games, as there is at least one other player who, seeing a signal, will try to leave it alone, and in doing so send Player number 0 a 1. If not, then Player number 0 encoding agrees with every other player, which is a contradiction. So with probability 1, player number will pick up at least 19 1s.

So when Player number 0 has picked up at least 19 1s in every game, she can say "we win".

Now, for this to work, what we do is we arrange for increasingly long blocks to play a copy of one of the 2^20 games. Everyone knows when these games begin, so they can ignore any signal that shows up to the first person to walk into the room on the first turn of the game. When we start a new copy of one of the 2^20 games, we forget all previous state that the game had "last time". As the "pass the 1s" has a 100% chance of winning in an infinite length game, and wrong games as well, the people in limbo will eventually escape.

As an optimization, Player number 0 can remember if they won in one of the 2^20 games in the past, and when there has been at least 1 victory in each of the 2^20 games, say they have won.

A rough estimate of how long this takes is 2^20 times the time it takes to win the "pass the 1s" game, or a million times longer -- assuming that the failed games are at least as fast as the winning game (which I don't know). If we ramp up the length of the games fast enough (say, exponentially), then the time spent on the failed games will be trivial compared to the time spent on the winning games.

We might be able to drop player 0s bit, but it is only a factor of 2, which is free.

[mfb]

I cannot follow your arguments.

Spoiler:

The first thing is that the assignment of 0/1 has 4 possible ways, as it is arbitrary for both parities. So in fact you have 4^20 different "masks".
The second problem is that there is no way to define which "mask" is used by other players. "00000...." is a nice definition, but how do you know how this is executed by others? To put that in a concrete question: Which switch do you turn in order to "leave the 0"? Maybe the answer to this question can explain your further arguments.

How do you track data for the event "in the last 20 days, every prisoner visited this room"?

[Yakk]

I cannot follow your arguments.

Spoiler:

The first thing is that the assignment of 0/1 has 4 possible ways, as it is arbitrary for both parities. So in fact you have 4^20 different "masks".
The second problem is that there is no way to define which "mask" is used by other players. "00000...." is a nice definition, but how do you know how this is executed by others? To put that in a concrete question: Which switch do you turn in order to "leave the 0"? Maybe the answer to this question can explain your further arguments.

How do you track data for the event "in the last 20 days, every prisoner visited this room"?

Damnit. I solved "every prisoner has been in the room in the past", not "in the last 20 days, every prisoner visited this room". D'oh.

Oh well:

Spoiler:

I'll try to abstract it somewhat.

There are games, which have rules. There are instances of games. We build a (finite) population of games such that the only way we could win an instance of every game is if everyone has visited the room, and we will win an instance of every game with probability one given infinite game length for each game. We then proceed to play exponentially growing length instances of every game until we win each game.

---

In this case, "a game" is described by a mapping that, for each player, maps what they see when they enter the room to a 0 or 1, and maps what they should leave when they leave the room to say 0 or say 1 to the next person.

We enumerate all such games (or a sufficient subset). We then proceed to play increasingly long instances of each game.

In each given instance of a game, we play "pass a 1 to player 0", as is standard for the lightbulb problem. In many cases, this doesn't actually "work", because we disagree with what the messages we are sending mean.

Now, as we are playing all versions of the game, in exactly one of them, everyone agrees on what the lightswitches mean. We don't know which game has this property, but there is one such game. We can guarantee that this game won't end with a win state unless we win it. So we can guarantee we won't announce early.

As for "will we eventually announce", the idea is that we arrange our game switch meaning assignments such that we'll send spurious signals that player 0 will pick up accidentally with a non-zero probability. This is the part I hand-waved over in my previous post, and could contain errors.

---

Now, when you enter the room, you know if there has been an even or odd number of turns before you. So the state of the switchs is limited to two possible states in either case. There are two different ways we can assign these two different states to the values 0 or 1. This means that the number of different interpretations that the players could assign to the switches is 2^20. In exactly one of these everyone will agree with what the switches mean, regardless of when they enter the room.

In every other case (the other 2^20-1 cases), someone will disagree with Player0 on what 0 and 1 mean.

What more, I believe because they always toggle a switch when they leave the room, when they try to "leave the switch alone" they'll actually toggle it (in the perspective of player0)!

Ie, suppose player 1 and player 0 disagree about what arrangement is a 0 and which is a 1.

So if player0 walks into the room, leaves a 0.
Player1 walks into the room, sees an X (I don't care really). Tries to leave it alone.
Player0 walks into the room next, and sees a 1, because what Player1 thought of as "leaving it alone" is an operation that Player0 interprets as "flip the switch". Player0 picks up the 1, leaving a 0.

If this is true, then as the length of the game goes to infinity, the probability that Player0 manages to pick up (at least) 19 1s goes to 1.

What I do need to do is make sure that my (intuitive) belief that the above is true actually holds.

Sigh.

[mfb]

Hmm... this actually leads me to a partial solution for the initial problem. But it has an absurd expectation value and memory requirement.

Spoiler:

Make slices of 20 days each. Each prisoner defines his own way to assign "0" and "1" to the switch states both for even and uneven days as soon as he first visits the room. I'll play it safe and regard it as 4^20 different setups.
Prisoner 0 now flips his assignment for every slice of 20 days, with a cycle of 4 slices (80 days): Day 1-20 he uses one, 21-40 a second one, 41-60 a third one, 61-80 the remaining one. At day 81, he begins with the first assignment again.
Prisoner 1 flips his assignment every 4. slice, with a cycle of 16 slices.
Prisoner i flips his assigment every 4^i slice.

So every 4^20 slices of 20 days, all assignments are used within a slice of 20 days.

Strategy for each player:
- At the first day of a slice, set 1.
- At days 2-19: If you visit the room for the second time within the slice, set it to 0, otherwise set it to the value it had when you entered.
- At day 20: If you see a 0 or were in the room before in this slice, do nothing. If you see a 1, write down the number of the slice (mod 4^20) somewhere in your cell. You know that the assignments were mismatched OR all other 19 prisoners visited the room in the 19 days before.

There is at least one setup where the assignment is correct. So as soon as any prisoner wrote down all freaking 4^19 combinations (~275 billions) of the other prisoners (because he was last and saw a 1 with this combination), he knows that one of this "1" was due to all 20 different prisoners in a row in the room.

However, they still do not know on which day it happened.

[Qaanol]

Here’s a couple thoughts:

Spoiler:

If they are ever able to agree on one particular switch as A and the other B, the problem reduces to the one-switch problem with the choice of whether to flip it.

If at any time a person enters on day N and also on day N+2, that person knows what switch was flipped on day N+1. If each person picks an arbitrary switch and flips it every time, and changes which switch they are flipping only when they enter on days with one day in between, in which case they change to start flipping the switch that was flipped in between those days, then eventually with probability 1 everyone will end up all flipping the same switch. Unfortunately this has no upper bound on how long it takes, and provides to mechanism to stop once everyone is on the same switch.

[Yakk]

Spoiler:

I cannot think of a way to agree on a switch assignment with probability 1. It might not be possible?

Now, my solution reduces the "you must switch one of two switches" to the one-switch "you may switch it" problem, with the fact that for each person the orientation of the swtich is unknown. I don't know if this reduction is a good idea -- can we show it is just as strong?

[mfb]

Spoiler:

Well, no system can give a probability of 1 to get free within a certain time.
But I think I found a solution which ends with probability 1.

A small modification to Qaanols n+2-idea: Prisoner 1 will stick with his interpretation. He defines A and B and switches only A. He also defines an "off" position of B for his personal use.
So after an unknown (random) amount time, all prisoners will use the definition of A.

Now we need a protocol which can work only if all prisoners agree on one switch and fails otherwise. Then we can insert "validation sections" of fixed length where this is tried from time to time to see if all are aligned. If a validation section fails, the n+2-method to align the prisoners just continues like before and another validation section comes some time later.

Now, define validation sections of 62 days length. Only prisoner 1 may end the puzzle and only prisoner 1 learns something inside, so I can require that he enters the room at all uneven days from 1 to 41 and at day 62 and not on other days. Otherwise, he knows that the protocol failed and all switch switches are irrelevant.
At days 1 to 41, prisoner 1 always ensures that B is "off".
All other prisoners follow this rule: Switch A (if defined for you) if you are in the room for the first time inside the validation section, switch B otherwise. Remember the position of switch B as "off".
If and only if all prisoners agree on the definition of A and every prisoner visits the room once in (2,4,...,40), prisoner 1 always sees switch A switched. In addition, he is now sure that all prisoners know the "off" position of B.

From day 42 to 61, all 19 prisoners follow this rule: If you enter the room the second time and see switch B as "off", switch it to "on". In all other cases, switch A.
On day 62, if prisoner 1 knows that all agree about the definition of A and all know the "off"-position of B and sees B still as off, he knows that at days 42-61, all 19 other prisoner visited the room and ends the game.
These parts have to lie in the same validation section to ensure the correct definition of "B is off" for all prisoners. Maybe there is a better way to handle this, but I don't care about expectation values at the moment. A back-of-the-envelope calculation shows a probability of (19!)^2 / 20^62 ~=3*10^(-47) that the validation section succeeds, if all prisoners agree on the definition of A.

Do you see any mistakes in this solution?

[Ermes Marana]

Spoiler:

Well, no system can give a probability of 1 to get free within a certain time.
But I think I found a solution which ends with probability 1.

A small modification to Qaanols n+2-idea: Prisoner 1 will stick with his interpretation. He defines A and B and switches only A. He also defines an "off" position of B for his personal use.
So after an unknown (random) amount time, all prisoners will use the definition of A.

Now we need a protocol which can work only if all prisoners agree on one switch and fails otherwise. Then we can insert "validation sections" of fixed length where this is tried from time to time to see if all are aligned. If a validation section fails, the n+2-method to align the prisoners just continues like before and another validation section comes some time later.

Now, define validation sections of 62 days length. Only prisoner 1 may end the puzzle and only prisoner 1 learns something inside, so I can require that he enters the room at all uneven days from 1 to 41 and at day 62 and not on other days. Otherwise, he knows that the protocol failed and all switch switches are irrelevant.
At days 1 to 41, prisoner 1 always ensures that B is "off".
All other prisoners follow this rule: Switch A (if defined for you) if you are in the room for the first time inside the validation section, switch B otherwise. Remember the position of switch B as "off".
If and only if all prisoners agree on the definition of A and every prisoner visits the room once in (2,4,...,40), prisoner 1 always sees switch A switched. In addition, he is now sure that all prisoners know the "off" position of B.

From day 42 to 61, all 19 prisoners follow this rule: If you enter the room the second time and see switch B as "off", switch it to "on". In all other cases, switch A.
On day 62, if prisoner 1 knows that all agree about the definition of A and all know the "off"-position of B and sees B still as off, he knows that at days 42-61, all 19 other prisoner visited the room and ends the game.
These parts have to lie in the same validation section to ensure the correct definition of "B is off" for all prisoners. Maybe there is a better way to handle this, but I don't care about expectation values at the moment. A back-of-the-envelope calculation shows a probability of (19!)^2 / 20^62 ~=3*10^(-47) that the validation section succeeds, if all prisoners agree on the definition of A.

Do you see any mistakes in this solution?

I think that works. That's the same basic idea I used.

I think Yakk's idea also works with a modification:

Spoiler:

The prisoners give themselves numbers from 0 to 19.

There are 4 ways to define even-day "off" and odd-day "off", so 4^20 ways for all the prisoners to do so. The prisoners will repeat a sequence of 4^20 games. Each prisoner divides the games into blocks of 4^n and shuffles through the possible definitions on these blocks. Thus every combination of definitions is used on exactly one game.

Each game is 21 days long. Whoever goes in on day 1 sets it to "off". After that, if you come in for the 2nd time and find it "off" turn it "on", otherwise leave it the same. On the game where everyone agrees, the only way the day 1 prisoner can come back on day 21 and find it "off" is if they won.

But unfortunately, he must have already crossed off every other game as a disagreement. If I am the day 2 prisoner and I disagree with the day 1 "off", I can cross out the game. We can add one day between complete runs of the 4^20 games so the initial days of each game will fall on both odd and even days. Thus every prisoner can cross off every game where not everyone agrees.

[mfb]

In that case, we already have two solutions. And both need an awesome amount of time.

Spoiler:

I would like to see a cell wall with 4^20 fields getting crossed out one by one

A possible speed-up of your solution: We have to rule out all but one interpretation before there is any chance to be done. So for the first ln(4^20)*4^20 (or whatever) days, just communicate switch interpretations: Everybody sets it to "off" according to the current map. That allows to rule out combinations much faster, as every day one prisoner (and not only the second in 22 days) can perform a check.

[Yakk]

Ah yes...

Spoiler:

We build games that are two-fold. First, they are "determine if we disagree on the assignment of switches". If we disagree on the assignment of switches, we consider the game "won" -- or, more accurately, we'll call that game "sour".

Second, there is the "determine if exactly one person has been here in the last 20 days" victory.

If we have determined that we have a disagreement on every game but our own (that they are sour games), and we get a victory on the remaining game, then we know that we have won the entire game.

Now, as for disagreements, we can do the "on even days send a 1, on odd days send a 0" pattern. If we ever see something that disagrees with our assumption, then we know that there is a disagreement. (Edit: actually, a block where everyone sends 0 is sufficient, as in my system there is only 2-fold symmetry in what the switches mean)

Amusingly, we might be able to speed up this system by lieing sometimes once we have determined there is a disagreement. As a simple solution, imagine that once we have determined that game N is in disagreement about the assignment of bits, we start sending random messages in the synchronization period for game N. This means whomever goes next has a 50-50 chance of also getting a desychronization. Which would allow desychronization to spread exponentially through the population.

For a n+1 length block of synchronization, with exactly 1 bit in our switch assignment being "off", and nobody knowing that there is a problem, there is a (19/20)^n chance that the person with the wrong bit will broadcast the fact that their bit is wrong to someone else. If they first learn that their bit is wrong, there becomes a (19.5/20)^n chance they'll broadcast their error to another player. That is worse, so let us be conservative.

Suppose block lengths of 30 -- that is long enough that even in the worst cast, a rebroadcast is more than 50% likely per block.

Each successful broadcast of error spreads it to another prisoner. And the chance of a broadcast keeps on going up for a bit, until the problem is reaching the last person who doesn't know the game is a sour game.

This has to go on over all 2^20 games (I think we can do this with two switch assignments per game, really!), until we reach the point where at least one player knows that 2^20-1 games are sour, and has a hope to win the actual game that isn't sour.

I cannot think of a way to safely communicate "between games" which games are sour without the receiver already knowing that 2^20-1 games are already sour, and that would be the goal of such communication. Or would it?

Once we have at least one player who has the sour-state of the entire system, we need a ridiculous number of repeats of the final game to clean things up. It might be an interesting idea to add in a game whereby we determine if everyone knows that every game except for one is sour!

... that is the "has everyone been in the room" game! If instead of playing the "has the last 20 games contained every player" from the start, we play a continuous set of 20 games of "send a 1 to the counter if you know that every game except for this one is sour", where we have all 20 players counting. Then somehow transition to playing the "has every 20 players been in the room" mode?

This gets tricky, because we need to both know that we know, and that everyone else knows. Or maybe we don't. Once we know that all games except for 1 are sour, we stop caring about what we pick up in the sour games. This means that other people could broadcast nonsense. So what we do is we wait until we personally know that everyone else knows all games but 1 are sour, then we change our broadcast strategy in this now known to be dead space, and start sending that we have changed our broadcast strategy.

When we know that everyone else has changed their broadcast strategy in the dead space, we start paying attention to inputs, as if they aren't random data.

This lets us transition the sour game bandwidth from finding out if the game is sour, to another game. Such as packed "has each of us been in the room in the block of 20 days" games.

Admittedly, the low odds of that happening sort of dominates any speedup in how often we play it. Still, I suspect it might be relatively expensive to get to the point where one person knows that all but one game is sour, and allocating more bandwidth to that determination (and less to the "block of 20 games") we might solve the problem faster.

On the other hand, if we split the bandwidth between blocks of 20 games, and determining that all but one game is sour, 50-50, such a speedup is limited by a factor of 2 (approx -- the seam between the blocks is somewhat wasted, but can be arranged to be minimal). And at the scales we are talking about, a factor of 2 isn't all that much.

Oh well -- I did find it interesting that we might actually be able to transition the use of blocks of bandwidth!

As for switch assignments:

Spoiler:

When we enter the room for the first time, we know if the day is even or odd.

There are two switches, and they can be in one of two positions. I'll call the switches A and B, and denote the two positions as upper vs lower case letters. So Ab is a switch position.

AB Ab aB ab are the 4 possible switch states. However, we know that half of these are impossible once we have first entered the room on even or odd days. This leaves only two switch positions that can occur on an even, or on an odd, day.

WLOG, we'll make them AA ab on an even day, and Ab aB on an odd day.

... bah, gotta go. It isn't looking good -- we might need 4 different possible switch interpretations instead of just 2. Bah -- a factor of a million slowdown sucks.

[Qaanol]

Spoiler:

Well, no system can give a probability of 1 to get free within a certain time.
But I think I found a solution which ends with probability 1.

A small modification to Qaanols n+2-idea: Prisoner 1 will stick with his interpretation. He defines A and B and switches only A. He also defines an "off" position of B for his personal use.
So after an unknown (random) amount time, all prisoners will use the definition of A.

Now we need a protocol which can work only if all prisoners agree on one switch and fails otherwise. Then we can insert "validation sections" of fixed length where this is tried from time to time to see if all are aligned. If a validation section fails, the n+2-method to align the prisoners just continues like before and another validation section comes some time later.

Now, define validation sections of 62 days length. Only prisoner 1 may end the puzzle and only prisoner 1 learns something inside, so I can require that he enters the room at all uneven days from 1 to 41 and at day 62 and not on other days. Otherwise, he knows that the protocol failed and all switch switches are irrelevant.
At days 1 to 41, prisoner 1 always ensures that B is "off".
All other prisoners follow this rule: Switch A (if defined for you) if you are in the room for the first time inside the validation section, switch B otherwise. Remember the position of switch B as "off".
If and only if all prisoners agree on the definition of A and every prisoner visits the room once in (2,4,...,40), prisoner 1 always sees switch A switched. In addition, he is now sure that all prisoners know the "off" position of B.

From day 42 to 61, all 19 prisoners follow this rule: If you enter the room the second time and see switch B as "off", switch it to "on". In all other cases, switch A.
On day 62, if prisoner 1 knows that all agree about the definition of A and all know the "off"-position of B and sees B still as off, he knows that at days 42-61, all 19 other prisoner visited the room and ends the game.
These parts have to lie in the same validation section to ensure the correct definition of "B is off" for all prisoners. Maybe there is a better way to handle this, but I don't care about expectation values at the moment. A back-of-the-envelope calculation shows a probability of (19!)^2 / 20^62 ~=3*10^(-47) that the validation section succeeds, if all prisoners agree on the definition of A.

Do you see any mistakes in this solution?

Nicely done, mfb. There’s one mistake, but it’s so minor as to be scarcely worth mentioning.

Spoiler:

The validation sections should be 59 days long.

Prisoner 1 enters on odd days 1, 3, …, 39, which leaves 19 even days for the other prisoners in between. Then prisoner 1 enters again on day 59, which leaves a 19-day gap for the other prisoners in between.

[mfb]

Hmm...
Let's call it a solution for 21 prisoners and modify 20->21 and 19->20 .
I re-used prisoner 1 as one of of the other prisoners, which is pointless.

[Yakk]

On mapping switches to 0 or 1:

Spoiler:

When we walk into the room, we pick an alignment (up-down direction) for the two switches. We know how many times the switch has been toggled since day 0, so we can pick an alignment such that they agreed with each other (had the same up-down value) before any person entered the room.

We also give the switchs letters (A and B) that we never alter.

When we enter the room on even days, the switches are in position AB or ab (where lower case represents the switches being down).
When we enter the room on odd days, the switches are in position Ab or aB.

So, on any given day, the value of the A switch determines the value of the B switch.

Given the above information, there are exactly two ways we can assign the value of the A switch to a 0 or 1 value. And these correspond to assigning the opposite value to the B switch.

So, suppose we have a number from 0 to 2^20-1, and we have an index from 0 to 19. We examine our index bit. If it is 0 we interpret the "up A" as 1, and the "down A" as 0. If it is 1 we interpret the "up A" as 0 and the "down A" as 1.

This applies both when we read and when we write. So if our index's bit is 0, and we had a aB and we want to write a 0, we leave the room with ab written.

I claim that there is always an 20 bit number that allows the players to communicate as if they had a single switch with a lightbulb attached.

Spoiler:

We enumerate the assignments from switch position to meaning. Let E be this enumeration.

A check sequence is a way to determine if the enumeration is a "sour" one (one in which we do not agree with everyone else's values). In a check sequence, if we do NOT know that the enumeration is sour, we write a 0 at all times. If we DO know the enumeration is sour, we write a 0 or 1 randomly.

We learn that an enumeration is sour by reading a non-zero value when we read during a check sequence (except, of course, at the first step of the check sequence).

If we have exactly 1 person that disagrees the other people for an enumeration, the worst case is that this one person is the first to find out (because they go from always broadcasting nonsense to only doing so half of the time). From then on, the number of people who know that the enumeration is sour grows.

Each time someone reads a check signal there is an (20-N)/20 * (N)/20 chance that they will learn that the enumeration is sour, assuming that N people know that the enumeration is sour, which equals (20N - N^2)/400. The min value of this that we care about is at N=19 and N=1 (At N=0, that corresponds to a non-sour enumeration -- at N=20, that corresponds to a known-sour enumeration), at 2.5% chance. If we assume only a 2.5% chance per read check bit that someone learns an enumeration is sour, we can estimate how many check bits have to be read before all 2^20-1 sour enumerations are known sour by all 20 players.

As a quick stab at it, we want the odds that a single player will not know their enumeration is sour, given that they have at least a 2.5% chance to know it is sour for every check bit read, to be under 1/2^20. .975^k < 1/2^20 <-> 2^20 .975^k < 1 <-> 20 ln 2 + k ln .975 < 0 <-> k > -20 log_.975 2 <-> k >= 548. To get it so that the chance that none of the 20 people are likely to not know their game is sour is going to be about 119 more rounds, or about 666 rounds of check bits. We have 2^20 games to do this on, so we do 666 check bit rounds for each 2^20 games (we reuse the first one as a read for the previous game, and a write for the next game, for efficiency).

That should give us at least a 50-50 chance that any one person knows which is the good game.

After that, we play some trials for all 2^20 games. With a good enumeration of switches, the game is trivial (set it to 1 iff you haven't been in there in the 20 length game before, and if it ends with a 1 you win). You only say you have won if you know that this is the only good game (the other 19 players could have no clue).

The odds that a given game will have one of each person is 20!/20^20.

So, we start playing ~2 * 20^20/20! copies of "has every person been in the room in the this 20 length block?" for each of the 2^20 enumerations. A back of the napkin estimation says that, after the above, there is at least a 50-50 chance that we'll get a victory out of this.

We then repeat this entire block as many times as required. With a better than 50-50 chance of winning each block, it should take at most on average 2 blocks to get out of limbo.

So 666 * 2^20 + 2 * 20^20 / 20! * 2^20.

The prefix part is trivial compared to the second part. Now, 20^20/20! can be approximated as (n ln(n)) -- I'll assume that is accurate to within a factor of 2.5.

2^20 * (666 + 2.5*2*20*ln(20) =~ 2^20 ( 1000 ) =~ 1E9, or 3E6 years, or 3 million years. Double it for the 50-50 chance, and we get an average stay in limbo of 6 million years, give or take.

Note: the initial 666 per game is ridiculously conservative. That factor of 2.5 could probably be dropped a bunch as well.

But it seems to be faster than mfbs solution -- the driving base behind it is that I managed to share knowledge about what enumerations are crap, and we play tight games that bet that everyone knows (or at least the last player does) what enumeration isn't crap, so we don't need a huge prologue.

tl;dr -- how about 6 million years?

Edit:
I no longer think the 2^20 trick works.

Spoiler:

Even though A determines B, on even/odd days how it determines B reverses.

This adds another 2^20, or factor of a million, constant factor at the front of my time estimate, bringing the total time up to approx. 6 trillion years.

Edit2: The 50-50 chances are closer to 1/e than 1/2: (lim n->infinity (1-1/n)^n) than 50-50. A ~35% boost in the number of rounds should get it up to 50-50, giving us 10 trillion years. (lim n->infinity (1-1/n)^(1.35 n) = e^-(1/1.35) =~ 50%).