Турнир на 17 (16?) (15?) команд

[someniatko]

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

В футбольном турнире каждая команда сыграла с каждой ровно один раз. Могло ли у каждой команды число побед оказаться равным числу ничей, если всего команд а) $17$, б) $16$, в) $15$.

Для а) почти сразу догадался, почему так не получится: общее число игр должно делиться на три: ведь на каждый матч, сыгранный вничью, у каждой из двух команд, его сыгравших, должно быть по победе, а общее число игр для случая с $17$ на три не делится ($\dfrac{17 \cdot 16}{2}$).

Для б) и в) это ограничение не выполняется, а каких-то других причин почему не получится я не придумал. Эксперименты с $3$, $4$, $6$, $7$ командами показали что все работает - легко нарисовать пример. Значит, нужно сконструировать положительный пример для этих вариантов (простого утверждения что число игр делится на три, ессно, недостаточно). И это оказалось намного сложнее - не рисовать же полный граф на $16$ вершинах. На этом моменте я чуток подсдался и пошел в гугл, и, к счастью, нормального решения там не оказалось. (Кто-то написал ерунду что при $16$ командах каждая сыграла с $15$, а это число на $2$ не делится - значит, число побед и ничей не может быть одинаковым. То, что бывают еще и поражения, сумрачный гений не учёл)

Для б), подумав, смог я родить такое объяснение: из рассуждения в а), общее число ничей должно составлять треть от игр вообще. В б) у каждой команды число ее игр - по $15$ - удобно делится на три. Значит, мы можем сделать каждой команде по $5$ ничей, и соответственно по столько же побед, и в остатке поражений. Как это сделать я тоже далеко не сразу догадался, но таки придумал: разместим команды по кругу. Пусть каждая команда проиграла пяти ближайшим по часовой, и выиграла у пяти ближайших против часовой. С остальными сыграла вничью. Тогда те пять ближайших по часовой по этому же правилу ее победят, а другие пять соответственно ей проиграют - вроде все сходится.

Для в) я даже не представляю как построить пример. Вообще, как я классифицировал в рамках этой задачи возможные кол-ва команд:
1) ни количество команд, ни число игр каждой команды не делится на три - тогда ответ "невозможно"
2) число игр у каждой команды делится на три. Тогда пример строится как в моем ответе для б)
3) кол-во команд делится на три. Простейшие примеры - $3$ или $6$ команд. И примеры на этих количествах, например для $6$ команд, получаются не такие тривиальные и "идеально симметричные", как в случае 2).

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

[mathematician123]

someniatko в сообщении #1590418 писал(а):

Простейшие примеры - $3$ или $6$ команд. И примеры на этих количествах, например для $6$ команд, получаются не такие тривиальные и "идеально симметричные", как в случае 2).

Можете показать пример для 6 команд? Я придумал пример для 9 команд, а для 6 не могу.

Если есть примеры для $3m$ и для $3n$ команд, то их можно "объединить" и построить пример для $3(m + n) $ команд.

[Gagarin1968]

someniatko в сообщении #1590418 писал(а):

Как построить пример в случае в), и можно ли его вообще построить (я думаю что да)

Например, так: аутсайдер проиграл все 14 матчей, а все остальные команды одержали по 5 побед и потерпели по 4 поражения.

(Оффтоп)

someniatko в сообщении #1590418 писал(а):

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

Правильно - ничьих.

[someniatko]

mathematician123 в сообщении #1590467 писал(а):

Можете показать пример для 6 команд?

Стрелки - победы (в направлении проигравшего), пунктир - ничьи.

mathematician123 в сообщении #1590467 писал(а):

Если есть примеры для $3m$ и для $3n$ команд, то их можно "объединить" и построить пример для $3(m + n) $ команд.

А это уже интересно! Тоже думал что как-то можно обойтись рассмотрением простейших случаев и объединить их, но как именно объединять - даже не догадываюсь.

-- 20.04.2023, 23:01 --

Gagarin1968 в сообщении #1590468 писал(а):

Например, так: аутсайдер проиграл все 14 матчей, а все остальные команды одержали по 5 побед и потерпели по 4 поражения.

Ага, так действительно всё становится просто - для остальных $14$ команд мы используем метод из б) - ставим команды по кругу, каждая проигрывает $4$ "слева" и побеждает $4$ "справа" + аутсайдера, с остальными $5$ ничья.

Мой пример для $6$ также становится тривиальным - просто пятиконечная "звездочка" с центром.

Спасибо, помогли дожать :)

[Shadow]

someniatko в сообщении #1590418 писал(а):

Вопрос в зал. Как построить пример в случае в)

Если можно построить для $n$, то можно построит и для $2n+1$ ("Новые" $n+1$ между собой заканчивают вничью, и выигрывают у "старых"). Так что можно построить для $1,3,7,15$ человек.

Только меня, пожалуйста, пишите в последнюю группу.

[EUgeneUS]

Есть решения для $3n$ и для $3n+1$ для любых $n \in \mathbb{N}$.
Это несложно доказывается увеличением турнирной таблицы для $3(n-1)$ или $3(n-1)+1$ до $3n$ или $3n+1$, соответственно, "готовыми блоками".

А для $3n-1$ решений нет ни для какого $n \in \mathbb{N}$, это с первого сообщения уже ясно.