Riddle Me This 5: All Of The Lights, All Of The Lights

These are the hardest set of flipping riddles I know, but when you get them, you'll light up for the rest of the day! Answers (along with a hint for the hardest one) can be found below each question, but feel free to ask for hints or let me know if you have the solution! :D

Easier:
I have 1000 numbered lights turned off, all in a row, each with associated light switches. I first flip all the lights (turning them all on). I then flip just the even numbered lights (2, 4, etc). I then flip just every 3rd light (3, 6, etc). I continue this through 1000 iterations (for the last one, I just flip the 1000th light). At the end, how many lights are on?

The first light will be flipped just once, on the first run. How many times will the 12th light be flipped? On the runs 1, 2, 3, 4, 6, and 12. Notice that these are the factors of 12, or all the positive integers that divide 12 evenly. The fun thing about factors is that they come in pairs! (1 * 12 = 2 * 6 = 3 * 4 = 12). So it would seem that every number besides 1 is going to be flipped an even number of times, and therefore end up off. But wait! What if a factor is paired with itself? For example, 4's factors are 1, 2, and 4 (2 is paired with 2!). That means that 4 will be flipped 3 times and end up on. If a number has a factor that is paired with itself, that means the number is a square. How many squares are there between 1 and 1000? It turns out that 32², or 2¹⁰ as many will know it, is 1024, which is just over 1000. So since there are 31 perfect squares under 1000, there will be 31 lights on at the end!

 

Harder:
There are 111 numbered lights turned off. You and I play a game where we take turns flipping lights. At least 1 and at most 10 flips must be made each turn. More lights must be flipped on than flipped off in any turn. The loser is the first one whose turn ends with all lights on. I let you choose who goes first. What should you choose, and what is your winning strategy? 

If the loser is the one who turns the last light on, you can force me to lose if you leave me with just 1 light off. You can make sure that happens if there are anywhere between 2 and 11 lights left off on your turn. How can you make sure that there are that many lights? By making sure that I have 12 lights left off on my turn! As you can see, the number of lights you want off on my turn is going to start at 1 and go up by increments of 11, or any number (11n + 1). 111 = 11(10) + 1, so you want to give the first turn to me!

 

Hardest (first found on Dr. Miller's riddle page here): 
A warden tells 50 numbered prisoners that he is giving them a chance to be released, or executed--a fun game (by his twisted definition of fun)! They will not be able to communicate with each other after one 3-hour-long planning session before they are taken to their rooms and the game begins.
There is a special room containing two light switches numbered 1 and 2, which can each be either up or down (on or off). They cannot be left in between, they are not linked in any way. Their initial positions are unknown to the prisoners. One at a time, a prisoner will be brought into the room. The prisoner must flip one and only one switch. The prisoner is then returned to his cell.
There is no fixed pattern to the order or frequency with which prisoners visit the room, but at any given time, every prisoner is guaranteed to visit again eventually. At any time, any prisoner may declare that all 50 of them have been in room 0. If right, the prisoners all go free. If wrong, they are all executed.
If you were Person 1, what plan would you give your cohorts during the meeting? 

Think about simpler versions of the riddle. Two switches where you are forced to flip at least one is similar to just one switch that you can choose not to flip. What would you do if there were just 2 people, and you knew the switch's starting position? Then see if you can remove assumptions to return to the original question.

 

You claim authority and says to the others, "Ok, listen up everyone! Here are the rules. The first two times you see Switch 1 down, flip it up. If Switch 1 is already up, or if you've already flipped it up twice, don't touch it and just flip Switch 2. If I ever see Switch 1 up, I'll flip it down. I'll flip Switch 2 otherwise. Once I see Switch 1 up 49 * 2 = 98 times, I'll know that each of you has flipped it at least once, though most if not all of you will have flipped it twice. Then I'll call the warden and we can get out of here."