Задача 6. Список непобеждённых

Кто с кем дрался

Сначала поймём, как устроены поединки. Их было ровно $149$: первый боец со вторым, второй с третьим и так далее до $149$-го со $150$-м. Значит, каждый поединок — это встреча двух бойцов с соседними номерами, и других поединков не было.

Посмотрим с точки зрения одного бойца номер $k$. Он дрался с бойцом $k-1$ (в поединке «$(k-1)$-й с $k$-м») и с бойцом $k+1$ (в поединке «$k$-й с $(k+1)$-м») — всего два поединка. Только у крайних бойцов поединок один: боец $1$ дрался лишь со вторым, боец $150$ — лишь со $149$-м.

Зачем это нужно: условие «победил во всех своих поединках» теперь можно проверять очень конкретно — боец $k$ попадает в список, если он выиграл и у соседа слева, и у соседа справа.

Два соседа не могут оба быть в списке

Возьмём двух бойцов с соседними номерами, $k$ и $k+1$. Они дрались друг с другом. В этом поединке победил не больше чем один из них: либо $k$, либо $k+1$ (а если бывают ничьи, то при ничьей — никто).

Чтобы попасть в список, каждому из них нужно выиграть все свои поединки, в том числе этот общий. Но выиграть его оба не могут. Значит:

в списке никогда нет двух бойцов с соседними номерами.

Это и есть ключ к задаче: требование «все кратные $17$ и все кратные $20$ в списке» невыполнимо, если среди этих номеров найдутся два соседних числа (рисунок ниже).

Ищем соседей среди кратных 17 и 20

Выпишем номера, о которых спрашивают.

• Кратные $17$ от $1$ до $150$: 17, 34, 51, 68, 85, 102, 119, 136 (следующее, $153$, уже больше $150$).
• Кратные $20$: 20, 40, 60, 80, 100, 120, 140.

Два кратных $17$ между собой соседями быть не могут — они отличаются хотя бы на $17$; два кратных $20$ — тоже. Значит, соседей надо искать в парах «кратное $17$ и кратное $20$».

Как искать быстро: кратное $20$ оканчивается на $0$, поэтому его соседи оканчиваются на $9$ или на $1$. Среди кратных $17$ на $1$ оканчивается только $51$, а на $9$ — только $119$. Соседи числа $51$ — это $50$ и $52$, ни одно из них не делится на $20$. А сосед числа $119$ — число $120=6\cdot 20$.

Нашлась пара соседей: $119=7\cdot 17$ и $120=6\cdot 20$. Других таких пар нет: мы проверили все кратные $17$, оканчивающиеся на $1$ или на $9$.

Вывод: так быть не могло

Предположим, что в списке оказались все бойцы с номерами, кратными $17$, и все с номерами, кратными $20$. Тогда в списке есть и боец $119$ (он кратен $17$), и боец $120$ (он кратен $20$).

Но $119$ и $120$ — соседние номера, и их поединок «$119$-й со $120$-м» действительно был: он входит в те $149$ поединков. По шагу 2 в этом поединке не могли победить оба, значит, хотя бы один из бойцов $119$ и $120$ проиграл (или сыграл вничью) и в список не попал. Противоречие.

Ответ: нет, не могли.

Почему мешает именно эта пара

Полезно понять, что ответ «нет» держится ровно на соседях $119$ и $120$, а не на том, что отмеченных бойцов много.

Если бы среди отмеченных номеров не было соседних, всех их можно было бы поставить в список: пусть каждый отмеченный боец выиграет оба своих поединка. Помешать этому мог бы только поединок двух отмеченных бойцов друг с другом, а такие бойцы — соседи. Например, для кратных $17$ и кратных $19$ (до $150$) соседних номеров нет, и такой список возможен.

Для кратных $17$ и $20$ всех, кроме одного из бойцов $119$ и $120$, поставить в список можно — это показывает пример в модели: в списке $14$ отмеченных из $15$. А пятнадцатого не впустит никакая расстановка итогов.