|
|
 |
Условие
С левого берега реки на правый с помощью одной лодки переправились N туземцев, каждый раз плавая направо вдвоем, а обратно – в одиночку. Изначально каждый знал по одному анекдоту, каждый – свой. На берегах они анекдотов не рассказывали, но в лодке каждый рассказывал попутчику все известные ему на данный момент анекдоты. Для каждого натурального k найдите наименьшее возможное значение N, при котором могло случиться так, что в конце каждый туземец знал, кроме своего, еще не менее чем k анекдотов.
Решение
Докажем по индукции, что 2k туземцев достаточно.
База. Для k = 1 двух туземцев,
которые переправляются вместе на другой берег, достаточно.
Шаг индукции. Пусть k > 1. Сначала (в соответствии с предположением индукции) переправляются на правый берег 2k–1 туземцев, каждый из которых узнаёт при этом
не менее k – 1 анекдота, а затем каждый из них поочередно переплывает по одному разу на левый берег и перевозит оттуда одного из оставшихся там 2k–1 туземцев, узнав по дороге его анекдот и рассказав ему не менее k анекдотов, известных ему на тот момент. В результате каждый из 2k туземцев узнает не менее k новых анекдотов.
Остается показать, что меньшего числа туземцев недостаточно.
Первый способ. Облегчим задачу: пусть N туземцев не переправляются через реку, а просто совершают не более N – 1 прогулки вдвоем по озеру с возвращением в компанию. Докажем, что даже в этой задаче N ≥ 2k.
Построим граф: вершины – туземцы, ребро соединяет плывших вместе. В этом графе N вершин и N – 1 ребро (если некоторые пары катались вместе более одного раза, то в этом графе есть кратные рёбра). Если N для данного k выбрано минимальным, то этот граф связен. Действительно, в противном случае рассмотрим компоненту связности, в которой рёбер меньше, чем вершин (при этом их меньше максимум на 1 в силу связности), и выполним только рейсы из этой компоненты. Раз этот граф связен и имеет N – 1 ребро, он является деревом (в частности, не имеет кратных рёбер).
Докажем теперь по индукции, что N ≥ 2k. База очевидна.
Шаг индукции. Выкинем из графа ребро, соответствующее первому рейсу. Граф распадется на две компоненты связности. В каждой знают не более одного анекдота из другой компоненты. Значит, каждый знает не менее k анекдотов из своей компоненты (считая свой). По предположению индукции, в каждой из компонент не менее 2k–1 туземцев, а всего – не менее 2k.
Второй способ. Назовём индексом туземца число известных ему анекдотов сверх своего. Туземцев с ненулевым индексом назовем богатыми, остальных – бедными, а капиталом туземца с индексом m назовем число 2–m (отметим, что капитал уменьшается с ростом количества анекдотов, известных туземцу).
Для моментов времени, в которые лодка находится на правом берегу, вычислим число S как сумму капиталов всех богатых туземцев (независимо от того, на каком берегу они находятся) минус количество L богатых туземцев на левом берегу. При первом появлении лодки на правом берегу
S = 2–1 + 2–1 – 0 = 1. Докажем, что S по мере переправы не уменьшается. Между последовательными попаданиями лодки на правый берег возможны три вида случаев: количество богатых туземцев в лодке на пути с левого берега на правый оказалось равным 0, 1 или 2.
В первом случае двое бедных по дороге на правый берег стали богатыми и увеличили S на 2–1 + 2–1 = 1. Но на левый берег лодку перегонял богатый туземец, который на левом берегу и остался, увеличив L на 1. Значит, в этом случае S не изменилась.
Во втором случае число L не меняется. Севший в лодку богатый знал (помимо своего) m анекдотов, его капитал был равен 2–m. Теперь он и его спутник знают (помимо своих) по m + 1 анекдоту, и сумма их капиталов равна 2–m–1 + 2–m–1 = 2–m, то есть вновь S не изменилась.
Наконец, в случае двух богатых туземцев в лодке число L уменьшается на 1, а сумма капиталов приплывших на правый берег богатых туземцев уменьшается, но, будучи изначально не более 2–1 + 2–1 = 1, она уменьшается менее чем на 1. Тем самым, в итоге S увеличилась.
Итак, в конце S ≥ 1, L = 0, а капитал каждого туземца не более 2–k. Значит, туземцев не менее 2k.
Ответ
N = 2k.
