Maths Olympiad Prep

Library / /23 of 25

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Russia

100 dwarves whose weights are 11, 22, \ldots, 100100 lb came to the left bank of a river. They cannot swim, but they have a boat which can take up to 100100 lb. When a boat crosses the river, one of the dwarves in it is an oarsman; while performing one crossing, the oarsman remains the same. Due to the stream, it is difficult to oar from the right bank to the left one, so each dwarf can oar in this direction at most once. Can the whole company of dwarves reach the right bank?

Solution

Answer. No.
Call the dwarves weighing at least 5050 lb heavy; assume they oared backwards dd times. Then there were at least 51+d51 + d their forward passages, and hence at least 5050 backward passages with no heavy dwarves oaring. But who could oar during these 5050 passages?

Первое решение. Предположим, что переправа гномам удалась. Назовём рейсы лодки с левого берега на правый прямым, а с правого на левый – обратными. Пусть было kk обратных рейсов; тогда прямых рейсов было k+1k+1.
В kk обратных рейсах гребли kk разных гномов; значит, суммарный вес гномов, участвовавших в обратных рейсах, не меньше 1+2++k=k(k+1)21+2+\ldots+k = \frac{k(k+1)}{2} (здесь и далее все веса измеряются в фунтах). На любом прямом рейсе суммарный вес гномов не превосходит 100100, так что в итоге суммарный вес гномов на левом берегу уменьшился не более, чем 100(k+1)k(k+1)2=(200k)(k+1)2100(k+1) - \frac{k(k+1)}{2} = \frac{(200-k)(k+1)}{2}. С другой стороны, этот вес уменьшился на 1+2++100=10010121+2+\ldots+100 = \frac{100 \cdot 101}{2}, откуда
(200k)(k+1)100101, или (k100)(k99)0. (200-k)(k+1) \ge 100 \cdot 101, \text{ или } (k-100)(k-99) \le 0.
Это может случиться лишь если k=99k=99 или k=100k=100. При этом неравенство обращается в равенство; это значит, что в kk обратных рейсах участвовали только гномы весами 1,2,,k1, 2, \dots, k – каждый по одному разу, а на каждом прямом рейсе суммарный вес гномов был равен 100100.
Ясно, что гном весом 100100 совершал все свои рейсы (один рейс при k=99k=99 и три при k=100k=100) в одиночку; рассмотрим теперь только остальных (обычных) гномов и их рейсы (их ровно 9999 прямых и 9999 обратных в любом случае). В каждом из прямых рейсов участвовало хотя бы 22 обычных гнома; значит, общее количество обычных гномов на правом берегу увеличилось как минимум на 99299=9999 \cdot 2 - 99 = 99. Это неравенство также обращается в равенство, так что на каждом прямом рейсе участвовало ровно два гнома. Но тогда гном веса 5050 должен был плыть с гномом веса 5050, а второго такого нет. Противоречие.

Второе решение. Мы также предполагаем противное. Воспользуемся терминологией, введённой в начале предыдущего решения.
Назовём гномов с весами 50,51,52,,10050, 51, 52, \ldots, 100 тяжёлыми, в dd обратных рейсах. Тогда эти dd тяжёлых гномов совершили хотя бы по два прямых рейса, а остальные — хотя бы по одному. Поскольку два тяжёлых гнома не могли плыть одновременно, =51+d= 51+d. Значит, обратных рейсов было не меньше, чем 2d+(51d)=2d + (51 - d) = есть хотя бы в 5050 из них гребцами были лёгкие гномы. Но лёгких гномов всего 4949, так что один из них должен был дважды грести в обратном рейсе, что невозможно.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.