Interview Question
Country: United States
Nice! Can you prove (or disprove) that the problem has a solution only for 4 and 2 coins (the solution for 2 coins is obvious: flip one).
We can either have 3/1 case or 2/2.
First we convert 3/1 to 2/2 case by asking assistant to flip one coin (step 1).
now 2/2 case can be 2heads on diagonals or along edge. so we ask assistant to flip 2 coins on diagonals (step 2). this will either solve it or we are now sure its 2/2 on sides.
now we ask assitant to flip 2 coins on edges (step 3). This will either solve it or make it 2/2 head on diagonals.
now we ask assistant to flip 2 coins on diagonal (step4). This should then make coins start jumping.
I assume the assistant is dumb and he does not read the coins. Assistant blindly follow my rules.
There are 8 sequences of step I do to make sure that all coins fly up and down.
There are only two possible configuration in the board. Either one coin is odd man out or two coins.
For eg
H H T H
H T or H T
There are several combination of this one odd man out or two odd man out possible. But that is not going to affect our coin.
First I will assume my table has only one odd man out.
1. I ask assistant to flip a coin. If it matches all coins fly up and down. otherwise there are two coins odd man out ( like two H and two tail - odd man out can be any two) bcoz of wrong flip.
2. I try to flip a vertical side of table assuming vertical ( assuming table is plane) could be odd man out. If it matches success or I flipped a Diagonal odd man out to Horizontal or I flipped a horizontal odd man out to Diagonal
3. I try to flip a diagonal side of table assuming diagonal ( assuming table is plane) could be odd man out. If it matches success. Otherwise I flipped a horizontal odd man out to vertical.
4. I apply vertical flip and now if it is success, coins fly up and down otherwise initial configuration is not one odd man out, but two. So it is one odd man out now. So continue all the step again since we know it is one odd man out now.
Looks fine, though trying to explain it in terms of "odd man out" when you have two tails and two heads (after you assumed one and did one flip and you did not win) is confusing. It should be best explained in terms of "3 heads 1 tail", then "2 heads on the diagonal", "2 heads on one side", etc. Otherwise, it's difficult to follow. Good effort!
Two situations: 2/2 and 3/1. Flip one coin can turn 3/1 to 2/2 or win the game.
First we assume it's 2/2 case. Flip coins on diagonal, if not win, the heads/tails should be on the same side, and flip on diagonal will preserve this situation. Then we can flip coins on a random side, if still not win, we flipped the wrong side, the situation turns to diagonal, so we finally flip coins on diagonal could win the game. So these three steps can win all 2/2 cases.
If it's still not win, it should be 3/1 case. Then we randomly flip one coin that turn 3/1 to 2/2 case, or win the game(Lucy enough). Then we can use the same way to solve 2/2 case.
1 flip on diagonal
2 flip on side
3 flip on diagonal
4 flip one coin
5 flip on diagonal
6 flip on side
7 flip on diagonal
1. flip one. Result: If it's the one man out, the problem is solved. If not, it has converted into a 2 men out problem.
2. Flip any diagonal. If H or T are arranged diagonally, problem is solved. If not, it has converted the board into H and H appearing side-by-side.
3. Now flip any side. If you've flipped the H and H side, problem solved. Otherwise arrangement became diagonal.
4. Happily flip diagonal
First we enumerate the starting positions. We either have 2 head and 2 tails or 3 heads and 1 tails (which is equivalent to 3 tails and 1 head from our perspective so we don't care about that case). in 2/2 case a diagonal flip either wins the game (when head/tails are diagonal) or preserves the situation (when 2 head/tails are along the sides). In 3/1 case diagonal flip preserves the situation. We can see that diagonal first is benefitial as we can after that assume that we don't have a 2/2 situation with diagonal head/tails.
- Anonymous September 09, 2014Now we know we either have a 2/2 situation with the head/tails along the edges or 3/1 situation. Then we tell the assistant to flip one of the sides, and then the diagonal, as this preserves the 3/1 situation but wins the above mentioned 2/2 situation. If we still haven't won, we know we have a 3/1 situation, in which case we tell the assistant to flip one coin, flip one edge, and then flip one diagonal. This wins the game.