Skip to main content
4 of 7
edited tags
Charles
  • 9.1k
  • 1
  • 38
  • 76

Fairest way to choose gifts

Suppose that a parent brings home from a trip $2n$ gifts of roughly
equal value for his/her two children. The children get to choose one
at a time which gifts they want. What is the fairest way to do this?
For instance, if $n=1$ then clearly one child chooses first
(determined by a coin flip) and the other child chooses second. If we
denote the children by 0 and 1, then this method is described by the
choice sequence 01 (assuming, as I do from now on, that 0 choose
first). Now suppose $n=2$. The choice sequence 0101 is clearly biased
toward 0, since 0 has the first choice at the beginning and after both
have chosen one gift. The fairest sequence by any reasonable criterion
is 0110. What about general $n$? If $n=2^k$, an argument can be made
that the fairest sequence is the first $n$ terms of the Thue-Morse
sequence
(http://mathworld.wolfram.com/Thue-MorseSequence.html). Another
argument can be made that the fairest sequence $a_1,\dots, a_n$ is one
that maximizes the value of $k$ for which the polynomial
$(1-2a_1)x^{n-1} + (1-2a_2)x^{n-2}+\cdots+(1-2a_n)$ and its first $k$
derivatives vanish at $x=1$. (The Thue-Morse sequence does not have
this property, though I cannot recall where I once saw this.)

Has this problem received any attention? What is a reference for the
problem of maximizing $k$?

Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279