Задача 66549
|
|
 |
Условие
Пять друзей подошли к реке и обнаружили на берегу лодку, в которой могут поместиться все пятеро. Они решили покататься на лодке. Каждый раз с одного берега на другой переправляется компания из одного или нескольких человек. Друзья хотят организовать катание так, чтобы каждая возможная компания переправилась ровно один раз. Получится ли у них это сделать?Решение
Предположим, что друзьям удастся осуществить желаемое. Давайте посчитаем, сколько всего возможных компаний можно составить из пяти человек (и, соответственно, сколько раз переплывёт лодка с одного берега на другой). Каждый человек может либо войти, либо не войти в компанию, то есть для каждого есть два варианта, поэтому всего вариантов 25 = 32. В том числе мы посчитали вариант, когда никто не попал в компанию. Однако лодка пустая не плавает, значит, всего компаний 32 − 1 = 31. Так как это число нечётно, то друзья должны переплыть реку нечётное количество раз, поэтому в итоге лодка окажется на противоположном берегу. Следовательно, хотя бы один из друзей завершит катание на другом берегу, пусть это будет Вася.
Посмотрим, сколько раз он мог переправиться.
Каждый из его друзей может либо плыть, либо не плыть с ним,
поэтому Вася входит в 24 = 16 различных компаний
(в том числе он может плыть и один).
Но это число чётно, значит, после катания Вася должен вернуться на исходный берег.
Полученное противоречие доказывает, что покататься требуемым образом не получится.
