Black-box counting to 19 with only 2 bits, and only toggleable?

Question

Some student asked this on another site, but got no answers. I had a few stabs at it, but found it pretty tricky.

Doing it with just the switches would require a 9:1 compression ratio, so I guess the trick is very much in the rules you assign to students. Perhaps every student needs a different set of rules?

I've thought about allowing many iterations where no answer comes up, by only paying attention to students in the correct sequence. I've also thought about encoding the student number as binary, and combining that with the bits from the switches, to get more bits to work with, but that's still a compression/validation problem: even if one of those bits was used for parity, you'd still have a big potential for false positives.

Presumably the problem wouldn't have been asked if there wasn't some way to do it. Maybe this is a common problem in comp-sci courses and well-known? Anyway, without further ado...

"Here is a problem I have for a computer class. It's seems kind of mathematical to me and could possibly involve the binary code. I'm not sure, all my ideas lead to dead ends.

Nineteen students are given the opportunity to win a prize by playing a game. After some time to decide on a strategy, all the students will be placed into separate soundproof isolation chambers with absolutely no way to communicate.

The game is played as follows. There are two light switches in a room that will begin in the "off" position. I will bring students into this room one at a time. Each time a student enters the room then he or she must flip one of the switches. All the students will eventually be brought into the room, but some students may be brought in more than one time.

If one person correctly tells me that everyone has been in the room, then everyone wins the prize. However, if someone incorrectly tells me that everyone has been in the room then everyone will be fed to the alligators! Note that either all the students win the prize or else everyone loses.

Your task is to determine a strategy that will be sure to allow everyone to win the prize (and not be eaten by alligators)."

Answer 1

This sounds like a variation of the Prisoners and the Light Switch riddle, where one prisoner is designated as a "counter" and everyone else "increments their count" only once.

Presumably the counter would turn on one switch, and if you had never been counted, you would turn off that switch; the other switch would be "garbage". Once the counter turned off the switch 18 times, he knows that all other students have been to the room.

Answer 2

The way the problem is worded, the organizer/teacher can ensure he never has to give out the prize: Allow each student into the room in turn - which only allows the Counter to count one other student. Then only iterate a subset of the students - say 3 of them.

Then either the Counter can count two other students then get stuck, or the Counter never goes back into the room.

This satisfies the specified conditions: Everyone goes into the room at least once, and some students go in multiple times.

To allow the students to win, you need to add the condition that there is a finite limit between any single student's visits to the switch room.