100 dwarves whose weights are , , , lb came to the left bank of a river. They cannot swim, but they have a boat which can take up to 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 lb heavy; assume they oared backwards times. Then there were at least their forward passages, and hence at least backward passages with no heavy dwarves oaring. But who could oar during these passages?
Первое решение. Предположим, что переправа гномам удалась. Назовём рейсы лодки с левого берега на правый прямым, а с правого на левый – обратными. Пусть было обратных рейсов; тогда прямых рейсов было .
В обратных рейсах гребли разных гномов; значит, суммарный вес гномов, участвовавших в обратных рейсах, не меньше (здесь и далее все веса измеряются в фунтах). На любом прямом рейсе суммарный вес гномов не превосходит , так что в итоге суммарный вес гномов на левом берегу уменьшился не более, чем . С другой стороны, этот вес уменьшился на , откуда
Это может случиться лишь если или . При этом неравенство обращается в равенство; это значит, что в обратных рейсах участвовали только гномы весами – каждый по одному разу, а на каждом прямом рейсе суммарный вес гномов был равен .
Ясно, что гном весом совершал все свои рейсы (один рейс при и три при ) в одиночку; рассмотрим теперь только остальных (обычных) гномов и их рейсы (их ровно прямых и обратных в любом случае). В каждом из прямых рейсов участвовало хотя бы обычных гнома; значит, общее количество обычных гномов на правом берегу увеличилось как минимум на . Это неравенство также обращается в равенство, так что на каждом прямом рейсе участвовало ровно два гнома. Но тогда гном веса должен был плыть с гномом веса , а второго такого нет. Противоречие.
Второе решение. Мы также предполагаем противное. Воспользуемся терминологией, введённой в начале предыдущего решения.
Назовём гномов с весами тяжёлыми, в обратных рейсах. Тогда эти тяжёлых гномов совершили хотя бы по два прямых рейса, а остальные — хотя бы по одному. Поскольку два тяжёлых гнома не могли плыть одновременно, . Значит, обратных рейсов было не меньше, чем есть хотя бы в из них гребцами были лёгкие гномы. Но лёгких гномов всего , так что один из них должен был дважды грести в обратном рейсе, что невозможно.