Ещё одна футбольная задача

[Ktina]

$N$ футбольных команд провели турнир в один круг (каждая команда сыграла с каждой из остальных ровно один раз).
При каких натуральных $N$ могло случиться так, что каждая команда выиграла столько же матчей, сколько и свела вничью?

[Psw]

При $N=3k+1$, $k$ натуральное

[Ktina]

Psw
А как же $N=3$?
Пусть было три команды - Зубило, Дубило и Крокодило. Зубило проиграло обе игры, а Дубило с Крокодилом сыграли вничью.

[NSKuber]

При $N\equiv 0, 1$ по модулю 3. Доказательство с построением будет через пару часов.

[ET]

NSKuber в сообщении #1067725 писал(а):

При $N\equiv 0, 1$ по модулю 3

то, что для других нельзя, это почти элементарно (даем почти как в шахматах, за выигрыш 2 очка, за ничью по 1, тогда у каждой команды число очков делится на 3, но всего их $N(N-1)$) , а вот что для всех этих можно...

[12d3]

Для $N=3k$ пример такой.
Поделим всех на группы по 3 команды. Сначала пусть сыграют только игры внутри каждой группы. В группе две команды выигрывают у третьей, а между собой играют вничью. После этих игр условие задачи выполняется.
Теперь сыграем межгрупповые игры. Возьмем пару групп, команды 1,2,3 принадлежат первой группе, команды 4,5,6 - второй. Исходы игр такие($>$ значит выиграл, $=$ значит ничья, $<$ значит проиграл): $1>4,2>5,3>6,1<5,2<6,3<4,1=6,2=4,3=5$. Итого, по исходу этих девяти матчей, каждая команды по разу выиграла, проиграла и свела вничью, то есть условие задачи опять выполняется. Вот таким образом и проведем матчи между всеми группами, и условие задачи будет выполняться.

-- Ср окт 28, 2015 15:08:32 --

Для $N=3k+1$ пример немного изменяется. Выделим группу из четырех команд под названием "Цетровые", между остальными матчи проведем как описано выше. Внутри Центровых результаты такие: $1>2,2>3,3>4,4>1,1=3,2=4$. Осталось сыграть матчи между Центровыми и остальными. Остальных опять делим на тройки. Для каждой тройки результаты матчей такие: один проигрывает всем центровым, второй выигрывает у $1,2$, третий выигрывает у $3,4$, остальные матчи вничью. После сыгранных 12 игр между тройкой и Центровыми условие выполняется. По такому же принципу пусть играют все тройки.
Ну и, $N=1$ тоже удовлетворяет условию задачи.

[NSKuber]

Как уже упомянул ET, случай $N\equiv 2 \mod 3$ невозможен, так как при заданных условиях утроенная сумма всех побед равна $N^2-N$.

Пусть $N\equiv 0 \mod 3$. Разобьём все команды на тройки, в каждой из которых проведём игры следующим образом (спасибо примеру Ktina):

(дуга из $A$ в $B$ означает, что команда $A$ выиграла у команды $B$, неориентированное ребро обозначает ничью). Условие задачи в точности означает, что у каждой вершины поровну исходящих дуг и неориентированных рёбер.
Пока что баланс выигрышей и ничьих у всех команд сохранён. Игры между командами любой пары троек проведём следующим образом:

Снова баланс сохраняется, и теперь уже каждая команда сыграла с каждой.
Пусть $N\equiv 1 \mod 3$. Случай $N=1$ неинтересен, так что пусть $N\geq 4$. Выберем четыре команды, а остальные опять разобьём на тройки. Внутри троек игры проведём так же, как в первом случае, а в четвёрке вот так:

Все тройки попарно снова соединим так, как в первом случае, а четвёрка с каждой тройкой пусть играет вот так:


UPD: долго писал, опередили

[Shadow]

Для $n=3k+1$ можно расставить комманд по кругу и каждая коммадна выигрывает у следующих $k$ (по часовой стрелке, напр), проигрывает у предыдущих $k$, с остальными $k$ заканчиват вничью. Кажется, проблем не будет.
Для $n=3k$ можно по индукции - если можно для $3k$, то можно и для $3k+3$:
Выделим "новые" три с номерами $0,1,2$ -они знают как сыграть между собой, осталные $3k$ по допущению тоже знают. Межгрупповые матчи: одинаковые номера по модулю 3 - ничья, иначе напр. 0 выигрывает у 1,1 у 2, 2 у 0.

[Ktina]

Спасибо!