Question

В 100 пакетах 2018 конфет, в каждом разное количество, пустых нет, причем в пакете могут лежать ещё пакеты , тогда конфеты внутреннего пакета считаются также лежащими во внешнем. Докажите, что есть пакет с пакетом внутри

Answer 1

Докажем от обратного. Пусть нет пакета с пакетом внутри, но при этом конфеты разложены по пакетам так, что их сумма минимальна (в каждом пакете разное количество, пустых нет). Тогда минимальное количество конфет в пакете равно 1 (так как пустых пакетов нет) и найдется ровно один пакет, содержащий k конфет, где k принимает все натуральные значения от 1 до 100. При этом сумма конфет во всех пакетах будет равна

$\frac{1+100}{2} * 100=5050.$

Так как минимальное количество конфет при условии, что нет пакета с пакетом внутри равно 5050, а по условию в 100 пакетах 2018 конфет, то обязательно найдется пакет с пакетом внутри.

Answer 2

Для доказательства данного утверждения воспользуемся методом математической индукции.

Пусть у нас есть некоторое количество пакетов, обозначим его как n. Предположим, что утверждение верно для n пакетов, то есть в каждом из этих пакетов содержится ещё пакет.

Теперь рассмотрим случай n+1 пакета. По предположению индукции, в каждом из первых n пакетов содержится ещё пакет. Рассмотрим последний (n+1)-й пакет. В нем может быть два случая:

1) В последнем пакете находится только конфеты, но не содержится других пакетов. В этом случае утверждение остается верным, так как мы не говорим, что каждый пакет содержит обязательно другой пакет.

2) В последнем пакете также содержится ещё пакет. Это означает, что внутри последнего пакета находится как минимум один пакет, а значит, утверждение остается верным и для n+1 пакета.

Таким образом, мы показали, что если утверждение верно для некоторого количества пакетов n, то оно верно и для n+1 пакета. Исходя из принципа математической индукции, это означает, что утверждение верно для любого количества пакетов.

Таким образом, можно сделать вывод, что среди 100 пакетов конфет, в каждом из которых содержится разное количество конфет и нет пустых пакетов, обязательно есть пакет, внутри которого находится ещё один пакет.