Докажем по индукции, что 2^k туземцев достаточно.

 База.  Для k = 1  двух туземцев, которые переправляются вместе на другой берег, достаточно.

  Шаг индукции. Пусть  k > 1.  Сначала (в соответствии с предположением индукции) переправляются на правый берег 2^k–1 туземцев, каждый из которых узнаёт при этом не менее  k – 1  анекдота, а затем каждый из них поочередно переплывает по одному разу на левый берег и перевозит оттуда одного из оставшихся там 2^k–1 туземцев, узнав по дороге его анекдот и рассказав ему не менее k анекдотов, известных ему на тот момент. В результате каждый из 2^k туземцев узнает не менее k новых анекдотов.   Остается показать, что меньшего числа туземцев недостаточно.   Первый способ. Облегчим задачу: пусть N туземцев не переправляются через реку, а просто совершают не более  N – 1  прогулки вдвоем по озеру с возвращением в компанию. Докажем, что даже в этой задаче  N ≥ 2^k.

  Построим граф: вершины – туземцы, ребро соединяет плывших вместе. В этом графе N вершин и  N – 1  ребро (если некоторые пары катались вместе более одного раза, то в этом графе есть кратные рёбра). Если N для данного k выбрано минимальным, то этот граф связен. Действительно, в противном случае рассмотрим компоненту связности, в которой рёбер меньше, чем вершин (при этом их меньше максимум на 1 в силу связности), и выполним только рейсы из этой компоненты. Раз этот граф связен и имеет  N – 1  ребро, он является деревом (в частности, не имеет кратных рёбер).

  Докажем теперь по индукции, что  N ≥ 2^k. База очевидна.

  Шаг индукции. Выкинем из графа ребро, соответствующее первому рейсу. Граф распадется на две компоненты связности. В каждой знают не более одного анекдота из другой компоненты. Значит, каждый знает не менее k анекдотов из своей компоненты (считая свой). По предположению индукции, в каждой из компонент не менее 2^k–1 туземцев, а всего – не менее 2^k.   Второй способ. Назовём индексом туземца число известных ему анекдотов сверх своего. Туземцев с ненулевым индексом назовем богатыми, остальных – бедными, а капиталом туземца с индексом 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. Значит, туземцев не менее 2^k.

N = 2^k.