Есть такая старая-престарая задача из числа задач о переправе. Классическим примером задачи о переправе является "волк, коза и капуста". А эта похитрее и есть полезные нюансы, поэтому давайте ее обсудим.
Иногда ее формулируют в терминах рыцарей и оруженосцев, но мы перепишем иначе. А именно, к берегу реки подходят три пары, при этом все согласны, что девушка не может остаться на берегу без своего спутника в обществе других мужчин, даже ненадолго. Есть лодка, в которой помещается не более двух человек. Как всем переправиться, если это возможно, и возможно ли это?
А если пар четыре, тогда как?
Под рисунком решение. Попробуйте решить ее сами.
Итак, сначала в лодке плывут две девушки. Одна остается на берегу, другая отгоняет лодку обратно и забирает третью подругу. Далее, одна из девушек плывет к своему кавалеру. И остается с ним, пока двое других плывут к своим спутницам. Одна пара плывет обратно. Девушка выходит на берег, а мужчина садится в лодку. Теперь на другом берегу все три мужчины и одна девушка (а на другом две девушки). Она плывет и забирает подругу. Наконец, спутник последней девушки плывет и забирает ее. Как вариант, за последней девушкой может сгонять девушка.
Всего 11 рейсов. При этом для неревнивых пар рейсов всего 9: пара рейсов переправляет одного человека, возвращая лодку на исходную позицию. Далее легко ошибиться, умножив шесть на два: число рейсов непременно нечетное. За четыре пары рейсов (восемь переправ) будет переправлено четыре человека, а девятым рейсом переправятся оставшиеся двое.
То есть ревность стоила двух лишних переправ.
А вот если пар четыре, то решения нет. Но это надо доказать.
Можно, конечно, перебрать все варианты переправы и установить, что ни один не подходит. Но есть способ проще. Он основан на таком простом принципе: если задано непустое множество натуральных чисел, то в нем есть наименьшее число.
Так или иначе, но должно быть выполнено несколько рейсов, и каждый рейс может менять число мужчин на другом берегу. И есть множество тех рейсов, после которых число мужчин на другом берегу больше двух. Это множество непусто, потому что после последнего рейса точно больше двух на другом берегу, просто потому, что там все. И в этом множестве есть наименьшее число k. И ясно, что k>2, потому что второй рейс разве что уменьшит число мужчин на втором берегу, а первым рейсом туда больше двух не переправить.
Итак, пусть k номер первого рейса, после которого на втором берегу станет более двух мужчин. Тогда после рейса k-1 там был либо один, либо двое, потому что три и четыре противоречат тому, что это рейс k первый, после которого больше двух мужчин на том берегу, а никого там быть не может тоже, так как сразу трое приплыть не могут.
Предположим, что после рейса k-2 на том берегу один мужчина. Тогда его девушка с ним: оставить ее на первом берегу он не может, ведь там другие мужчины. Но и других девушек на втором берегу нет, ведь там он. То есть на втором берегу ровно одна парочка.
И обратно плыть некому! Девушку отпустить нельзя (там другие мужчины), а самому плыть невозможно, так как иначе после рейса k не получится больше двоих.
Итак, после рейса k-1 на втором берегу ровно двое мужчин, и то если получится. Соответственно, с ними их девушки, и больше никого. Две пары на одном берегу, две на другом.
И обратно плыть некому! Почти. Девушек отпускать нельзя, ни вдвоем, ни по одной. Плыть одному нельзя, так как твоя дама останется с чужим мужиком. Плыть вдвоем нельзя, так как тогда не получится больше двух мужчин после рейса k.
Вроде бы может уплыть пара. Тогда после рейса k-1 у нас три пары на первом берегу и одна на втором. По условию, на втором берегу после очередного рейса должно стать более двух мужчин, то есть три. Значит, должны уплыть двое мужчин. Но третий останется, а значит, девушек оставлять нельзя. И этот вариант отпадает.
Как видим, для трех пар "спасает" ситуацию именно то, что рейсом k=7 могут уплыть двое мужчин, оставив своих девушек вдвоем. И сразу понятно, что задача для более, чем трех пар решения не имеет.
Разумеется, есть множество вариантов, которые интересно не только решать, но и придумывать. Например, можно ли переправиться четырём парам на трехместной лодке? Если можно, то как, и сколько пар максимум можно так переправить? Или можно ли переправить четыре пары на двухместной лодочке, если на реке есть остров, на котором можно временно оставлять людей? И опять, сколько пар позволит переправить наличие острова?