In [3], Peter Winkler lists “seven problems you think you must not have heard correctly.” I think the following problem deserves to be on such a list:

Alice and Bob are playing a game, searching bins arranged in a grid with rows and columns, in which balls have been placed in distinct randomly selected bins. At each turn, both players simultaneously choose a bin to inspect. The first player to find a ball wins the game. (If both players choose the same bin containing a ball, the game ends in a draw.)

Alice decides to systematically search the grid row by row, left to right across each row, from the top row to the bottom. Bob decides to search columns, top to bottom, left to right. Which player is more likely to win? What if instead the game is played– using the same strategies above– on a slightly wider grid with columns? What if ?

I really like this problem, since a natural reaction might be, “How can either player possibly have an advantage?” (And for just ball, this intuition is correct; neither player has an advantage for any size grid.) While at the same time, it is an undergraduate-level problem to reasonably efficiently compute the exact probabilities of each player winning:

// Compute probability Alice wins by searching rows.
Rational p_grid_search_rows(int rows, int cols, int balls) {
    int ai = 1, aj = 0, bi = 0, bj = 0; // start in upper left
    Integer wins = 0;

    // Evaluate each bin/time where Alice finds a ball first.
    for (int bin = 1; bin <= rows * cols; ++bin) {
        if (++bi == rows) { bi = 0; ++bj; } // move Bob down
        if (bin < aj * rows + ai) { // verify Alice got here first

            // Place remaining balls in unsearched bins.
            int searched = 2 * bin - ai * bj - std::min(ai, bi);
            wins += binomial(rows * cols - searched, balls - 1);
        }
        if (++aj == cols) { aj = 0; ++ai; } // move Alice right
    }
    return Rational(wins, binomial(rows * cols, balls));
}

The result is that for the original problem with , Alice is at a very slight disadvantage, with an expected return on a unit wager of approximately -0.000274524, or -0.027%. But for most “wide” grids with more columns than rows, Alice has the advantage: intuitively, Alice spends more time exploring new territory, while Bob has to waste more turns on bins that Alice has already searched.

The figure below shows that it’s more complicated than this, though, indicating which player has the advantage as we vary the grid size, keeping the number of balls fixed (the three example grid sizes above are highlighted in yellow):

I first encountered this problem in [1] and [2], where the problem is generalized to consider search strategies as arbitrary permutations of the bins.

References:

1. Chow, Timothy Y., Fair permutation problem and solution [PDF]
2. Simons, Jim, solution 11523 in Problems and Solutions, The American Mathematical Monthly, 119(9) November 2012, p. 801-803 [JSTOR]
3. Winkler, P., Seven Puzzles You Think You Must Not Have Heard Correctly, with solutions [PDF]