Maths Olympiad Prep

Library / /137 of 152

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Russia

The treasurer of Math republic chose a number α>2\alpha > 2 and issued coins with values of 1 rouble and of αk\alpha^k roubles for all positive integer kk. It turns out that all the values of coins (except for 1) are irrational. May it happen that for any positive integer nn, one may take several coins whose values sum up to nn roubles so that the coins of each value are taken at most six times? (I. Bogdanov, S. Berlov)

Solution

Ответ. Могло.

Покажем, что математики могли выбрать число α=1+292\alpha = \frac{-1 + \sqrt{29}}{2}; это число является корнем уравнения α2+α=7\alpha^2 + \alpha = 7. Ясно, что α>2\alpha > 2. Нетрудно видеть, что при натуральных mm мы имеем (2α)m=am+bm29(2\alpha)^m = a_m + b_m\sqrt{29}, где ama_m и bmb_m — целые числа, причём am<0<bma_m < 0 < b_m при нечётных mm и am>0>bma_m > 0 > b_m при чётных mm. Значит, число αm\alpha^m иррационально.

Осталось показать, что для любого натурального числа nn сумму в nn рублей можно набрать требуемым способом. Рассмотрим все способы набрать nn рублей выпущенными монетами (хотя бы один такой способ существует: можно взять nn рублёвых монет). Выберем из них способ, в котором наименьшее число монет. Предположим, что какая-то монета достоинства αi\alpha^i (i0i \ge 0) встречается в этом способе хотя бы 7 раз. Тогда можно заменить 7 монет по αi\alpha^i монетами достоинств αi+1\alpha^{i+1} и αi+2\alpha^{i+2}. При этом суммарное достоинство монет не изменится (поскольку αi+1+αi+2=7αi\alpha^{i+1} + \alpha^{i+2} = 7\alpha^i), а их количество уменьшится.

Это невозможно по выбору нашего способа. Итак, этот способ удовлетворяет условию.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.