Matching Game

Another week, another riddler. I really liked this one, if a bit clear cut. The problem:

I have a matching game app for my 4-year-old daughter. There are 10 different pairs of cards, each pair depicting the same animal. That makes 20 cards total, all arrayed face down. The goal is to match all the pairs. When you flip two cards up, if they match, they stay up, decreasing the number of unmatched cards and rewarding you with the corresponding animal sound. If they don’t match, they both flip back down. (Essentially like Concentration.) However, my 1-year-old son also likes to play the game, exclusively for its animal sounds. He has no ability to match cards intentionally — it’s all random.

If he flips a pair of cards every second and it takes another second for them to either flip back over or to make the “matching” sound, how long should my daughter expect to have to wait before he finishes the game and it’s her turn again?

To solve this we can look at each “level” independently, where a level is the number of pairs of cards remaining. We start at level 10 and our goal is to get to level 0. To figure out the estimated amount of time on, for example, level 10 we use the equation:

t_{10} = \frac{1}{19}(2) + \frac{18}{19}(2+t_{10})

This says the first card selection doesn’t matter – but after selecting it we have to select the second card and there is only one pair. This equation shows that there is a 1/19 chance we correctly select the card and proceed, while costing two seconds. There is also a 18/19 chance we fail, which costs us two seconds plus the time to successfully complete the level. Solving this gives us:

t_{10} = 38

Extending this we can see that solving for a generalized level is:

t_{n} = \frac{1}{2n-1}(2) + \frac{2n-2}{2n-1}(2+t_{n})

Summing levels 1-10 gives us 200 seconds. This was confirmed by brute forcing it in python.

import random, math

def run_trial(card_pairs): 
  time = 0
card_set = [math.floor(i/2) for i in range(card_pairs*2)]
while len(card_set):
    selection_index = [i for i in range(len(card_set))]
    random.shuffle(selection_index)
    if card_set[selection_index[0]] == card_set[selection_index[1]]:
      value = card_set[selection_index[0]]
      card_set.remove(value)
card_set.remove(value)
time += 2
return time

sum_time = 0
trials = 10000
for i in range(trials): sum_time += run_trial(10)
print("Average time: " + str(sum_time/trials))

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s