Задача 6. Лодка для компаний

Сколько всего переправ

Каждый из пятерых либо входит в компанию, либо нет — это $2^5=32$ варианта. Один из них — «никто», а пустая лодка не плавает. Значит, компаний $32-1=31$, и лодка должна пересечь реку $31$ раз.

Где окажется лодка

Лодка ходит туда и обратно: после нечётного числа переправ она на другом берегу. $31$ — нечётное, значит, последняя переправа привезёт компанию на другой берег, и хотя бы один друг (пусть Вася) закончит катание там.

Сколько раз плавает Вася

Вася входит в те компании, где он есть: каждый из остальных четырёх либо с ним, либо нет — $2^4=16$ компаний. Значит, Вася переправляется ровно $16$ раз. Число чётное: после каждых двух переправ он снова на исходном берегу, и в конце он тоже там.

Противоречие

Получилось, что Вася в конце и на другом берегу (шаг 2), и на исходном (шаг 3). Так не бывает. Значит, покататься так, чтобы каждая компания переправилась ровно один раз, не получится.

Заметь: рассуждение работает для любого числа друзей от двух: компаний $2^n-1$ — нечётное число, а с каждым другом — $2^{n-1}$, чётное.