3
1

В турнире брали участие $%n$% команд, каждая сыграла с каждой другой один раз без ничьих. При каких $%n$% всегда можно разбить все команды на несколько групп так, чтобы команды каждой группы вместе получили одинаковое количество побед?

задан 29 Апр '15 13:46

10|600 символов нужно символов осталось
2

Задача очень давно здесь находится без решения. Сейчас я понял, что надо делать.

Единственным случаем, когда разбиение всегда возможно, является $%n=4$%. Это легко проверить вручную. Действительно, наборы очков команд здесь могут принимать следующие значения: 3, 2, 1, 0 или 3, 1, 1, 1 или 2, 2, 2, 0 или 2, 2, 1, 1. Очевидно, что требуемое разбиение всегда возможно.

Докажем, что никакие другие значения не подходят. Отметим такой простой вспомогательный факт: если количество команд нечётно, то возможен такой исход, когда все они набрали одинаковое число очков. Делается это так: рассматриваем правильный многоугольник с нечётным числом сторон, вершины которого -- это команды. Считаем, что A выиграла у B, если при обходе по часовой стрелке дуга AB короче дуги BA. Ясно, что здесь будет соблюдён нужный баланс.

Теперь разберём два случая. Пусть $%n=2k+1$%, где $%k\ge1$%. Считаем, что первые $%2k-1$% команд во встречах между собой набрали равное количество очков, то есть $%k-1$%. Пусть у двух последних команд каждая из них выиграла, а предпоследняя команда победила последнюю. Тогда набор очков получается такой: $%k+1$%, ... , $%k+1$%, $%1$%, $%0$%. Все числа кроме одного кратны $%k+1$%, откуда ясно, что на группы с равным числом очков разбиения не существует.

Теперь пусть $%n=2k$%. Если команд всего две, то всё очевидно. Случай $%k=2$% был разобран. Пусть $%k\ge3$%. Будем считать, что первая команда выиграла у всех, а остальные между собой сыграли "поровну", то есть набрали по $%k-1$% очку. Получаются значения $%2k-1$%, $%k-1$%, ... , $%k-1$%. Здесь разбиение также невозможно, так как первое число не делится на $%k-1 > 1$%, а остальные делятся.

ссылка

отвечен 18 Май '15 15:12

@falcao: спасибо, что обратили внимание на эту задачу. Решения к ней я не знал.

(18 Май '15 20:07) Роман83
2

@Роман83: у меня поначалу не было даже гипотетического общего ответа. Я почти сразу заметил то, что для нечётной суммы очков возможен простой пример, а также что n=4 подходит. Нетрудно было проверить, что n=5 не подходит, а дальше было непонятно. Сегодня утром вспомнил про неё, и по дороге на работу решил.

(18 Май '15 20:13) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×967

задан
29 Апр '15 13:46

показан
386 раз

обновлен
18 Май '15 20:13

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru