Japan 2013 Final Round

Question

Let n, k be positive integers satisfying n 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, , 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 i k, every member of the club C_i receives a_i pieces of cake. * If 1 i < j k, then a_i > a_j is satisfied.

Accepted Answer

Let for each i, 1 i 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 + + x_k) for each i, then we claim that a_1, a_2, , a_k satisfy all the conditions of the problem. The condition a_i > 0 is obvious. For 1 i 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 i < j k. Finally, the total number of the cakes distributed is given by a_1x_1 + a_2x_2 + a_kx_k = _i=1^k x_i^2 + 2 _i=1^k-1 _j=i+1^k x_i x_j = (x_1 + x_2 + + x_k)^2 = n^2. Thus our claim is proved.