До­ста­точ­ность та­ко­го ко­ли­че­ства ту­зем­цев до­ка­зы­ва­ет­ся по ин­дук­ции. Дей­стви­тель­но, для до­ста­точ­но двух ту­зем­цев, ко­то­рые пе­ре­прав­ля­ют­ся вме­сте на дру­гой берег. Если для до­ста­точ­но 2^m ту­зем­цев, то для сна­ча­ла (в со­от­вет­ствии с пред­по­ло­же­ни­ем ин­дук­ции) могут пе­ре­пра­вить­ся на пра­вый берег 2^m ту­зем­цев, каж­дый из ко­то­рых узна­ет при этом не менее m анек­до­тов, а затем каж­дый из них по­оче­ред­но пе­ре­плы­ва­ет по од­но­му разу на левый берег и пе­ре­во­зит от­ту­да од­но­го из остав­ших­ся там ту­зем­цев, узнав по до­ро­ге его анек­дот и рас­ска­зав ему не менее анек­до­та, из­вест­но­го ему на тот мо­мент. В ре­зуль­та­те каж­дый из ту­зем­цев узна­ет не менее новых анек­до­тов.

Оста­ет­ся по­ка­зать, что мень­ше­го числа ту­зем­цев не­до­ста­точ­но.

Спо­соб I. Об­лег­чим за­да­чу: пусть N ту­зем­цев не пе­ре­прав­ля­ют­ся через реку, а про­сто со­вер­ша­ют не более про­гул­ки вдво­ем по озеру с воз­вра­ще­ни­ем в ком­па­нию. До­ка­жем, что даже в этой за­да­че

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

До­ка­жем те­перь при по­мо­щи ин­дук­ции по k, что База оче­вид­на. Для до­ка­за­тель­ства шага вы­ки­нем из графа ребро, со­от­вет­ству­ю­щее пер­во­му рейсу. Граф рас­па­дет­ся на 2 ком­по­нен­ты связ­но­сти. В каж­дой знают не более од­но­го анек­до­та из дру­гой ком­по­нен­ты. Зна­чит, каж­дый знает не менее k анек­до­тов из своей ком­по­нен­ты (счи­тая свой). По пред­по­ло­же­нию ин­дук­ции, в каж­дой из ком­по­нент не менее ту­зем­цев, а всего  — не менее 2^k.

Спо­соб II. На­зо­вем ин­дек­сом ту­зем­ца число из­вест­ных ему анек­до­тов сверх сво­е­го. Ту­зем­цев с не­ну­ле­вым ин­дек­сом на­зо­вем бо­га­ты­ми, осталь­ных  — бед­ны­ми, а ка­пи­та­лом ту­зем­ца с ин­дек­сом z на­зо­вем число 2^−m (здесь сле­ду­ет от­ме­тить, что так опре­де­лен­ный ка­пи­тал умень­ша­ет­ся с ро­стом ко­ли­че­ства анек­до­тов, из­вест­ных ту­зем­цу).

Для мо­мен­тов вре­ме­ни, в ко­то­рые лодка на­хо­дит­ся на пра­вом бе­ре­гу, вы­чис­лим число S как сумму ка­пи­та­лов всех бо­га­тых ту­зем­цев (не­за­ви­си­мо от того, на каком бе­ре­гу они на­хо­дят­ся) минус ко­ли­че­ство L бо­га­тых ту­зем­цев на левом бе­ре­гу. При пер­вом по­яв­ле­нии лодки на пра­вом бе­ре­гу До­ка­жем, что S по мере пе­ре­пра­вы не умень­ша­ет­ся. Между по­сле­до­ва­тель­ны­ми по­па­да­ни­я­ми лодки на пра­вый берег воз­мож­ны 3 вида слу­ча­ев: ко­ли­че­ство бо­га­тых ту­зем­цев в лодке на пути с ле­во­го бе­ре­га на пра­вый ока­за­лось рав­ным 0, 1 или 2.

В слу­чае нуля бо­га­тых ту­зем­цев в лодке двое бед­ных по до­ро­ге на пра­вый берег стали бо­га­ты­ми и уве­ли­чи­ли S на Но на левый берег лодку пе­ре­го­нял бо­га­тый ту­зе­мец, ко­то­рый на левом бе­ре­гу и остал­ся, уве­ли­чив L на 1. Зна­чит, в этом слу­чае S не из­ме­ни­лась.

Рас­смот­рим слу­чай од­но­го бо­га­то­го ту­зем­ца в лодке. Число L в этом слу­чае не из­ме­ни­лось. Сев­ший в лодку бо­га­тый знал (по­ми­мо сво­е­го) m анек­до­тов, его ка­пи­тал был равен 2^−m. Те­перь он и его спут­ник знают (по­ми­мо своих) по анек­до­ту, и сумма их ка­пи­та­лов равна то есть вновь S не из­ме­ни­лась.

На­ко­нец, в слу­чае двух бо­га­тых ту­зем­цев в лодке число L умень­ша­ет­ся на 1, а сумма ка­пи­та­лов при­плыв­ших на пра­вый берег бо­га­тых ту­зем­цев умень­ша­ет­ся, но, бу­дучи из­на­чаль­но не более она умень­ша­ет­ся менее чем на 1. Тем самым, в итоге S уве­ли­чи­лась.

Итак, в конце а ка­пи­тал каж­до­го ту­зем­ца не более 2^–k. Зна­чит, ту­зем­цев не менее 2^k.

Ответ: 2^k.