Question

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

Answer 1

Очевидно то, что количество шаров каждого из цветов должно отличаться на минимальное число. Обозначим цвета буквами А, Б, В,... Тогда первоначально картина будет такая:  А11 Б12 В13 ... И19 К20 Теперь произведём замену таким образом, чтобы максимальное число стало минимальным, то есть от 20 отнимем 9 и прибавим к 11. Далее последовательно проделаем тот же трюк со следующей из оставшихся : от 19 отнимем 7 и прибавим к 12.  В итоге получаем пять чисел пяти пар шаров : 9, 7,5,3,1. Всего их 25. То есть волшебных шаров было 25

Answer 2

Давайте рассмотрим ситуацию более подробно. У нас есть 10 различных цветов шариков, и мы знаем, что каждого цвета в сундуке находится разное количество шариков.

Пусть количество шариков каждого цвета в первом списке убывает, тогда во втором списке цвета будут идти в точности в обратном порядке. Пусть N1, N2, ..., N10 обозначают количество шариков каждого цвета в первом списке.

Тогда во втором списке цвета будут идти в порядке увеличения количества шариков, то есть второй список будет иметь вид N10, N9, ..., N1.

Мы знаем, что сумма всех шариков в первом списке равна сумме всех шариков во втором списке. Если S обозначает общее количество шариков, то мы можем записать следующее уравнение:

N1 + N2 + ... + N10 = N10 + N9 + ... + N1 = S

Заметим, что если мы поместим волшебные шарики в список с меньшим количеством шариков, то они автоматически попадут во второй список с большим количеством шариков, так как во втором списке цвета идут в обратном порядке.

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

Предположим, что наименьшее количество волшебных шариков равно M. Тогда мы должны выбрать M цветов из 10 возможных цветов и поместить в них волшебные шарики. Количество оставшихся обычных шариков будет равно (155 - M), и они должны быть распределены между оставшимися (10 - M) цветами.

Мы знаем, что общая сумма шариков в первом списке равна общей сумме шариков во втором списке:

N1 + N2 + ... + N10 = N10 + N9 + ... + N1

M + (155 - M) = (10 - M) + (10 - M - 1) + ... + 1

155 = (10 - M)(10 - M + 1) / 2

310 = (10 - M)(11 - M)

Теперь мы можем перебрать возможные значения M и найти такое значение, при котором выполняется это уравнение:

M = 1: 9 * 10 = 90 (не выполняется) M = 2: 8 * 9 = 72 (не выполняется)