Добрый день. Помогите решить... Каноэ

[maska11]

Девять команд на каноэ сплавлялись по реке. Каждая команда стартовала в разное время. Каноэ передвигались с постоянной скоростью, необязательно одинаковой. Иногда каноэ обгоняли друг друга. Докажите, что каждое каноэ не могло обогнать именно  четыре других каноэ.

[Artem of 93]

Назовём каноэ по номерам: 1, 2, 3, ..., 9. Так как все каноэ имеют постоянную скорость, и они стартовали в разное время, то каноэ с большей скоростью рано или поздно обгонит каноэ с меньшей, но не наоборот.

Предположим, что все каноэ имеют разные скорости: самая маленькая скорость у каноэ 1, самая большая - у каноэ 9. Очевидно, что каноэ 9 рано или поздно (учитывая, что стартовали команды в разное время) обгонит 8 других каноэ.

Предположим, что n из 9 каноэ имеют равные скорости. Тогда очевидно, что эти n каноэ обгонят одинаковое количество других каноэ, скорости которых меньше. Допустим, таких каноэ m. Но те каноэ, у которых скорости выше, чем у группы из n каноэ, обгонят как минимум m + n других каноэ. Поэтому каждое каноэ не могло обогнать одинаковое количество других каноэ.

Единственное исключение: если у всех равные скорости. Тогда каждое каноэ обгонит 0 других каноэ.

P.S. У меня получилось так. Не знаю правда, все ли условия задачи я понял правильно.

[StrannikPiter]

Да уж, условие мутное.
Очевидно, что каноэ с самой низкой скоростью не могло бы обогнать никого, что уже является доказательством искомого.

[Artem of 93]

Да уж, условие мутное.

Можно предположить ещё, что в вопросе имелось в виду, что для любого каноэ найдётся четыре каноэ, которые его обгонят. Но это тоже легко опровергнуть, поскольку из 9 каноэ будет хотя бы одно, скорость которого будет наибольшей.

[Головолом]

Четыре самых медленных каноэ однозначно не могли обогнать по четыре каноэ. А именно 4 каноэ могли обогнать 5 самых быстрых каноэ в случае, если они стартовали с пятого номера в порядке возрастания своей скорости. В этом случае они обгоняли 4 самых медленных и при этом не доганяли никого из пятёрки быстрых.

[StrannikPiter]

Написано "каноэ обгоняли друг друга". Возможно обгон при этом засчитывается обоим каноэ. То есть имелось ввиду, что каждое каноэ поравнялось (обогнало либо было обогнано) с четырьмя другими.
Тогда можно предложить такое доказательство:

Самое быстрое каноэ никто не может обогнать, значит, чтобы оно встретилось с четырьмя каноэ, оно должно было бы стартовать на пятом месте. Аналогично самое медленное каноэ должно стартовать на пятом месте с конца. Но если всего 9 каноэ, то это одно и то же место.

[Головолом]

Возможно обгон при этом засчитывается обоим каноэ. То есть имелось ввиду, что каждое каноэ поравнялось (обогнало либо было обогнано) с четырьмя другими.

В этом плане всё однозначно, если одно каноэ обгоняет, то другое в этой паре отстает. А в вопросе говорится не про встречу каноэ, а про обгон. А т.к. у всех скорости разные, значит существуют 4 с самыми низкими скоростями, которые не смогут обогнать по 4 каноэ, у которых скорость выше.

[Artem of 93]

т.к. у всех скорости разные

В условии не говорится однозначно, что у всех разные скорости. Там формулировка следующая: "... скоростью, необязательно одинаковой". Я это понял так, что допускается некое количество каноэ (n из 9) с одинаковой скоростью.

[StrannikPiter]

Головолом, я согласен с Вашей трактовкой обгона, но при ней задача совсем бессмысленна, приходится искать другие трактовки.

Artem of 93, если скорости могут быть равны, то мое доказательство требует уточнения.

Если самое быстрое каноэ не одно, а есть несколько, с равной скоростью, но большей, чем у всех остальных, тогда они должны стартовать на 5, 6 и т.д. местах. Дня нескольких самых медленных, это будут 5, 4, и т.д. места. На 5 месте все равно конфликт.

[Artem of 93]

приходится искать другие трактовки

Действительно, условия задачи очень туманные. Если применять к задаче стандартное определение обгона, то становится не совсем понятно, для чего в задаче фигурирует число 4.

[maska11]

Скорости могут быть одинаковыми, а могут быть разными. В оригинале задачи, если переводить дословно, то "каждое каноэ по дороге не могло встретить четыре других".

[Artem of 93]

"каждое каноэ по дороге не могло встретить четыре других".

Это условие не равносильно тому, которое привели Вы.

Это подразумевает, что каждое каноэ может опередить кого-то и отстать от кого-то. В таком случае решение уже прозвучало.

Кстати, эту задачу можно задать в общем виде для нечётного числа каноэ.

[StrannikPiter]

Если задать в общем виде, то это будет как подсказка.

[maska11]

    "Это подразумевает, что каждое каноэ может опередить кого-то и отстать от кого-то." Скорее всего так и есть. Большое спасибо за помощь.!

[Artem of 93]

Если задать в общем виде, то это будет как подсказка.

Можно сформулировать иначе. Например, всего было n каноэ. Найдите минимальное количество каноэ, с которым не сможет встретиться каждое из n каноэ.