№ 8673

С левого берега реки на правый с помощью одной лодки переправились $N$ туземцев, каждый раз плавая направо вдвоем, а обратно — в одиночку. Изначально каждый знал по одному анекдоту, каждый — свой. На берегах они анекдотов не рассказывали, но в лодке каждый рассказывал попутчику все известные ему на данный момент анекдоты. Для каждого натурального $k$ найдите наименьшее возможное значение $N$, при котором могло случиться так, что в конце каждый туземец знал, кроме своего, ещё не менее чем $k$ анекдотов.