A paper entitled "One hundred prisoners and a lightbulb" by Paul-Olivier Dehaye (whose homepage also includes a decadent chocolate mousse recipe), Daniel Ford (who also has a web page with puzzles), and Henry Segerman (whose delightful homepage deserves a discussion of its own and suggests he has spent some quality time with Gödel, Escher, Bach) appeared in the Mathematical Intelligencer 24 (2003) no. 4, pp 53-61. It is available as a preprint here, here, here, and here. In that article, a situation very similar to the two switch puzzle is described. You should read the description of that puzzle if you haven't already.

The most important difference in this version is the fact that the warden brings a prisoner to the switch room at regular intervals (although the one selected is still random). Other differences include a known initial switch position (which slightly simplifies solutions), the fact that there are one hundred prisoners instead of twenty-three (although the number of prisoners is immediately generalized to n), and the use of only one switch which may or may not be switched (which is actually exactly equivalent to requiring the switching of one of two switches).

What is exciting about the paper is the degree to which it clobbers this problem! The authors provide several strategies for the problem, analyzing the expected time until the prisoners are freed for each. The first ends up with a nasty O(n^1/2eⁿ). This is dramatically improved by the second to O(n²). The third has an expected running time of O(n log(n)²), which is probably nearly optimal if not optimal. (In any case, the authors point out that no algorithm can do better than O(n log n).) They then proceed to consider a fascinating array of sixteen variations on the problem, including the formulation of the problem with random visitation times. Each of these is promptly solved. Finally, the authors give their "über-theorem": the prisoners can all reliably send each other messages of arbitrary length. Even more astonishing is the "über-über-theorem" that follows it: this can even occur in the scenario of random visitation times.

I highly recommend the paper. Thanks to Evan Danaher for pointing it out to me. Be sure to also check out Danaher's homepage. After poking around his website I was very impressed when I learned he is (or was in spring 2004, anyway) still a high school student!