Question

В сундуке у Хагрида хранится 275 шариков десяти различных цветов. Некоторые шарики волшебные и могут в разные моменты оказаться любого из этих десяти цветов (но меняют цвет только тогда, когда сундук закрыт и заперт). Однажды Хагрид открыл сундук, пересчитал шарики каждого цвета (каждого цвета оказалось разное количество шариков), выписал список цветов в порядке убывания количества шариков, закрыл и запер сундук. На следующий день Хагрид проделал то же самое и обнаружил, что в его втором списке цвета идут в точности в обратном порядке (по отношению к первому списку). Какое наименьшее количество волшебных шариков может быть в сундуке?

Answer 1

Имеем 5 пар по 55 шариков  (5*55=275)

Пары меняющиеся местами (по вертикали)

                               23    24    25    26    27

                               32     31    30    29    28

Смена цвета          9       7      5       3     1

Волшебных   9+7+5+3+1 = 25

Answer 2

Пусть n - это количество десяти различных цветов шариков, а a1, a2, ..., an - это количество шариков каждого цвета в порядке убывания в первом списке. Тогда во втором списке количество шариков каждого цвета будет a_n, a_(n-1), ..., a_1 в порядке убывания.

Так как количество шариков каждого цвета оказалось разным в обоих списках, то существует хотя бы одна пара цветов (ai и aj), количество шариков которых в первом списке отличается от количества шариков во втором списке.

Но так как эти два списка отличаются только порядком следования цветов, то существует цвет ak, количество шариков которого в первом списке находится на том же месте, что и количество шариков цвета ai во втором списке.

Таким образом, количество шариков цвета ai + количество шариков цвета ak = количество шариков цвета aj + количество шариков цвета ak.

Из этого следует, что количество шариков цвета ai - количество шариков цвета aj = количество шариков цвета aj - количество шариков цвета ak.

Это означает, что разность между количествами шариков соседних цветов в первом списке равна разности между количествами шариков соседних цветов во втором списке.

Поскольку количество шариков каждого цвета в первом списке оказалось разным, разности между количествами шариков соседних цветов в первом списке также различны. Аналогично, разности между количествами шариков соседних цветов во втором списке также различны.

Допустим, что минимальное количество волшебных шариков равно m.

Тогда у нас есть две последовательности из n-1 различных чисел (разности между количествами шариков соседних цветов в первом списке и разности между количествами шариков соседних цветов во втором списке), и все эти разности больше или равны m.

Мы знаем, что сумма элементов последовательности из n-1 различных чисел равна сумме чисел от 1 до n-1, что равно (n-1)(n-1+1)/2 = n(n-1)/2.

Таким образом, сумма разностей между количествами шариков соседних цветов в первом списке и сумма разностей между количествами шариков соседних цветов во втором списке равны n*(n-1)/2.

Так как разности между количествами шариков соседних цветов в первом списке и во втором списке различны, то сумма разностей в первом списке и сумма разностей во втором списке не могут иметь общих элементов.

Таким образом, сумма разностей в первом списке + сумма разностей во втором списке = n*(n-1)/2 + n*(n-1)/2 = n*(n-1) меньше, чем сумма элементов в первом списке + сумма элементов во втором списке = 275.

Так как n >= 2 (потому что у нас 10 цветов), то n*(n-1) больше или равно 2*(2-1) = 2.

Таким образом, минимальное значение n*(n-1) равно 2, а значит, минимальное значение n равно 2.

Таким образом, минимальное количество волшебных шариков равно 2.