Решение задачи 347

Условие:

Есть 20 гирек, каждая из которых весит целое число грамм. Известно, что если убрать произвольное число (возможно ноль) каких-то гирек, то оставшиеся нельзя разделить на две кучки с одинаковым весом. Докажите, что суммарный вес всех гирек не меньше 1 тонны.

Решение:

Рассмотрим произвольные два (возможно, пересекающиеся) подмножества гирек. Уберем все гири из пересечения и гири, не входящие в эти наборы, тогда, согласно условию, оставшиеся части будут весить по-разному. Получается, что произвольные два подмножества гирек весят по-разному. Значит и все подмножества имеют разный вес. Всего есть 2²⁰ различных подмножеств гирек. Поскольку все подмножества различной массы, то самое тяжелое из них (все гирьки) весит не меньше, чем 2²⁰ - 1 (самое легкое - пустое подмножество весит 0). 2²⁰ - 1 = (2¹⁰)² - 1 = (1024)² - 1 > (1000)² - 1 = 999999 грамм. Значит суммарный вес всех гирек не меньше тонны (10⁶ грамм).