Track / Stage 6 / 160 of 400 #1640 of 2444

Problem 1640

National Olympiad, first round

Combinatorics Difficulty 6.3 Prove it BAMO · United States

In the $O$ - $E$ game, a round starts with player $A$ paying $c$ cents to player $B$ . Then $A$ secretly arranges the numbers $1, 3, 5, 7, 9, 11, 13$ in some order as a sequence $a_{1}, a_{2}, \ldots, a_{7}$ , and $B$ secretly arranges $2, 4, 6, 8, 10, 12, 14$ as a sequence $b_{1}, b_{2}, \ldots, b_{7}$ . Finally, the players show their sequences and $B$ pays $A$ one cent for each $i$ in $X=\{1,2,3,4,5,6,7\}$ such that $a_{i}<b_{i}$ . This finishes the round. What number $c$ would make the game fair? (The game is fair if the total payments by $A$ to $B$ equals the total payments by $B$ to $A$ after all possible distinct rounds are played exactly once.)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solutions — 2

Solution 1

Solution:

Let $k$ be in $X$ . There are $7!\,6!\,(8-k)$ choices of the sequences $a_{1}, a_{2}, \ldots, a_{7}$ and $b_{1}, b_{2}, \ldots, b_{7}$ for which $2k-1$ is an $a_{j}$ with $a_{j}<b_{j}$ . Indeed, the $a$ 's can be any of the $7!$ permutations of the 7 odd integers; then $j$ is the subscript such that $a_{j}=2k-1$ , and $b_{j}$ must be one of the $8-k$ numbers in $\{2k, 2k+2, \ldots, 14\}$ ; the remaining 6 even integers can be arranged in $6!$ ways.

The total of the payments by $B$ to $A$ for the $(7!)^{2}$ possible rounds is then
$\sum_{k=1}^{7} 7!\,6!\,(8-k) = 7!\,6!\,(7+6+\cdots+1) = 7!\,6!\,28 = (7!)^{2} 4$
$A$ pays to $B$ a total of $(7!)^{2}c$ ; so $c=4$ makes the game fair.

Solution 2

Solution:

For those who know that the sum of expected values (averages) is the expected value of the sum, we note that in the first spot, $1, 3, 5, 7, 9, 11, 13$ are equally likely, and hence the average payment is the average of the payments for each of these numbers, $7/7, 6/7, 5/7, 4/7, 3/7, 2/7, 1/7$ . Hence in the first spot the average payment is
$\frac{(7/7 + 6/7 + 5/7 + 4/7 + 3/7 + 2/7 + 1/7)}{7} = 4/7 \text{ of a cent. }$
Since there are 7 spots, with an average payment of $4/7$ cent each, the total payment averages 4 cents; so $c=4$ makes the game fair.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.