Maths Olympiad Prep

Library / /15 of 25

Combinatorics Difficulty 6.6 National olympiad Prove it Russia

Pasha chose 2017 (not necessarily distinct) positive integers a1,a2,,a2017a_1, a_2, \dots, a_{2017}, and then he plays a solitaire game. Initially, he has 2017 empty large boxes and an unbounded supply of small stones. By a move, Pasha adds a1a_1 stones into some box by his choice, a2a_2 stones into any other box by his choice, ..., a2017a_{2017} stones into the remaining box. His aim is to equalize the numbers of stones in all boxes. Can he choose the initial numbers so that the aim is reachable in 43 moves, but unreachable in any smaller (nonzero) number of moves?

Паша выбрал 2017 (не обязательно различных) положительных целых чисел a1,a2,,a2017a_1, a_2, \dots, a_{2017}, после чего играет в пасьянс. Изначально у него есть 2017 пустых больших коробок и неограниченное количество маленьких камешков. За один ход Паша кладёт a1a_1 камней в какую-то коробку по своему выбору, a2a_2 камней — в другую коробку по своему выбору, ..., a2017a_{2017} камней — в оставшуюся коробку. Его цель — уравнять количество камней во всех коробках. Может ли он выбрать начальные числа так, чтобы цель была достижима за 43 хода, но недостижима ни за какое меньшее (ненулевое) число ходов?

Solutions — 2

Solution 1

Yes.

Notice that 2017=4346+392017 = 43 \cdot 46 + 39. One example of Pasha's numbers consists of 39 twos, 46 numbers equal to 44, and ones as the remaining numbers.

To achieve the goal in 43 moves, Pasha chooses 39 boxes in which he always puts 2 stones—after 43 moves, each of these will contain 432=8643 \cdot 2 = 86 stones. The remaining boxes are divided into 43 groups of 46 boxes each; on the ii-th move, he puts 44 stones into all boxes of the ii-th group and 1 stone into the others—in each group, there will be 44+421=8644 + 42 \cdot 1 = 86 stones, so all boxes will have the same number of stones.

It remains to prove that the goal cannot be achieved in fewer moves. Suppose Pasha made k<43k < 43 moves. Then in some box AA, 44 stones were placed in one move, so it will have at least 44+(k1)1=43+k44 + (k-1) \cdot 1 = 43 + k stones. On the other hand, since 46k<201746k < 2017, there is some box BB that never received 44 stones, so it will have at most 2k2k stones. Since k<43k < 43, we have 2k<k+432k < k + 43, so box BB has fewer stones than box AA. Thus, Pasha has not yet achieved the goal.

Remark. The example given is not unique. For example, a set consisting of 42 ones, 201743=19742017 - 43 = 1974 numbers equal to a>1a > 1, and one number equal to 43a4243a - 42 also works. There are even examples with all numbers pairwise distinct; however, checking that they work is somewhat more difficult than for the examples given above.

Solution 2

Да, мог.

Заметим, что 2017=4346+392017 = 43 \cdot 46 + 39. Приведём пример Пашиных чисел, при которых требуемое выполняется. Пусть среди его чисел будут 39 двоек, 46 чисел, равных 44, а остальные — единицы.
Чтобы добиться требуемого за 43 хода, Паша выбирает 39 коробок, в которые он всегда кладёт по 2 камня — через 43 хода в них окажется по 432=8643 \cdot 2 = 86 камней. Остальные коробки он разбивает на 43 группы по 46 коробок; на ii-м ходу он положит по 44 камня во все коробки ii-й группы и по одному камню — в каждой группе будет по 44+421=8644+42 \cdot 1 = 86 камней, то есть во всех коробках будет поровну камней.

Осталось доказать, что за меньшее число ходов требуемое невыполнимо. Пусть Паша сделал k<43k < 43 ходов. Тогда в какую-то коробку AA попало 44 камня на одном ходу, и в ней будет не меньше, чем 44+(k1)1=43+k44 + (k-1) \cdot 1 = 43 + k камней. С другой стороны, поскольку 46k<201746k < 2017, в какую-то коробку BB ни на одном из ходов не попадёт 44 камня, то есть в ней будет не больше 2k2k камней. Поскольку k<43k < 43, имеем 2k<k+432k < k + 43, а значит, в коробке BB меньше камней, чем в AA. Таким образом, Паша ещё не добился требуемого.

Замечание. Приведённый пример — не единственный. Например, подойдёт также набор чисел, состоящий из 42 единиц, 201743=19742017 - 43 = 1974 чисел, равных a>1a > 1, и одного числа, равного 43a4243a - 42. Существуют даже примеры с попарно различными числами; однако проверка того, что они подходят, несколько труднее, чем для примеров, приведённых выше.

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.