# The Unknown Prison of Unknown Size

Inspired by The Circular Prison of Unknown Size by @MikeEarnest (Great puzzle, by the way!)

The rules are almost same, so I won't waste time by rewriting them all here. (They're still valid, though.) The only major difference is the structure of the prison. It is not necessarily circular.

The prison has $n$ cells, each having atleast one switch and atleast one light. Every light is completely controlled by exactly one switch. A light and its switch cannot exist in the same room. As in the earlier version, lights emit a single flash at noon, after which the prisoners are re-scattered, one prisoner per room.

There is no dead end (or start) in the graph of the lights and switches. Meaning to say, if I select any switch in any room, find the room of its light, then see any one of the switches in that room and find the room of that light, and keep on doing so, I will eventually end up in the room I started with. This effectively makes the structure a set of cycles that are interlinked.

Added rule: One cannot find two independent non-empty subsets of this graph. Meaning to say, if the cells are divided into two sets, there will always exist a switch in set 1 that controls a light in set 2, and a switch in set 2 that controls a light in set 1.

As earlier, you can devise a plan for the other prisoners and follow a different strategy yourself. And the task is same, find the value of $n$ from any one prisoner's point of view.

## Extra

If this gets solved, try

• a method that enables a prisoner to figure out the entire structure, rather than just $n$
• a method that does not involve randomness

Please clearly specify if you are solving a variant and not the actual puzzle.

• Can there be any cycles of 1? – Deusovi Dec 23 '15 at 0:46
• @MikeEarnest Good catch. (You could have posted as an answer and earned some rep) I've added a rule that does not permit this. – ghosts_in_the_code Dec 23 '15 at 10:53
• @Deusovi In Q: A light and its switch cannot exist in the same room. – ghosts_in_the_code Dec 23 '15 at 10:53

If there is no known maximum number of switches and bulbs, the first part of the solution (finding a known upper bound) becomes much harder (refer to the other puzzle for the approach that's workable there). In the original puzzle, that involves for each "attempt" making sure that the number of prisoners who have seen light is at least $N$ and and at most $2^N$, and then using a procedure which, if any prisoners haven't seen light, will each day increase by 1 the number of prisoners who know that not everybody has seen the light. The same principle can be applied, even in the generalized problem, but the number of prisoners who might see light increases a according to $N!$ rather than $2^N$.

For simplicity, regard the boss as a "prisoner who has seen the light going into the first day". On the first day, the boss alone turns on one light. On the second day, the boss and the prisoner who saw the first light must turn on two lights if possible to ensure that someone will see light who hasn't done so already. After the second day, it's possible that as few as three people (including the boss) may have seen light, but as many as six might have done so.

Now comes an interesting bit.

On the third day, it's not necessary that prisoners ensure that anyone new see the light, but merely to ensure that by the end of the day at least four people (including the boss) have done so. If at least one of the prisoners who has seen light (or is the boss) is able to turn on three light switches, then three other prisoners will see light next turn, bringing the total up to four prisoners. If none of them have three or more switches, then having them all turn on all their switches will result in at least one new person seeing light. Thus, weakest case ends with four prisoners plus the boss having seen the light; strongest with 24 (six people each turn on three switches, illuminating 18 new people)

For succeeding days:

1
1+1=2
2+(2*2)=6
6+(6*3)=24
24+(24*4)=120
120+(120*5)=720

Thus setting up the $N!$ progression.

Once an upper bound on the number of prisoners is established, the approach used in the other puzzle for determining an exact number may be used. Determining the topology of the switches is apt to be difficult, and I don't think a full mapping will be possible without randomness or a means of hiding one's plans from the warden:

If in a prison with 14 or more cells there are five rooms with two switches and one light, and none of them control each other's light, a warden will always be able to ensure that the lights are always all light or all dark (by suitably arranging nine prisoners in the five cells that control them) thus rendering them indistinguishable from each other. The warden will then always be able to ensure that the first two of the rooms are always populated by prisoners who will flip the switches the same way given the same circumstance (there are four possible prisoner actions; by the pigeonhole principle, if there are five prisoners two must perform the same action). Since there is no way prisoners can operate those switches independently, there is no way to disambiguate what they control.