fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Турнир на 17 (16?) (15?) команд
Сообщение20.04.2023, 13:44 


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

В футбольном турнире каждая команда сыграла с каждой ровно один раз. Могло ли у каждой команды число побед оказаться равным числу ничей, если всего команд а) $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).

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

 Профиль  
                  
 
 Re: Турнир на 17 (16?) (15?) команд
Сообщение20.04.2023, 22:27 


21/04/22
356
someniatko в сообщении #1590418 писал(а):
Простейшие примеры - $3$ или $6$ команд. И примеры на этих количествах, например для $6$ команд, получаются не такие тривиальные и "идеально симметричные", как в случае 2).

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

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

 Профиль  
                  
 
 Re: Турнир на 17 (16?) (15?) команд
Сообщение20.04.2023, 23:22 
Аватара пользователя


01/11/14
2015
Principality of Galilee
someniatko в сообщении #1590418 писал(а):
Как построить пример в случае в), и можно ли его вообще построить (я думаю что да)
Например, так: аутсайдер проиграл все 14 матчей, а все остальные команды одержали по 5 побед и потерпели по 4 поражения.

(Оффтоп)


 Профиль  
                  
 
 Re: Турнир на 17 (16?) (15?) команд
Сообщение20.04.2023, 23:37 


06/11/21
26
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$ также становится тривиальным - просто пятиконечная "звездочка" с центром.

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

 Профиль  
                  
 
 Re: Турнир на 17 (16?) (15?) команд
Сообщение21.04.2023, 12:01 


26/08/11
2147
someniatko в сообщении #1590418 писал(а):
Вопрос в зал. Как построить пример в случае в)
Если можно построить для $n$, то можно построит и для $2n+1$ ("Новые" $n+1$ между собой заканчивают вничью, и выигрывают у "старых"). Так что можно построить для $1,3,7,15$ человек.

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

 Профиль  
                  
 
 Re: Турнир на 17 (16?) (15?) команд
Сообщение21.04.2023, 18:39 
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Skipper


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group