This game, or a variation, is played sometimes on the SyFy game show Exit. I feel like this could be beaten with a coherent strategy, but I can’t puzzled it out.
Here’s how it works: You are asked five questions, and you must provide answers to each question. Only after you’ve answered are you told how many (if any) you got right.
For example, in an episode of Exit it might look like this: You are given five action heroes from recent movies (say, Iron Man, Thor, Wolverine, Lone Ranger, John McClane) and you must match them to the five actors who portrayed them (Robert Downey, Jr., Chris Hemsworth, Hugh Jackman, Armie Hammer, and Bruce Willis).
So assume you’re playing the game and the only one you’re sure about is John McClane=Bruce Willis. So you match John McClane to Bruce Willis and match the other four at random. Once the host tells you that you only have one correct, how can you work it out logically and systematically to get the rest, without having to just resort to wild guesses?
Similarly, if you don’t know any of the answers and your first set of matches is totally random, how can you use the information the host gives you to suss out the solution?
In the show there is a time limit, but for this thought experiment assume that there isn’t one. The guesses are registered when you do the fifth match.
Well, just looking at it from a purely information-theory standpoint: Given n completely unknown items to match up, you have n! possible arrangements of them, and each try will either win, or give you one of n-1 different possible responses (in the case of n=5, this is 720 possibilities, and a response of either 0, 1, 2, or 3 matches on each try). So you’ll surely sometimes need ceil[log[sub]n-1/sub] wrong guesses before you have enough information. For the game with 5 unknowns, each wrong guess gives you one of 4 answers. 4[sup]3[/sup] = 64, less than 120, so 3 guesses will sometimes be insufficient, but 4[sup]4[/sup] = 256, well more than 120, so there’s at least a reasonable hope that 4 will always be enough to learn the answer (followed by a fifth try where you give the solution you deduced).
If you already know one of the matches, then (for purposes of this analysis) you can treat it as just being a lower value of n. For instance, with four unknowns, you must distinguish between 24 possibilities, and each non-winning guess gives you one of 3 results. 3[sup]2[/sup] < 24 < 3[sup]3[/sup], so there will always be cases where 2 guesses aren’t enough, but 3 looks like it might be enough.
It sounds like it can be played in a similar way to the pegboard game Mastermind - although in Mastermind, you’re told how many you got right, and how many you got in the right sequence - the latter detail being irrelevant for the game the OP describes.
If you have multiple trials, you can cross-reference results and get the correct answers by inference
There was a TV game show, probably late '70s, where the bonus round was somewhat similar. There were 12 TV monitors, arranged in four columns. When you touched one, a light went on around it. (Touch it again and the light goes out.) You’d get a question like “names for a group of animals” and 12 answers would appear on the monitors (6 right, 6 wrong). You’d run over and select 6 monitors, then run back and press a button, and a number would tell you how many you had correct. You could keep trying until you got 6 right or time ran out (60 seconds, I think.) I did see someone beat it by brute force once. He changed two monitors at a time (deselect one, select another) and noticed if the number of correct answers went up, down, or stayed the same.
Can’t remember what it was called. I’m checking through Wikipedia, but the list of game shows is long.
But what you’re describing is a little different. You have to match up five names to five movies. You can’t just change one-at-a-time and use process of elimination. There might still be a way, but it’s not jumping out at me as obvious. If you know one for sure, I wonder if you could use that somehow.
You just use the same idea and see if the number goes up, down, or stays the same. Say you guess 1,2,3,4 and know that 1 is correct. You’re told you have one right. So you go 1,3,2,4. One is impossible because then both the 2 and 3 would have to go last (you tried them everywhere else), so you can only be told two or four are right. If four, you win. If two, then you just have to figure out where the 4 goes. So either 1,4,2,3 or 1,3,4,2. Then you’re done.
It’s more complicated with a higher n, but the same idea.
I think that there are some situations where you’d be better off to deliberately make a guess that you know is wrong, so as to give you more information. I haven’t worked it out completely yet, though.
Right, let’s say have {A,B,C,D,E} and {1,2,3,4,5}. We’ll assume you know that A=1, but nothing else. The following gives some useful information:
{,A,,,} (assume that for all answers we’re using {1,2,3,4,5} for the arrangement of the other set) Where _ means it doesn’t matter what you put there. You know two things with this assignment:
The first slot cannot be correct
The second slot cannot be correct.
From here you can proceed as follows. You will be given some number, 0 <= n <= 3, telling you how many are correct (remember, it must be <= 3 because we’ve eliminated two possible correct slots). Remember this number. If n is ever 3, just swap slots 1 and 2 because you win. Swap slot 1 and slot 3, if n stays the same then you know that the element in slot 4 or slot 5 must go in slot 3. If n increases, then the element that was previously slot 1 belongs in slot 3. If n decreases, then the element previously in slot 3 was correct.
In the case where n stayed the same, swap slots 3 and 4:
[ul]
[li]If n increases by 2, then you solved the puzzle. You know slot3 and slot 4 are correct, if n is 2, then slot1 belongs in slot 5 and slot 5 in slot 2. If n is 3 then slot 1 belongs in slot 2. [/li][li]If n decreases by 1, then you’ve also solved the puzzle: slot 5->slot3, slot4->slot5, slot3->slot4, slot1->slot2, slot2->slot1.[/li][li] If n stays the same, n must be zero (because you’ve eliminated all other possibilities for slot 3). Thus slot5->slot3, slot1->slot4, slot2->slot1. Then one more move is necessary: randomly assign the remaining two variables (slot 3, slot 4) to 5 and 2. If n is 5 you were right, else swap them and you win.[/li][/ul]
In the case where n increased by one in the initial check, you know the following, {A,,C,,} which will look like {,A,C,,} in your current configuration. As always, if n=3, you’ve won, slot1 is really slot 2. Swap 1 and 4. If n increases and n=3, you win, if n increases and n=2 then slot1 is really slot 5 and slot 5 is slot 2, you’ve won. If n decreases, then n=1, and slot 4 is slot 5, slot 5 is slot 2, slot 1 is slot 4, you win. If n stays the same, n=1, and slot5 is slot4, randomly assign slots 1 and 4 to 5 and 2, if you’re right you win, if not, swap 5 and 2 and you win.
In the case where n decreased by one in the initial check, swap 1 and 3 back and proceed as if n had increased.
Okay, but what if you start off and don’t know any answers? Pick a slot, any slot. We’ll assume we’re finding 1. Swap 1 and 3. If n decreases or increases by 2, you have two answers, lucky you! Put 3 in 2 and 1 in 3 (if it’s decreased), or nothing (if it’s increased) and proceed as if “n has increased” above.
If it increases or decreases by 1, swap 1 with another slot. Ignore whether n increases or decreases here (for now). Now swap 1 and 3 again,
[ul]
[li] If n increased the first time, and suddenly stays the same this time, then whatever value you just put in that random slot belongs in 1.[/li][li] If n increased the first time, and suddenly stays the same this time, then whatever value you just put in that random slot belongs in 1.[/li][list]
[li] If n decreased the first time, and suddenly stays the same this time, then whatever value you just put in that random slot belongs in 3. Rearrange your “answer” set so it reads {3,2,1,4,5} and proceed as if you learned slot 1.[/li][li] If n decreased when you swapped the first time, increases this time, you know that what is in slot 1 is not correct.[/li][li] If n decreased when you swapped the first time, and decreases this time, then whatever you put in that random slot is what belongs in slot 3, and what’s currently in slot 3 belongs in slot 1.[/li][li] If n increased when you swapped the first time, and decreases this time, the value in slot 1 belongs in slot 3. Rearrange your “answer” set so that it looks like {3,2,1,4,5} and proceed as if you learned slot 1.[/li][li] If n increased when you swapped the first time, and decreases this time, then what you put in the random slot belongs in slot 1, and what’s in slot 1 belongs in slot 3.[/li][/ul]
If n stays the same during the initial swap, then pick a slot other than 3 and do this again. (You actually have some extra information now and could do something slightly more efficient, but for a set as small as 5 the extra cost here isn’t a big deal).
P.S.: Interesting note, you can never have four correct answers.
Should be:
[ul]
[li] If n increased the first time, and suddenly stays the same this time, then whatever value you just put in that random slot belongs in 1.[/li][li] If n increased the first time, and suddenly stays the same this time, then whatever value you just put in that random slot belongs in 1.[/li][li] If n decreased the first time, and suddenly stays the same this time, then whatever value you just put in that random slot belongs in 3. Rearrange your “answer” set so it reads {3,2,1,4,5} and proceed as if you learned slot 1.[/li][li] If n decreased when you swapped the first time, increases this time, you know that what is in slot 1 is not correct.[/li][li] If n decreased when you swapped the first time, and decreases this time, then whatever you put in that random slot is what belongs in slot 3, and what’s currently in slot 3 belongs in slot 1.[/li][li] If n increased when you swapped the first time, and decreases this time, the value in slot 1 belongs in slot 3. Rearrange your “answer” set so that it looks like {3,2,1,4,5} and proceed as if you learned slot 1.[/li][li] If n increased when you swapped the first time, and decreases this time, then what you put in the random slot belongs in slot 1, and what’s in slot 1 belongs in slot 3.[/li][/ul]
and
Should be “Put 1 in 2 and nothing for 3 (if it’s increased)”
I also forgot the case where n is the same for the first swap and only increases by 1 for the (3,4) swap, but there’s a guaranteed order when that happens (you know that 1 has to be 5, and 4 has to be 2).
In short, the strategy is to create a “safe space”, meaning you force a situation in which case if n changes you’re 100% sure of the reason it changed (in our case, we’re sure because we know we’re forcing one of the answers to be wrong no matter what). Everything cascades logically from there.
I’m sure in real life (and with bigger sets) you can get better results by doing multiple swaps per “turn” and using some probability, but that’s not very necessary here (and would be harder to pull off under the spotlight at a gameshow).
In the UK this was called Wipeout and was hosted by Bob Monkhouse and Paul Daniels (in separate stints- there may have been other hosts as well). One of the better quiz shows of its time, IMHO. Don’t know if the US version had the same name.
The odd thing is, I checked that page before. I remembered the two-player bidding round of the game, and the bonus round, but the description starts with three players. I didn’t remember that part, so I figured that wasn’t the right show and kept looking.
In any case, I saw a player using a brute-force approach on the bonus round. He’d change two monitors at a time, notice if his number went up or down (or stayed the same), and logically derived the correct answers. I consider that to be an excellent game-show hack.