Project Euler

Waiting for a Pair

A standard 52-card deck contains 13 ranks across four suits. Cards are drawn without replacement from a shuffled deck until either two consecutive draws form a pair (same rank) or all 52 cards are...

Source sync Apr 19, 2026

Problem #0856

Level Level 18

Solved By 737

Languages C++, Python

Answer 17.09661501

Length 438 words

probabilitydynamic_programmingbrute_force

A standard 52-card deck comprises 13 ranks in four suits. A pair is a set of two cards of the same rank.

Cards are drawn, without replacement, from a well shuffled 52-card deck waiting for consecutive cards that form a pair. For example, the probability of finding a pair in the first two draws is $\frac {1}{17}$.

Cards are drawn until either such a pair is found or the pack is exhausted waiting for one. In the latter case we say that all 52 cards were drawn.

Find the expected number of cards that were drawn. Give your answer rounded to eight places after the decimal point.

Problem 856: Waiting for a Pair

Mathematical Analysis

Setup

Let $E$ denote the expected number of cards drawn. After drawing the first card, on each subsequent draw $k$ (having drawn $k-1$ cards already), the probability that the $k$ -th card matches the rank of the $(k-1)$ -th card depends on how many cards of that rank remain.

State-Based Approach

After drawing card $k-1$ with some rank $r$ , suppose there are $m$ remaining cards of rank $r$ among the $52-(k-1)$ remaining cards. The probability of a consecutive match is:

P(\text{match at position } k) = \frac{m}{52 - (k-1)}

We need to track how many cards of each rank have been drawn. However, for the consecutive pair condition, we only care about the rank of the most recently drawn card.

Dynamic Programming

We define a state by $(k, c)$ where $k$ is the number of cards drawn so far and $c$ is how many cards of the same rank as the last drawn card remain in the deck. The transition probabilities account for drawing either a matching card (stopping) or a non-matching card (continuing).

When we draw a non-matching card, we need the distribution of how many cards share the rank of the newly drawn card. This depends on the overall distribution of remaining ranks.

We track states as $(n, c, \text{rank\_distribution})$ where the rank distribution describes how many ranks have 1, 2, 3, or 4 remaining cards.

Probability Calculation

The expected value is computed via:

E = \sum_{k=1}^{52} k \cdot P(\text{stop at card } k)

where $P(\text{stop at card } k)$ is the probability that the first consecutive pair occurs exactly at position $k$ (or $k=52$ if no pair is found).

Editorial

We use dynamic programming over the distribution of remaining cards by rank. The state is. At each step, we either match (stop) or draw a card of a different rank, updating the distribution. We $(n_1, n_2, n_3, n_4, c)$ : where $n_i$ = number of ranks with exactly $i$ cards remaining, and $c$ = cards remaining of the last-drawn rank.

Pseudocode

$(n_1, n_2, n_3, n_4, c)$: where $n_i$ = number of ranks with exactly $i$ cards remaining, and $c$ = cards remaining of the last-drawn rank

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

The number of states is bounded by the number of partitions of 13 ranks into groups by count, times the possible values of $c$ (0-3), making this tractable with memoization.

Answer

\boxed{17.09661501}

C++ project_euler/problem_856/solution.cpp

#include <bits/stdc++.h>
using namespace std;

map<tuple<int,int,int,int,int>, double> memo;

double E(int n1, int n2, int n3, int n4, int c) {
    int R = n1 + 2*n2 + 3*n3 + 4*n4 + c;
    if (R == 0) return 0.0;

    auto key = make_tuple(n1, n2, n3, n4, c);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;

    double match_prob = (double)c / R;
    double nonmatch_prob = 1.0 - match_prob;

    if (nonmatch_prob < 1e-15) {
        memo[key] = 1.0;
        return 1.0;
    }

    int total_other = n1 + 2*n2 + 3*n3 + 4*n4;
    double ev_nonmatch = 0.0;

    int nj_arr[5] = {0, n1, n2, n3, n4};
    for (int j = 1; j <= 4; j++) {
        if (nj_arr[j] == 0) continue;
        double prob_j = (double)(j * nj_arr[j]) / total_other;

        int nn1 = n1, nn2 = n2, nn3 = n3, nn4 = n4;
        if (j == 1) nn1--;
        else if (j == 2) nn2--;
        else if (j == 3) nn3--;
        else nn4--;

        if (c == 1) nn1++;
        else if (c == 2) nn2++;
        else if (c == 3) nn3++;

        int new_c = j - 1;
        ev_nonmatch += prob_j * E(nn1, nn2, nn3, nn4, new_c);
    }

    double result = 1.0 + nonmatch_prob * ev_nonmatch;
    memo[key] = result;
    return result;
}

int main() {
    double answer = 1.0 + E(0, 0, 0, 12, 3);
    printf("%.8f\n", answer);
    return 0;
}

Python project_euler/problem_856/solution.py

from functools import lru_cache

@lru_cache(maxsize=None)
def E(n1, n2, n3, n4, c):
    """
    We have already drawn some cards. The last drawn card had rank R with c
    copies remaining in the deck. The other ranks have n1 ranks with 1 card,
    n2 with 2, n3 with 3, n4 with 4 cards remaining.

    Returns the expected number of ADDITIONAL cards to draw until we stop.
    """
    R = n1 + 2*n2 + 3*n3 + 4*n4 + c  # total remaining cards
    if R == 0:
        return 0.0  # deck exhausted, already stopped

    # Draw next card:
    # Prob c/R: matches last card -> stop, draws 1 more card
    # Prob (R-c)/R: doesn't match -> draws 1 card and continues

    match_prob = c / R
    nonmatch_prob = 1.0 - match_prob

    if nonmatch_prob == 0:
        return 1.0  # forced match

    # For non-match: the drawn card comes from some other rank.
    # The old "last rank" (c remaining) goes back to pool.
    # We pick a new card from ranks in pool + returned rank... no wait.
    # The old last rank IS part of the deck but NOT in n1..n4.
    # When we draw a non-matching card, it must come from ranks in n1..n4.
    # After drawing it:
    #   - old last rank (c remaining) returns to n_i counts
    #   - the drawn rank (had j cards, now has j-1) becomes new "last rank" with c'=j-1

    ev_nonmatch = 0.0
    # Total non-matching cards = n1 + 2*n2 + 3*n3 + 4*n4
    total_other = n1 + 2*n2 + 3*n3 + 4*n4
    assert abs(total_other - (R - c)) < 1e-9

    for j in range(1, 5):
        nj = [0, n1, n2, n3, n4][j]
        if nj == 0:
            continue
        prob_j = (j * nj) / total_other  # prob of drawing from a rank with j cards

        # New state:
        # - Old last rank returns to pool: if c > 0, add to n_c
        # - Drawn rank: had j cards, now has j-1, becomes new last rank
        # - Remove drawn rank from pool (decrement n_j)
        new_n1, new_n2, new_n3, new_n4 = n1, n2, n3, n4

        # Remove the drawn rank from its group
        if j == 1: new_n1 -= 1
        elif j == 2: new_n2 -= 1
        elif j == 3: new_n3 -= 1
        else: new_n4 -= 1

        # Return old last rank to pool
        if c == 1: new_n1 += 1
        elif c == 2: new_n2 += 1
        elif c == 3: new_n3 += 1

        new_c = j - 1

        ev_nonmatch += prob_j * E(new_n1, new_n2, new_n3, new_n4, new_c)

    return 1.0 + nonmatch_prob * ev_nonmatch

# Test with 4-card deck (2 ranks, 2 suits)
# After drawing first card: 1 rank with 1 card left (last drawn), 1 rank with 2 cards
# n1=0, n2=1, n3=0, n4=0, c=1
test = 1.0 + E(0, 1, 0, 0, 1)
print(f"4-card deck: {test:.8f} (expected 3.0)")

# Full 52-card deck
# After drawing first card: 12 ranks with 4 cards, c=3
answer = 1.0 + E(0, 0, 0, 12, 3)
print(f"{answer:.8f}")