Maths Olympiad Prep

Library / /14 of 22

Combinatorics Difficulty 6.8 National olympiad Prove it Croatia

Let a2018a \ge 2018 be a real number. There are 2018 bowls, each containing a finite number of balls. It is known that the weight of each ball is of the form aka^k, where kk is an integer, and that the total weight of balls in any bowl is the same. Let BB denote the total number of occurrences of the most frequently used weight.
Determine the smallest possible value of BB.

Solution

The smallest value BB can attain is 2018.

Without loss of generality we can assume that the weight of the lightest ball is equal to 1. If this is not the case, we can divide all the weights by the weight of the lightest ball.

Let us assume that there are at most 2017 balls of each weight appearing in all the bowls. Let nn be a non-negative integer such that ana^n is the weight of the heaviest ball.

Since there are at most 2017 balls of the weight ana^n, there exists at least one bowl which does not contain any balls of weight ana^n, and moreover, all of the balls in that bowl are lighter than ana^n. Thus, the total weight of balls in that bowl is at most
2017k=0n1ak=2017an1a12017an12017=an1<an, 2017 \cdot \sum_{k=0}^{n-1} a^k = 2017 \cdot \frac{a^n - 1}{a - 1} \le 2017 \cdot \frac{a^n - 1}{2017} = a^n - 1 < a^n,
which leads to contradiction.

So, there exists at least one weight which appears at least 2018 times.

On the other hand, if we put a ball of weight 1 in each bowl, then all bowls contain the same weight, while the weight 1 appears exactly 2018 times.

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.