Sum of random cards puzzle

Here’s a nice puzzle, via Christian Lawson-Perfect and Tanya Khovanova:

There are 100 cards with integers from 1 to 100. You have three possible scenarios: you pick 18, 19, or 20 cards at random. For each scenario, you need to estimate the probability that the sum of the cards is even. You do not need to do the exact calculation; you just need to say whether the probability is less than, equal to, or more than 1/2.

Solution

For a card with the number \(k\), construct the term \(a(k) = 1 + (-1)^kx\), and consider the product of these terms for all the cards:

\[ A=a(1)a(2)\cdots a(100)=(1-x)^{50}(1+x)^{50}. \]

The expansion of this product consists of \(2^{100}\) monomials of the form \((-1)^{k_1+k_2+\cdots+k_n}x^n\), and each such monomial corresponds to a unique combination of \(n\) cards \(k_1, k_2, \ldots, k_n\). The coefficient of this monomial is \(+1\) when the sum of the cards \(k_1+\cdots+k_n\) is even and \(-1\) when it’s odd.

Therefore, once we reduce \(A\) by adding up all monomials of the same degree, the coefficient in front of \(x^n\) will be the number of \(n\)-card combinations with an even sum minus the number of \(n\)-card combinations with the odd sum.

And the simplified form of \(A\) is

\[ A=(1-x)^{50}(1+x)^{50}=(1-x^2)^{50} = \sum_{m=0}^{50} {50 \choose m} (-1)^m x^{2m}. \]

The fact that all terms here have even powers means that for odd values of \(n\), the numbers of even-sum and odd-sum \(n\)-card combinations are exactly equal, and so the probability to draw an even sum is exactly 1/2. And for even values of \(n=2m\), the probability is greater than 1/2 when \((-1)^m > 0\), i.e. when \(n\) is divisible by 4, and less than 1/2 otherwise.

Bonus: calculating the probabilities

One way to calculate these probabilities is by a recursive calculation. Here’s a Haskell function that does that.

{-# LANGUAGE LambdaCase #-}
import Data.Ratio
import Data.MemoUgly (memo)

prob_even
  :: ( Integer {- number of even cards -}
     , Integer {- number of odd cards -}
     , Integer {- number of cards to draw -}
     )
  -> Rational {- probability of drawing an even sum -}
prob_even = memo $ \case
  (_, _, 0) -> 1 -- no cards to draw; the sum is 0
  (_, 0, _) -> 1 -- all even cards
  (0, _, to_draw) -> fromInteger $ 1 - (to_draw `mod` 2) -- all odd cards
  (num_even, num_odd, to_draw) ->
    let
      prob_1st_odd = num_odd % (num_even + num_odd)
      if_1st_even = prob_even (num_even-1, num_odd, to_draw-1)
      if_1st_odd = 1 - prob_even (num_even, num_odd-1, to_draw-1)
    in
      prob_1st_odd * if_1st_odd + (1-prob_1st_odd) * if_1st_even

E.g. for \(n = 20\), this gives

\[p(\text{even})=\frac{26088826721}{52177653441} = \frac{1}{2} + \frac1{104355306882}.\]

Notice how close this is to 1/2.

Alternatively, we can derive the probabilities from the proof itself. For \(n = 2m\), the number of even combinations minus the number of odd combinations is \((-1)^m {50 \choose m}\), and their sum is the total number of \(n\)-card combinations, \(100 \choose 2m\).

Then the probability of drawing an even sum is

\[p(\text{even})=\frac{\frac{1}{2}\left((-1)^m {50 \choose m} + {100 \choose 2m}\right)}{100 \choose 2m}=\frac12+(-1)^m\frac{50 \choose m}{2 {100 \choose 2m}}.\]

And sure enough, for \(n=20\),

\[p(\text{even}) = \frac12+\frac{50 \choose 10}{2 {100 \choose 20}} = \frac12 + \frac1{104355306882}. \]