Сумма произведений количеств монет при разбиении
Задача
Двадцать пять монет раскладывают по кучкам следующим образом. Сначала их произвольно разбивают на две группы. Затем любую из имеющихся групп снова разбивают на две группы, и так далее до тех пор, пока каждая группа не будет состоять из одной монеты. При каждом разбиении какой-либо группы на две записывается произведение количеств монет в двух получившихся группах. Чему может быть равна сумма всех записанных чисел?
Решение
Первый способ. Изобразим монеты точками и соединим каждую пару точек отрезком. Получим 25(25 – 1) : 2 = 300 отрезков. При каждом разбиении одной группы монет на две будем стирать все отрезки, соединяющие точки, соответствующие монетам, оказавшимся в разных группах. Пусть на некотором шаге мы разбили монеты одной из уже имевшихся групп на две группы по x и y монет. Тогда мы стираем xy отрезков. Это же число мы записываем. Таким образом, сумма записанных чисел – это количество всех стёртых отрезков. Так как изначально было 300 отрезков, а в итоге все отрезки стёрты, то общее количество стёртых отрезков равно 300. Второй способ. Рассмотрим переменную величину S, равную в каждый момент половине суммы квадратов количеств монет в кучках. Изначально
S = 25² : 2 = 312,5, а в самом конце S = (1² + ... + 1²) : 2 = 12,5. Если кучка, в которой было x + y монет разбивается на две кучки по x и y монет, то S уменьшается на ½ (x + y)² – ½ (x² + y²). Таким образом, при каждом разбиении величина S уменьшается на очередное записываемое число. Следовательно, сумма всех записанных чисел равна общему уменьшению величины S, которое равно 312,5 – 12,5 = 300.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь