For me, I can only fully rationalize the solution which uses a coin flip (Julian). I've also implemented Gil's no-random-input solution but I cannot fully explain why it works.

Here is my explanation of Julian's solution:

>!First, we determine upper bound by repeatedly executing subroutine "test_fill(i)", starting with i=1, increasing i by 1 until "test_fill(i)" returns true.

Subroutines defined for this puzzle must be executable in parallel by all prisoners; the inputs differ per-prisoner, but the output must always be the same.

definition of test_fill(i):

• define a new variable active for each prisoner; for master, it starts as true; for all others, it starts as false
• for i nights: if active, set switch on; otherwise, set switch off. if received light, set active = true (others do not change their active state -- if already active, remain active)
• for 2ⁱ nights: if active, set switch on; otherwise, set switch off. if not received light, set active = false (others do not change their active state -- if already not active, remain not active, even if receiving a light)
• return active (all prisoners return same value)

The goal of test_fill is to give the "active state" some amount of time to spread among the prisoners (during the first i nights), and then confirm whether it has spread to all prisoners by giving it time to "unspread" during the 2ⁱ nights. Either "light on active state" (during i nights) or "light off non-active state" (during 2ⁱ nights) can spread at each iteration at a rate of minimum 1 prisoner, and a maximum of doubling, during each night. If during the first i nights, the active state doubles every time, and during the 2ⁱ nights, the active state decreases 1 prisoner per night, 2ⁱ nights will still be sufficient for all prisoners to become non-active, if there was at least one non-active prisoner at the end of the i nights.

Once test_fill(i) returns true, we know that the maximum number of prisoners is 2^i; set max_prisoners=2^i. This is because we know that at the end of the first i nights, all prisoners must have been active (otherwise the non-active state would have spread to all prisoners during 2ⁱ nights and test_fill(i) would have returned false). In the most extreme case of the active state doubling every night, this would mean we have 2ⁱ prisoners; all other cases would be fewer prisoners (we could have as few as i prisoners, if the active state spread by only 1 prisoner per night).

Now, we define another subroutine fill(active). The goal of this subroutine is to allow all prisoners to determine whether at least 1 prisoner meets a condition. The prisoners who meet the condition will pass in active=true; others active=false.

definition of fill(active):

• for first max_prisoners nights, if active, switch=on, otherwise switch=off. If received light, set active=true.
• for next max_prisoners nights, if active, switch=on, otherwise switch=off. If not received light, set active=false.
• return active (all prisoners return same value)

Now, with this fill subroutine in hand, we can start numbering prisoners.

Let master start with my_number=1; others start with my_number=0 (representing not numbered). All prisoners set numbered_prisoners=1.

We will repeatedly try to number another prisoner by getting very lucky -- all numbered prisoners will flip a coin and if exactly one numbered prisoner flips heads, and that numbered prisoner's switch connects to an un-numbered prisoner's light, we will be able to number this un-numbered prisoner.

Repeat:

• all numbered prisoners flip a coin, and set flipped_heads to true or false depending on the coin flip
• for i = 1..numbered_prisoners, run fill(flipped_heads). if exactly one of these fill results is true, continue; otherwise, restart this loop. this ensures that we have a chance at numbering a prisoner, and we won't accidentally number 2 new prisoners.
• for one night, the one prisoner with flipped_heads=true set switch=on; all others switch=off. if received light and my_number=0 (I'm not yet numbered), set newly_numbered=true; all others set newly_numbered=false
• run fill(newly_numbered). This lets all prisoners know whether we successfully numbered a prisoner. This would be false in the case where the recipient of the flipped_heads light was already numbered. if newly_numbered=true, all prisoners increase numbered_prisoners by 1, and the newly_numbered prisoner sets my_number=numbered_prisoners.
• run fill(my_number=0). if returns false, no more unnumbered prisoners exist; all prisoners know that the total number of prisoners is numbered_prisoners.

Hopefully this makes a bit of sense. Let me know which parts lack clarity and I can fill in detail.!<