, 2013

Combinatorics Difficulty 5.9 AIME, harder Prove it Japan

Let $n, k$ be positive integers satisfying $n \ge k$ .
There is a group consisting of $n$ people. Each person of this group belongs to one and only one of $k$ clubs, called club $C_1, C_2, \dots, C_k$ . Each club has at least one member belonging to it. Prove that it is possible to distribute $n^2$ pieces of cake to these $n$ people in such a way to satisfy all of the following conditions:
* Every one receives at least 1 piece of cake.
* For each $i$ $1 \le i \le k$ , every member of the club $C_i$ receives $a_i$ pieces of cake.
* If $1 \le i < j \le k$ , then $a_i > a_j$ is satisfied.

Solution

Let for each $i$ , $1 \le i \le k$ , $x_i$ be the number of people belonging to the club $C_i$ .
If we set $a_i = x_i + 2(x_{i+1} + x_{i+2} + \cdots + x_k)$ for each $i$ , then we claim that $a_1, a_2, \cdots, a_k$ satisfy all the conditions of the problem. The condition $a_i > 0$ is obvious. For $1 \le i \le k-1$ , we have $a_i = x_i + x_{i+1} + a_{i+1} > a_{i+1}$ which shows that $a_i > a_j$ holds for $1 \le i < j \le k$ . Finally, the total number of the cakes distributed is given by
$a_1x_1 + a_2x_2 + \cdots a_kx_k = \sum_{i=1}^{k} x_i^2 + 2 \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} x_i x_j = (x_1 + x_2 + \cdots + x_k)^2 = n^2.$
Thus our claim is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.