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
1906
Principality of Galilee
someniatko в сообщении #1590418 писал(а):
Как построить пример в случае в), и можно ли его вообще построить (я думаю что да)
Например, так: аутсайдер проиграл все 14 матчей, а все остальные команды одержали по 5 побед и потерпели по 4 поражения.

(Оффтоп)

someniatko в сообщении #1590418 писал(а):
Могло ли у каждой команды число побед оказаться равным числу ничей
Правильно - ничьих.

 Профиль  
                  
 
 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
2100
someniatko в сообщении #1590418 писал(а):
Вопрос в зал. Как построить пример в случае в)
Если можно построить для $n$, то можно построит и для $2n+1$ ("Новые" $n+1$ между собой заканчивают вничью, и выигрывают у "старых"). Так что можно построить для $1,3,7,15$ человек.

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

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


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

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

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

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



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

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


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

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