Robot Concentration

Suppose that $A_{a,b,m,n}$ is the probability that player A wins, given that he goes first, that the score is $a\,:\,b$ (A has found $a$ pairs, while B has found $b$ ), that there are still $m$ pairs to be identified, and that $n$ singleton cards ( $n \le m$ ) have already been uncovered. Suppose also that $B_{a,b,n,m}$ is the probability that player A wins, given that B goes first, the score is $a\,:\,b$ , that $m$ pairs remain and $n$ singletons have been uncovered. There are $2m-n$ cards from which A can choose; call the $n$ cards that match a previously uncovered singleton "old", and the other $2m-2n$ cards "new". At $A$ 's turn, he might:

• turn over two different new cards, scoring nothing, with the play passing to B,
• turn over a new card and then an old card. The play would then pass to B, who would take the now declared pair, and retain the play.
• turn over a new card and its pair,
• turn over an old card, and then its pair.

Thus we obtain the recurrence relation $A_{a,b,m,n} \; = \; \frac{4(m-n)(m-n-1)}{(2m-n)(2m-n-1)}B_{a,b,m,n+2} + \frac{2(m-n)n}{(2m-n)(2m-n-1)}B_{a,b+1,m-1,n} + \frac{2(m-n)}{(2m-n)(2m-n-1)}A_{a+1,b,m-1,n} + \frac{n}{2m-n}A_{a+1,b,m-1,n-1}$ Similar arguments apply to when it is B's turn to play, and we obtain the recurrence relation $B_{a,b,m,n} \; = \; \frac{4(m-n)(m-n-1)}{(2m-n)(2m-n-1)}A_{a,b,m,n+2} + \frac{2(m-n)n}{(2m-n)(2m-n-1)}A_{a+1,b,m-1,n} + \frac{2(m-n)}{(2m-n)(2m-n-1)}B_{a,b+1,m-1,n} + \frac{n}{2m-n}B_{a,b+1,m-1,n-1}$ and we have the initial conditions $A_{a,b,0,0} \; = \; B_{a,b,0,0} \; = \; \left\{ \begin{array}{lll} 1 & \hspace{1cm} & a > b \\ 0 & & \mathrm{o.w.} \end{array}\right.$ We also have the probabilities $D^A_{a,b,n,m}$ and $D^B_{a,b,n,m}$ of a draw where (respectively) A and B play first and $a,b,n,m$ have the same meaning as above. These probabilities have the recurrence relations $\begin{aligned} D^A_{a,b,m,n} & = \; \frac{4(m-n)(m-n-1)}{(2m-n)(2m-n-1)}D^B_{a,b,m,n+2} + \frac{2(m-n)n}{(2m-n)(2m-n-1)}D^B_{a,b+1,m-1,n} + \frac{2(m-n)}{(2m-n)(2m-n-1)}D^A_{a+1,b,m-1,n} + \frac{n}{2m-n}D^A_{a+1,b,m-1,n-1} \\ D^B_{a,b,m,n} & = \; \frac{4(m-n)(m-n-1)}{(2m-n)(2m-n-1)}D^A_{a,b,m,n+2} + \frac{2(m-n)n}{(2m-n)(2m-n-1)}D^A_{a+1,b,m-1,n} + \frac{2(m-n)}{(2m-n)(2m-n-1)}D^B_{a,b+1,m-1,n} + \frac{n}{2m-n}D^B_{a,b+1,m-1,n-1} \end{aligned}$ together with the initial conditions $D^A_{a,b,0,0} \; = \; D^B_{a,b,0,0} \; = \; \left\{ \begin{array}{lll} 1 & \hspace{1cm} & a = b \\ 0 & & \mathrm{o.w.} \end{array}\right.$ The probability that A wins a game with $n$ pairs of cards, given that A goes first, is thus $p_A(n) \; = \; A_{0,0,n,0}$ while the probability that B wins a game with $n$ pairs of cards, given that A goes first, is $p_B(n) \; = \; 1 - A_{0,0,n,0} - D^A_{0,0,n,0}$ Careful inspection shows that these recurrence relations are sufficient to evaluate all these probabilities. Computer checking gives that the smallest value of $n$ for which both of $p_A(n)$ and $p_B(n)$ are less than $\tfrac12$ is $n=8$ , with $p_A(8) \; =\; \frac{185527}{405405} \hspace{2cm} p_B(8) \; =\; \frac{870778}{2027025}$ making the answer $185527 + 405405 = \boxed{590932}$ .

The following Python Code shows that the least number of cards needed for the probability of either robot winning to be less than half is $8$ cards, so that Player $1$ wins at a $\frac{185527}{405405} \approx 0.4576$ probability, Player $2$ wins at a $\frac{870778}{2027025} \approx 0.4296$ probability, and a tie happens at a $\frac{76204}{675675} \approx 0.1128$ probability.

Therefore $p = 185527$ , $q = 405405$ , and $p + q = \boxed{590932}$ .

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

# Robot Concentration
# Python 2.7.3

from fractions import Fraction

# function that takes a sequence of cards (denoted by A's, B's, C's, etc.)
#   and determines the winner
def find_winner(seq):
    winner = ""
    revealed = []
    pturn = 1
    flip = 1
    flip1card = ""
    index = 0
    pmatches = []
    for a in range(0, 3):
        pmatches.append(0)
    # go through each card in order of seq
    while True:
        if flip == 1:
            # first card flip
            flip1card = seq[index]
            if seq[index] in revealed:
                # if it matches a card that has been revealed on a previous
                #   turn, then match those cards and start again
                revealed.remove(seq[index])
                pmatches[pturn] += 1
                index += 1
                flip = 1
            else:
                # if it doesn't match a card that has been revealed on a
                #   previous turn, then move on to a second card flip
                revealed.append(seq[index])
                flip = 2
                index += 1
        elif flip == 2:
            # second card flip
            if flip1card == seq[index]:
                # if it matches the first card flip, then match those
                #   cards and start again
                revealed.remove(seq[index])
                pmatches[pturn] += 1
                index += 1
                flip = 1
            else:
                # if it doesn't match the first card flip, then the turn
                #   is over
                if pturn == 1:
                    pturn = 2
                elif pturn == 2:
                    pturn = 1
                if seq[index] in revealed:
                    revealed.remove(seq[index])
                    pmatches[pturn] += 1
                else:
                    revealed.append(seq[index])
                index += 1
                flip = 1
        if index == len(seq):
            # at the end of the sequence of cards, finish the game
            break
    # determine the winner by the number of matches made by each player
    if pmatches[1] > pmatches[2]:
        winner = "p1"
    elif pmatches[2] > pmatches[1]:
        winner = "p2"
    else:
        winner = "tied"
    return winner

# function that subtracts a letter one at a time from another string
#   (needed for the game_data function)
def str_subtract(str1, str2):
    for a in range(0, len(str2)):
        str1 = str1.replace(str2[a], "", 1)
    return str1

# function that finds all the unique sequences given the number of pairs,
#   and calculates the probability of winning
def game_data(pairs):
    letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    # find unique sequences, for example, for two pairs the unique
    #   sequences are AABB, ABAB, and ABBA (BBAA, BABA, and BAAB are
    #   not counted because if A and B are swapped the sequence is
    #   already given)
    bank = ""
    for a in range(0, pairs):
        bank += letters[a]
        bank += letters[a]
    seqposs = ["A"]
    seqpossnext = []
    for a in range(1, len(bank)):
        for b in range(0, len(seqposs)):
            rem = str_subtract(bank, seqposs[b])
            for c in range(0, letters.find(max(seqposs[b])) + 2):
                if letters[c] in rem:
                    seqpossnext.append(seqposs[b] + letters[c])
        seqposs = []
        seqposs = seqpossnext
        seqpossnext = []
    # run find_winner function with each possible unique sequence
    #   and tally up the winners
    p1count = 0
    p2count = 0
    tiedcount = 0
    for a in range(0, len(seqposs)):
        winner = find_winner(seqposs[a])
        if winner == "p1":
            p1count += 1
        elif winner == "p2":
            p2count += 1
        elif winner == "tied":
            tiedcount += 1
    # display the results
    print "For", n, "pair(s):"
    print "  Player 1 Wins:", format(1.0 * p1count / len(seqposs), '.4f'), "or", Fraction(1.0 * p1count / len(seqposs)).limit_denominator()
    print "  Player 2 Wins:", format(1.0 * p2count / len(seqposs), '.4f'), "or", Fraction(1.0 * p2count / len(seqposs)).limit_denominator()
    print "  Tied Games:   ", format(1.0 * tiedcount / len(seqposs), '.4f'), "or", Fraction(1.0 * tiedcount / len(seqposs)).limit_denominator()

# find and display probabilities for 1-8 pairs
for n in range(1, 9):
    game_data(n)