Question

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

Answer 1

(25-16)+(24-17)+(23-18)+(22-19)+(21-20)=9+7+5+1=25

ответ: 25

Answer 2

Пусть $a_1,a_2,\ldots,a_{10}$ обозначают количество шариков каждого цвета в сундуке, упорядоченные по убыванию. Предположим, что первый список цветов выглядит следующим образом:

$a_1,a_2,\ldots,a_k,b_{k+1},\ldots,b_{10}$,

где $k \leq 9$ и $b_{k+1},\ldots,b_{10}$ - это цвета, которые в сундуке встречаются меньше раз, чем цвет $a_k$.

Тогда второй список цветов должен выглядеть следующим образом:

$b_{10},\ldots,b_{k+1},a_k,a_{k-1},\ldots,a_1$.

Обратите внимание, что количество шариков каждого цвета во втором списке точно такое же, как и в первом списке. Однако цвета идут в обратном порядке, поэтому $b_{10}$ (самый редкий цвет) встречается чаще всего в сундуке, а $a_k$ (самый частый цвет) встречается меньше всего.

Поскольку в сундуке всего 275 шариков, мы можем записать уравнение:

$a_1+a_2+\ldots+a_k+b_{k+1}+\ldots+b_{10}=275.$

После того, как мы переставили цвета второго списка, мы должны иметь:

$b_{10}+\ldots+b_{k+1}+a_k+a_{k-1}+\ldots+a_1=275.$

Учитывая, что $b_{10}$ является наиболее частым цветом в этом списке, мы можем записать неравенство:

$b_{10} \geq \frac{275}{10}=27.5.$

Также заметим, что $a_k$ является наименее частым цветом во втором списке, поэтому $a_k \leq \frac{275}{10}=27.5$.

Наконец, поскольку количество шариков каждого цвета является целым числом, мы должны выбрать наименьшее возможное количество волшебных шариков, чтобы удовлетворить оба неравенства. Таким образом, мы можем выбрать $b_{10}=28$ и $a_k=27$. Это означает, что суммарное количество шариков на девять цветов должно быть равно 247. Теперь мы можем выбрать $a_1=27, a_2=26, \ldots, a_8=20$ и $b_9=19, b_8=18, \ldots,

Answer 3

Пусть $a_1, a_2, \ldots, a_{10}$ — количество шариков каждого цвета в первый день, а $b_1, b_2, \ldots, b_{10}$ — количество шариков каждого цвета во второй день.

Так как цвета в первый день расположены в порядке убывания количества шариков, то $a_1 \geq a_2 \geq \dots \geq a_{10}$, аналогично, $b_1 \leq b_2 \leq \dots \leq b_{10}$. При этом, сумма $a_1 + a_2 + \dots + a_{10}$ равна сумме $b_1 + b_2 + \dots + b_{10}$, поскольку в сундуке всего $275$ шариков.

Давайте рассмотрим цвет с наибольшим количеством шариков, скажем, это цвет $c_1$. В первый день он содержал $a_1$ шариков, а во второй — $b_{10}$. Поскольку $c_1$ — цвет с наибольшим количеством шариков, то $a_1 \geq a_i$ и $b_{10} \geq b_i$ для всех $i \in {1,2,\ldots,10}$.

Так как волшебные шарики могут менять цвет, то количество шариков каждого цвета может быть увеличено или уменьшено на любое неотрицательное число. В частности, мы можем увеличить количество шариков цвета $c_1$ в первый день на некоторое число $x$ и уменьшить количество шариков этого же цвета во второй день на то же число $x$. Тогда количество шариков цвета $c_1$ в первый и второй день станет равным $a_1+x$ и $b_{10}-x$ соответственно.

Таким образом, мы получили новые количество шариков каждого цвета, причем все условия задачи выполняются. Сумма количества шариков при этом не изменится, поэтому мы можем рассматривать задачу для новых значений $a_1+x, a_2, \ldots, a_{10}$ и $b_1, b_2, \ldots, b_9, b_{10}-x$.

Теперь давайте попробуем найти наименьшее возможное значение $x$. Мы хотим, чтобы цвет $c_1$ оказался на $10$-м месте в первый день и на $1$-м месте во второй день, то есть $a_{10} \geq a_1+x