Lidl Challenge - Today FM

moycullen14

Hi,

Bit of an odd one but as Sherlock Holmes would say, 'It presents certain points of interest'.

On Ian Dempsey's program about 830am, they play a game.

There are 8 pairs of songs - 16 in total, numbered 1 to 16.

Each competitor (there are two) gets to pick two numbers in turn, a snippet from the song is played as it is picked and the winner is the first one to get two matched songs.

Generally people either win by randomly matching two songs or by picking a song that has already been played and then selecting the other song.

An example would probably help as I'm not explaining this very well.

Say Song A is number 1 & 9, B = 2 & 10, C = 3 & 11 and so on.

Here's a sample game:

Competitor 1: 2 & 13 - B,E
Competitor 2: 1 & 7 - A,G
Competitor 1: 4 & 3 - D,C
Competitor 2 now picks 9 (A) as his first pick and knows that it's the same as 1 so that's his second pick and he wins.

The question is what are the probabilities of winning on each turn? Assuming perfect memory. Also, are you better going first or second?

I drive my daughter (LC Maths) to school around the time this is on so I've been having great fun getting her to try and work out the probabilities.....

IMO it's a lot trickier than it seems at first.......

hivizman

One way to do this is to work through easier cases and see if any sort of pattern emerges.

Let's assume that there are n songs, and for each song there are two identical snippets (if the two snippets are different for each song, then the challenge becomes more than just memory - it requires competitors to be familiar with the whole songs). Let's also assume that both competitors have perfect memory, so, if they have heard a snippet already, they will always match this correctly with any subsequent playing of the same snippet. Finally, let's assume that both competitors hear the snippets whether or not it's their turn.

Then first of all consider n=1. In this case, there are only two snippets, which are identical, and the first competitor must win.

Now consider n=2. There are four snippets. The first competitor can choose two snippets in any one of six ways (this is simply 4C2, the number of ways of selecting two items from a set of four, when the order of selection doesn't matter). Two of these ways involve selecting matching snippets, the other four involve selecting mismatching snippets, so the first player has a probability of 1/3 of hitting a match on the first round. If the first player does not hit a match, then the second player must win, because the second player will have heard a snippet for both of the songs, and hence can match whichever snippet is selected from the remaining two with one of the two snippets selected originally by the first player. So the probability that player 2 wins is 2/3 and the probability that player 1 wins is 1/3.

Now consider n=3. The first player has 15 ways of selecting two snippets from the original set of six, of which three will lead to a matched pair, so the probability that the first player wins on the first round is 1/5. Note that we are starting to see a pattern - in general, the number of ways of selecting two snippets, when there are n songs and hence 2n snippets, is (2n)(2n-1)/2, and n of these will be matched pairs, so the probability that player 1 wins on the first round is (2n)/(2n)(2n-1) = 1/(2n-1).

If the first player does not win on the first round, then the second player will choose a snippet from the remaining four available. Given that the first round did not produce a match, the remaining four snippets contain two snippets that match with the two songs selected in the first round, plus another matched pair. There are three possibilities: (1) the first snippet selected by Player 2 matches one of the snippets chosen by Player 1 - probability 2/4 = 1/2; (2) the first snippet does not match, so represents the third of the three songs, but Player 2 selects the other snippet for this song from the three remaining snippets - probability 1/3*1/2 = 1/6; (3) Player 2's first snippet doesn't match one of the two snippets selected by Player 1, but the second snippet does match - probability 2/3*1/2 = 1/3. In cases (1) and (2), Player 2 has a matching pair and hence wins. The overall probability of this happening in round 2 is 1/2+1/6 = 2/3, but the game will reach round 2 only 4/5 of the time, so the overall probability that Player 2 wins is 4/5*2/3 = 8/15.

If player 2 does not win on round 2, then player 1 must be able to win on round 3 - between them, the two players have revealed a matching pair already. The probability of reaching round 3 is 4/5*1/3 = 4/15. Overall, then, Player 1 wins with probability 1/5+4/15 = 7/15 and Player 2 wins with probability 8/15.

You can see how complicated things get as n increases, but there are likely to be underlying patterns that allow you to work out some underlying formula. Also, the possible outcomes become complicated depending on how much new information becomes available. If n=4, then, assuming that Player 1 doesn't hit a pair in round 1, then there are four types of outcome in round 2: (1) Player 2's first choice matches one of the two snippets in round 1; (2) Player 2's first choice doesn't match one of the first two snippets, but the player hits a pair with the second choice; (3) Player 2's first choice doesn't match one of the first two snippets, but the second choice does match, and (4) Player 2's first choice doesn't match one of the first two snippets, and the second choice doesn't match any of the songs so far revealed - this means that, between them, Player 1 and Player 2 have identified all four songs. So (1) implies that Player 2 wins on round 2, (2) also implies that Player 2 wins on round 2, (3) implies that Player 1 wins on round 3, because between them the two Players have identified two snippets that match, which Player 1 can pick on round 3, and (4) implies that Player 1 wins on round 3, because Player 1 can match whichever snippet is selected from the remaining four snippets with one of the four snippets already revealed. So the game must terminate by round 3, and I have calculated that Player 1 has a 3/5 chance of winning and Player 2 only a 2/5 chance of winning.

If I have time over the weekend, I'll see if I can come up with something more general, or at least see if I can work out the probabilities for n=8. This must terminate after five rounds at the most, and I suspect that Player 1 will have the advantage, as in the n=4 game.

hivizman

I've been able to analyse the structure of this game more carefully.

As I noted in my earlier post, Player 1 has a probability of 1/(2n-1) of winning in the first round if there are n songs (and hence 2n snippets). If Player 1 does not win, each subsequent round has the same structure, with four possible outcomes:

(a) The player selects a snippet that matches a snippet revealed in an earlier round. The player can then select the matching snippet and win.
(b) The player's snippet does not match a previously revealed snippet, in which case:
(b1) The player selects another snippet that matches the first selection, and hence wins.
(b2) The player selects another snippet that matches one revealed in an earlier round. This allows the other player to make a matched pair in the next round and win.
(b3) The player selects a snippet that does not match any previously revealed.

So, in cases (a) and (b1), the player making the selections wins the game, in case (b2), the other player can win the game on the next round, and in case (b3), the outcome is uncertain.

Each round, the player reveals additional information. If the player doesn't win on that round, and doesn't provide the other player with a guaranteed win on the next round, then the players have information about two more songs. This means that, if the number of songs n is even, after n/2 rounds all the songs are revealed and, if there hasn't been a winner yet, the player of the next round must be able to match a previously unselected snippet with one of the snippets revealed in the previous rounds. If n is odd, we need (n+1)/2 rounds to reveal all the songs, and the player of the next round must be able to win. So for a game with 7 songs, we need 4 rounds to reveal all the songs and the game cannot have more than 5 rounds, while with 8 songs we also need 4 rounds to reveal all the songs and hence the game cannot have more than 5 rounds.

I have calculated the probabilities that Player 1 will win the game and that Player 2 will win the game for up to 10 songs. After some early irregularity, the probabilities appear to be converging, with a probability of 0.515 that Player 1 will win and 0.485 that Player 2 will win. So Player 1 has a slight edge.