|
|
 |
Условие
Сто гномов, веса которых равны 1, 2, 3, ..., 100 фунтов, собрались на левом берегу реки. Плавать они не умеют, но на этом же берегу находится гребная лодка грузоподъемностью 100 фунтов. Из-за течения плыть обратно трудно, поэтому у каждого гнома хватит сил грести с правого берега на левый не более одного раза (грести в лодке достаточно любому из гномов; гребец в течение одного рейса не меняется). Смогут ли все гномы переправиться на правый берег?
Решение
Занумеруем гномов по их весу. Предположим, что переправа гномам удалась. Назовём рейсы лодки с левого берега на правый прямыми, а с правого на левый – обратными.
Первый способ. Пусть было k обратных рейсов; тогда прямых рейсов было k + 1.
В k обратных рейсах гребли k разных гномов; значит, суммарный вес гномов, участвовавших в обратных рейсах, не меньше
1 + 2 + ... + k = ½ k(k + 1). На каждом прямом рейсе суммарный вес гномов не превосходит 100, так что в итоге суммарный вес гномов на левом берегу уменьшился не более чем на 100(k + 1) – ½ k(k + 1) = ½ (200 – k)(k + 1). С другой стороны, этот вес уменьшился на 1 + 2 + ... + 100 = 50·101, откуда (200 – k)(k + 1) ≥ 100·101, или (k – 100)(k – 99) ≤ 0.
Это может случиться лишь если k = 99 или k = 100. При этом неравенство обращается в равенство; это значит, что на каждом прямом рейсе суммарный вес гномов был равен 100. Но тогда гном веса 50 должен был плыть с гномом веса 50, а второго такого нет. Противоречие.
Второй способ. Назовём гномов 50, 51, 52, ..., 100 тяжёлыми, а остальных – лёгкими. Пусть тяжёлые гномы были гребцами в d обратных рейсах. Тогда эти d тяжёлых гномов совершили хотя бы по два прямых рейса, а остальные – хотя бы по одному. Поскольку два тяжёлых гнома не могли плыть одновременно, количество прямых рейсов было не меньше чем 2d + (51 – d) = 51 + d. Значит, обратных рейсов было не меньше чем 50 + d, то есть хотя бы в 50 из них гребцами были лёгкие гномы. Но лёгких гномов всего 49, так что один из них должен был дважды грести в обратном рейсе, что невозможно.
Ответ
Не смогут.
