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."

 

Riddle Me This 5: All That Glitters Is Gold (Coins)

These are less straightforward than the card-flipping riddles, but it all comes down to flipping in the end! Answers (along with a hint for the harder 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:
You are blindfolded with 72 coins on a table in front of you. Exactly 1/4 of them are heads up, though you don't know which they are. Separate the 72 coins into 2 piles, each containing the same number of heads up. You can flip as many coins as you like, though you won't be able to tell if they are heads or tails up.

This is a fun math trick that always blows my mind. There are 18 heads up. Say we take 18 coins from the 72 coin pile, and there are x heads up in the remaining 54. Then there are 18-x heads up in the 18-coin pile, and x tails. But then if we flip all of those 18 coins, there will be x heads up in that pile too, leaving x heads in each pile. :D

 

Harder (first read on the riddle page of Dr. Miller here):
You sit blindfolded in front of a square with a coin in each corner. You want to get all coins heads up or all tails up. You have no idea what the starting formation is, of course; they could even be all heads up to begin with. You may flip however many you want, then ask if you are done (this constitutes a turn). If you are not done, the square is then spun an undisclosed amount clockwise or counterclockwise. You then get another turn and so the game continues. Is there a strategy that is guaranteed to work in a finite number of moves, and if so, what is that smallest number of moves you need?

Think about what possible states the four coins could be in. For example, there could be 1 head and 3 tails up. What other states could they be in? Do any of these states have a "guaranteed win" move?

 

This one is really tricky. The key is to enumerate all the possible states and work through them to see which you can solve fastest. First, all the states:
All 4 of one kind (4:0)
3 of one, and 1 of the other (3:1)
2 each, with same-sided coins next to each other (2:2 adjacent)
2 each, with same-sided coins diagonally opposite each other (2:2 diagonal)
Next, let's define some flips:
No flip (N)
Just one coin (O)
2 adjacent coins (A)
2 diagonally opposite coins (D)
The first thing to notice is that if we do a diagonal flip (D) from the 2:2 diagonal state, we win! This is good news. Even better, this has no effect on the 3:1 state or the other 2:2 state!
Now, what happens if we try to solve the 2:2 adjacent state by using A? Either we win (yay!) or we get to the 2:2 diagonal state! Then we can do D again and win!
Fortunately, neither of these 2 coin flips affect the 3:1 state. If we try to solve this state by using O, either we win or we get to one of the 2:2 states. Then we can do the same sequence of D, A, D to be sure of success!
Since we also want to check the case where we're done to begin with, we'll check that first by flipping no coins. In sum, we have N, D, A, D, O, D, A, D. Just 8 flips and we're sure to win! :)

Riddle Me This 5: Luck And Intuition Play The Cards

This is the first of a series of 3 sets of flipping riddles, which will get progressively harder. Answers can be found below each question, but feel free to ask for hints or let me know if you have the solution! Enjoy! :D

Easier:
I have 5 cards on a table, showing L, 1, F, E, 8 face-up. How many cards do you need to flip to test the rule "If there is a consonant on one side of a card, there is an odd number on the other side"? Which ones?

You definitely need to check the consonant cards, L and F. If they don't have an odd number on the other side, the rule is definitely broken. Now, which do you need to flip, the 1 or the 8? Suppose the 1 was flipped, and there was an A on the other side. That wouldn't actually invalidate the rule! Instead, it is the 8 that should be flipped to make sure that there is a vowel on the other side. In total, then, you need to flip 3 cards--the L, F, and 8.

Harder:
There is a standard deck of 52 playing cards lying face-down on a table. How many do you have to flip to guarantee a straight somewhere (eg. 4, 5, 6, 7, 8)? How about a straight flush (same suit as well)?

Without 4 and 9 (or 5 and 10), no sequences of 5 cards from {1,2,3,4,5,6,7,8,9,10,11,12,13} can be made. That means that you could have picked 11 * 4 = 44 cards without having picked a 4 or a 9, and thus without having made a straight, or a straight flush.