Question

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

Answer 1

Рассмотрим все возможные непустые наборы, состоящие из каких-то из 10 выбранных чисел. Таких наборов 1023: каждое число можно независимо взять или не взять в набор, это даст $2^{10}=1024$ вариантов, и 1 вариант, когда набор пустой, нужно исключить.

Выпишем сумму чисел каждого из таких наборов. Максимальное возможное выписанное значение $91+92+\cdots+100=955$, так что различных возможных сумм не больше 955. Поскольку мы выписали 1023 суммы, значит, какие-то два набора имеют одинаковую сумму.

Из каждого из найденных наборов исключим числа, входящие в оба набора (если такие числа есть, конечно). Суммы чисел останутся равными, поскольку обе суммы уменьшились на одно и то же число; получившиеся наборы будут непусты (ни один набор не может полностью входить в другой, иначе их суммы были бы не равны).

Итак, мы получили, что нашлись два набора, содержащие разные числа, имеющие одинаковые суммы. Ура!

Answer 2

Для доказательства данного утверждения, воспользуемся принципом Дирихле (или принципом ящиков Дирихле). Этот принцип утверждает, что если разместить n+1 объектов в n ящиках, то в каком-то из ящиков окажется не менее двух объектов.

В нашем случае, у нас есть 10 чисел, выбранных из натуральных чисел от 1 до 100. Давайте рассмотрим сумму этих чисел и поделим каждое из них на 100 (целую часть от деления). Таким образом, каждое число будет принадлежать одной из 100 "ящиков" (числа 0 до 99 включительно). Всего у нас есть 10 чисел и 100 "ящиков", значит, по принципу Дирихле, как минимум одна из "корзин" будет содержать не менее двух чисел.

Пусть одна из "корзин" содержит числа a и b (где a ≠ b) из нашего набора чисел. Это означает, что существует другой набор, в котором числа a и b также содержатся, но в другой "корзине". Таким образом, мы можем составить два набора чисел с одинаковой суммой, где числа a и b находятся в разных наборах.

Итак, доказано, что можно составить два набора из выбранных 10 натуральных чисел с одинаковой суммой.