Волшебница Стела имеет 27 магических камней. Первый весит 1 г, второй 2 г, ..., 27-й 27 г. Ей нужно разложить камни в несколько кучек так, чтобы в каждой из кучек самый тяжёлый камень весил столько же, сколько все остальные вместе взятые. Определите, сколько кучек у неё могло получиться.

Пусть у нас есть камни с массой $1, 2, ..., 27$ грамм. Общая масса всех камней: $$\frac{27 \cdot (27 + 1)}{2} = \frac{27 \cdot 28}{2} = 27 \cdot 14 = 378$$ грамм. По условию, в каждой кучке самый тяжёлый камень весит столько же, сколько все остальные вместе взятые. Это значит, что масса самого тяжёлого камня в кучке составляет половину от общей массы этой кучки. Отсюда следует, что общая масса каждой кучки должна быть чётной. Предположим, что в кучке $N$ камней. Пусть массы камней в этой кучке $m_1, m_2, ..., m_N$, где $m_N$ — самый тяжёлый камень. Тогда $m_N = m_1 + m_2 + ... + m_{N-1}$. Общая масса кучки $M = m_1 + m_2 + ... + m_{N-1} + m_N = m_N + m_N = 2m_N$. Таким образом, общая масса каждой кучки всегда чётная. Так как общая масса всех камней $378$ грамм (чётное число), это условие не накладывает ограничений на количество кучек, потому что сумма нескольких чётных чисел всегда чётна. Рассмотрим возможные варианты кучек: * **Кучка из двух камней.** Если взять два камня с массами $x$ и $y$, где $y > x$. Тогда $y = x$. Это невозможно, так как массы камней различны. Поэтому кучка не может состоять из двух камней. * **Кучка из трёх камней.** Пусть массы $x, y, z$, где $z$ — самый тяжёлый. Тогда $z = x + y$. Например, $1 + 2 = 3$. Кучка $(1, 2, 3)$. Общая масса $1+2+3=6$ грамм. Самый тяжёлый камень $3$ грамма. Попробуем найти, какие массы камней подходят под это условие. Если в кучке камни $m_1 < m_2 < ... < m_k$, то $m_k = m_1 + m_2 + ... + m_{k-1}$. Сумма всех камней в кучке будет $2m_k$. Рассмотрим случай, когда количество кучек равно 1. Тогда самый тяжелый камень — 27 г. Сумма всех остальных камней $378 - 27 = 351$ г. Но $27 \neq 351$. Значит, одна кучка не подходит. Можно собрать, например, такие кучки: 1. Камни $(1, 2, 3)$. Сумма $1+2+3 = 6$. $3 = 1+2$. 2. Камни $(4, 5, 9)$. Сумма $4+5+9=18$. $9 = 4+5$. 3. Камни $(6, 7, 13)$. Сумма $6+7+13=26$. $13 = 6+7$. 4. Камни $(8, 10, 18)$. Сумма $8+10+18=36$. $18 = 8+10$. 5. Камни $(11, 12, 23)$. Сумма $11+12+23=46$. $23 = 11+12$. 6. Камни $(14, 15, 29)$ - здесь камень 29г. нам не подходит. Попробуем сформировать кучки так, чтобы они использовали все камни от 1 до 27. Возьмем, например, такую комбинацию кучек: * **Кучка 1:** Камни $1, 2, 3$. ($3 = 1+2$) Общая масса $6$. * **Кучка 2:** Камни $4, 5, 9$. ($9 = 4+5$) Общая масса $18$. * **Кучка 3:** Камни $6, 7, 13$. ($13 = 6+7$) Общая масса $26$. * **Кучка 4:** Камни $8, 10, 18$. ($18 = 8+10$) Общая масса $36$. * **Кучка 5:** Камни $11, 12, 23$. ($23 = 11+12$) Общая масса $46$. * **Кучка 6:** Камни $14, 16, 20, 26, 76$ - это слишком большая масса и не соответствует оставшимся камням. Допустим, у нас есть $k$ кучек. Каждый камень используется ровно один раз. Массы камней от 1 до 27. Рассмотрим самый большой камень, который может быть самым тяжелым в кучке. Пусть это $m$. Тогда сумма всех остальных камней в этой кучке должна быть $m$. Отсюда следует, что $m$ должно быть больше любого другого камня в этой кучке. Если у нас есть кучка $(a, b, c)$ где $c = a+b$. Предположим, количество кучек $K$. Общая масса всех камней $S = 378$. Пусть $M_i$ - сумма масс камней в $i$-ой кучке. $M_i = 2m_{i,max}$, где $m_{i,max}$ - самый тяжелый камень в $i$-ой кучке. Заметим, что самый большой камень 27 может быть самым тяжелым в кучке. Тогда сумма остальных камней должна быть 27. Мы можем взять камни $1, 2, ..., 27$. Например, кучка $(1, 2, 3)$. Остались камни $4, 5, ..., 27$. Сумма оставшихся $378 - 6 = 372$. Рассмотрим самый большой камень 27. Может ли он быть самым тяжёлым в кучке? Да, если мы найдем набор других камней, сумма которых равна 27. Например: $1+2+3+4+5+6+7+8+9+10$ - это уже 55, слишком много. Может быть $1+2+... + x = 27$. $x(x+1)/2 = 27 ightarrow x(x+1) = 54$. Это не имеет целых решений. Но можно подобрать так: $1+2+3+4+5+6 = 21$. Если добавить $x$, то $21+x=27 ightarrow x=6$. Но камни не могут повторяться. Можно использовать набор: $1+2+3+4+5+12 = 27$. (Камни $1,2,3,4,5,12,27$). Эта кучка содержит 7 камней. Сумма $1+2+3+4+5+12+27 = 54$. Самый тяжёлый камень $27 = 1+2+3+4+5+12$. Такая кучка возможна. Сколько кучек могло получиться? Попробуем разложить все 27 камней. Вот один из возможных вариантов разбиения на кучки: 1. Кучка $(1, 2, 3)$. (сумма $6$, $3 = 1+2$) 2. Кучка $(4, 5, 9)$. (сумма $18$, $9 = 4+5$) 3. Кучка $(6, 7, 13)$. (сумма $26$, $13 = 6+7$) 4. Кучка $(8, 10, 18)$. (сумма $36$, $18 = 8+10$) 5. Кучка $(11, 12, 23)$. (сумма $46$, $23 = 11+12$) 6. Кучка $(14, 15, 27)$ - здесь $27 \neq 14+15=29$. Не подходит. Нужно по-другому. Попробуем такой подход. Мы знаем, что каждый камень может быть использован только один раз. Сумма всех камней $378$. Каждая кучка имеет четную сумму $2m_{max}$. Рассмотрим максимальное количество кучек. Если все кучки состоят из 3 камней. $n$ кучек * 3 камня = 27 камней. $n = 9$ кучек. Попробуем найти 9 таких троек: 1. $(1, 2, 3)$ $3=1+2$ 2. $(4, 5, 9)$ $9=4+5$ 3. $(6, 7, 13)$ $13=6+7$ 4. $(8, 10, 18)$ $18=8+10$ 5. $(11, 12, 23)$ $23=11+12$ 6. $(14, 16, 20)$ - нет, 20 не 14+16 Тогда нужно искать другие комбинации. Если у нас $K$ кучек. Каждый камень $m_i$ должен принадлежать ровно одной кучке. Пусть самая большая масса в кучке $C_j$ будет $M_j$. Тогда сумма всех масс в $C_j$ будет $2M_j$. Рассмотрим камни в порядке убывания. Самый большой камень 27. Ему нужна сумма 27 из меньших камней. Например, $27 = 1+2+3+4+5+12$. Это одна кучка. Остались камни: $6,7,8,9,10,11,13,14,15,16,17,18,19,20,21,22,23,24,25,26$. (20 камней) Самый большой оставшийся камень 26. Ему нужна сумма 26. Например: $26 = 6+7+8+5$. Нет, 5 уже нет. $26 = 6+7+13$. Итак, кучки: 1. $(1, 2, 3, 4, 5, 12, 27)$. (7 камней) 2. $(6, 7, 13)$. (3 камня) Остались камни: $8, 9, 10, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26$. (17 камней) Следующий самый большой 26. Но он уже в кучке. Следующий 25. Ему нужна сумма 25. Например: $25 = 8+9+?$. $25 = 8+17$. Итак, кучки: 1. $(1, 2, 3, 4, 5, 12, 27)$. 2. $(6, 7, 13)$. 3. $(8, 17, 25)$. (3 камня) Остались камни: $9, 10, 11, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 26$. (14 камней) Следующий самый большой 26. Ему нужна сумма 26. $26 = 9+?$ нет. $26 = 10+16$. Итак, кучки: 1. $(1, 2, 3, 4, 5, 12, 27)$. 2. $(6, 7, 13)$. 3. $(8, 17, 25)$. 4. $(10, 16, 26)$. (3 камня) Остались камни: $9, 11, 14, 15, 18, 19, 20, 21, 22, 23, 24$. (11 камней) Следующий самый большой 24. Ему нужна сумма 24. $24 = 9+15$. Итак, кучки: 1. $(1, 2, 3, 4, 5, 12, 27)$. 2. $(6, 7, 13)$. 3. $(8, 17, 25)$. 4. $(10, 16, 26)$. 5. $(9, 15, 24)$. (3 камня) Остались камни: $11, 14, 18, 19, 20, 21, 22, 23$. (8 камней) Следующий самый большой 23. Ему нужна сумма 23. $23 = 11+12$. Но 12 уже нет. Значит, этот способ подбора не подходит. Надо искать более систематически. Каждая кучка должна иметь сумму $2x$, где $x$ — самый тяжелый камень в кучке. Рассмотрим камни, которые могут быть самыми тяжелыми: * Если самый тяжелый камень — $m$. Сумма остальных камней в кучке должна быть $m$. * Если кучка из 3 камней $(a, b, a+b)$. Может быть 3 кучки. Например: 1. Кучка 1: $(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)$. Не подходит. Давай попробуем рассуждать про количество кучек. Минимальное количество камней в кучке — 3 (как показано выше $x, y, x+y$). Максимальное количество кучек — 9 (27 камней / 3 камня на кучку). Рассмотрим пример, когда все камни разбиваются на 9 кучек по 3 камня. 1. $(1, 2, 3)$ 2. $(4, 5, 9)$ 3. $(6, 8, 14)$ 4. $(7, 10, 17)$ 5. $(11, 12, 23)$ 6. $(13, 15, 28)$ - 28 нет. Так что 9 кучек по 3 камня невозможно. Попробуем разложить камни так, чтобы использовать как можно меньше кучек. Если у нас 2 кучки. Пусть $K_1$ и $K_2$ - две кучки. В $K_1$ самый тяжелый камень $M_1$. Сумма камней в $K_1$ равна $2M_1$. В $K_2$ самый тяжелый камень $M_2$. Сумма камней в $K_2$ равна $2M_2$. Общая сумма $2M_1 + 2M_2 = 378 ightarrow M_1 + M_2 = 189$. Предположим, $M_1=27$. Тогда $M_2 = 189 - 27 = 162$. Кучка 1: самый тяжелый камень 27. Сумма остальных камней должна быть 27. Например, $(1, 2, 3, 4, 5, 12, 27)$. Камни, которые взяли: $1,2,3,4,5,12,27$. Остались камни: $6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26$. Самый тяжелый камень в этой кучке должен быть $M_2 = 162$. Но самый большой оставшийся камень 26. Это невозможно. Значит 2 кучки не получится. Волшебница Стела справилась с заданием, значит, решение существует. Если она разложила камни на 3 кучки. $M_1 + M_2 + M_3 = 378/2 = 189$. Пример возможного разбиения на 3 кучки (это один из возможных вариантов, но не единственный): **Кучка 1:** Самый тяжелый камень: $27$. Остальные камни, дающие в сумме $27$: $1+2+3+4+5+12 = 27$. (Камни $1,2,3,4,5,12,27$). Сумма $54$. **Кучка 2:** Самый тяжелый камень: $26$. Остальные камни (из оставшихся): $6,7,8,9,10,11,13,14,15,16,17,18,19,20,21,22,23,24,25$. $6+7+13 = 26$. (Камни $6,7,13,26$). Сумма $52$. **Кучка 3:** Оставшиеся камни: $8,9,10,11,14,15,16,17,18,19,20,21,22,23,24,25$. Сумма этих камней: $8+9+10+11+14+15+16+17+18+19+20+21+22+23+24+25 = 282$. Если эта кучка содержит самый тяжелый камень $M_3$, то сумма всех камней в ней должна быть $2M_3$. Этот способ тоже не дает 3 кучки легко. Подумаем о свойствах этих кучек. Если в кучке есть камень $m$, который является самым тяжелым, то $m$ должно быть равно сумме остальных камней в этой кучке. Значит, $m$ не может быть очень маленьким. Давай попробуем с 4 кучками. $M_1+M_2+M_3+M_4 = 189$. Это известная задача. Ответ на неё - 3 кучки. Один из способов разбиения на 3 кучки: * **Кучка 1:** $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 27$ (Здесь $27 = 1+2+...+12+27$ - это неверно, $1+2+...+12 = 78$. То есть $27 \neq 78$. Эта кучка не подходит). Правильный подход к поиску решения: Предположим, количество кучек $K$. Общая сумма всех камней $S = 378$. Каждая кучка имеет общую массу $2m_{max}$, где $m_{max}$ - самый тяжелый камень в кучке. Рассмотрим максимально возможную массу $m_{max}$ для одной кучки. Она может быть 27. Тогда сумма остальных камней в этой кучке должна быть 27. Пример такой кучки: $(1, 2, 3, 4, 5, 12, 27)$. Это 7 камней. Остались 20 камней. Сумма их $378 - (27 \times 2) = 378 - 54 = 324$. Следующий по убыванию максимальный камень — 26. Сумма оставшихся камней в этой кучке должна быть 26. Например: $(6, 7, 13, 26)$. (Это 4 камня). Остались 16 камней. Сумма их $324 - (26 \times 2) = 324 - 52 = 272$. Следующий по убыванию максимальный камень — 25. Сумма остальных должна быть 25. Например: $(8, 9, 10, 25)$. (Это 4 камня). Нет, $8+9+10=27 \neq 25$. Не подходит. Надо $8+17=25$. Кучка $(8, 17, 25)$. (3 камня). Остались 13 камней. Сумма их $272 - (25 \times 2) = 272 - 50 = 222$. Следующий по убыванию максимальный камень — 24. Сумма остальных должна быть 24. Например: $(11, 13, 24)$. ($11+13=24$). (3 камня). Остались 10 камней. Сумма их $222 - (24 \times 2) = 222 - 48 = 174$. Следующий по убыванию максимальный камень — 23. Сумма остальных должна быть 23. Например: $(14, 15, 23)$ - $14+15=29 \neq 23$. Не подходит. $(10, 13, 23)$ - 10 и 13 уже нет. Так, этот подход