Do not remember.

To analyze the problem, let us first understand card shuffling as follows. We start with 1 card. The second card moves to one of two "slots" chosen uniformly at random: either to the left or to the right of the card already in the shuffle. In general, the i-th card chooses one out of i slots. When all n cards are in the shuffle, we have a random permutation of cards. Now, let us see how the process of populating two urns with n balls, as outlined in the puzzle, is related to card shuffling. Imagine that the first two balls are joined with a rod. These correspond to the first card in the pile. The third ball (which corresponds to the second card) has two choices. In general, the i-th ball corresponds to card i-1 and has i-1 choices. Now, the first card could be in any position uniformly at random. This means that all configurations with a balls in the first pile and b balls in the second pile, with a + b = n, are equally likely. In other words, the following configurations of balls in the two urns are all equally likely: (1, n-1), (2, n-2), (3, n-3), ..., (n-3, 3), (n-2, 2) and (n-1, 1). It turns out that the average number of balls in the smaller urn is (n+1) / 4 if n is odd, and n^{2} / (4n - 4) when n is even. As n increases, both quantities converge to n/4.

**Reference**: George Polya, *Sur quelques points de la theorie des probabilites*, Annales de L'Institut, Henri Poincare 1 (1930), pages 117-161.

© Copyright 2008—2017, Gurmeet Manku.

Send me email or a
Sarahah message!