Форум умных людей

В футбольном турнире участвуют mn команд, где m ≥ 2 и n ≥ 2. Командам присвоены номера
1, 2, . . . , mn в соответствии с результатами предварительного этапа. Организаторы собираются разбить команды на m групп по n команд так, чтобы для любых двух команд сумма номеров согруппниц той из этих двух команд, номер которой меньше, была больше. При каких m и n желание организаторов осуществимо?

Организаторы собираются разбить команды на m групп по n команд так, чтобы для любых двух команд сумма номеров согруппниц той из этих двух команд, номер которой меньше, была больше.
Что- то не понял смысл...Это как?

Может так понятнее.

...чтобы для любых двух команд А и В выполнялось условие: если номер А меньше номера В, то сумма номеров соперников по группе для команды А больше, чем для команды В.

ещё больше запутал )

Ну, он или очень хорошо подсказал или подсказал так, что это только показалось.

Fortpost, а это условие оригинальное?
Если я его правильно понял, то, по крайней мере, решению этой задачи ВСЕГДА будет удовлетворять ситуация, при которой сумма номеров в каждой группе будет одинаковой и таких групп можно создать сколь угодно много!
То есть, если я правильно понял, номера у каждых групп разные и их нумерация идет в хронологическом порядке. Значит, если сумма номеров в каждой из этих групп будет одинаковой, то какие бы ты не взял две команды (из разных групп), их номера ВСЕГДА будут отличаться (минимум на 1), а, следовательно, у команды с меньшим номером (допустим, эта команда А) ВСЕГДА сумма ОСТАВШИХСЯ номеров будет больше, чем сумма ОСТАВШИХСЯ номеров группы команды Б!
Задача об этом или я что-то не так понял? Если нет, расшифруй еще немного условие  :)

Типа так?
1   2
4   3
5   6
8   7

Да, и так можно сделать с разным количеством групп!

Да, условие перенесено из первоисточника без изменений. Правда оно существует в двух редакциях, и перепост был сделан с более поздней, а пояснение взято из первой.

Да, это так.

И здесь все правильно.

Мой вопрос с комментариями оказался решением? Или нужно дать характеристику формирования групп (типа, в них кол-во команд должно быть четным)?

Думаю не получится для четного количества групп с нечетным количеством команд. Например, 2 группы по 3 команды

А так думаю, ты ответил, главное чтобы сумма была в группах одинаковая.

Ага, нужно еще выяснить, при каких m и n такое возможно.

Да, так оно и есть!

Конечно, так оно и есть - как же такому не быть?!
Другое дело, что кол-во команд в принципе может быть нечетным (при нечетном кол-ве групп, разумеется). А вот это и есть условие для ответа. То есть сама задача сводится к доказательству этих обстоятельств.
Раз, уж, я начал, то и закончу - m и n должны быть больше или равны 2, причем (m+1)*n - должно быть четным числом.

Ура, решено!!! :beer:

а где доказательство, что при n=3 и нечётном m это всегда получится?

А я ведь зашел, чтобы просто условие уточнить.
Такие задачи направлены не на ответ (т.к. он сразу очевиден), а на поиск доказательства. Поэтому я и стал уточнять условие (требовалось ли там что-либо доказывать).





 

И не только это нужно доказать. Нужно также доказать и то, что при четном m и нечетном n это не получится.
Вот поэтому и нужно корректировать условие задачи (ИМХО), т.к. в ней важен не очевидный ответ, а доказательство.

Ну для четного m и нечетного n доказать легко:

(1+2+...mn)/m = mn(mn+1)/2m=n(mn+1)/2 - число нецелое, что противоречит условию

Молодец, Tim!!!
Cчитаю, что в задачах такого типа вот так и должен выглядеть ответ (Мало ли, что я там в ответе указал (списал, допустим)).
В отношении нечетных m и n, думаю, можно сделать "по разнице", т.е. простым бухгалтерским принципом двойной записи (чтобы пошел баланс):
Каждая группа при равномерном заполнении командами нечетным числом отличается на 1, следовательно, будет справедлива разница сумм групп (по отношению к средней группе (балансу), например, в отношении 3-х групп): (-1), 0 и 1 (т.е. есть баланс (-1)+0+1=0)), для которых, естественно, справедливы и 3 перестановки (проводки (по разнице)) (+1 (первая группа)), (-1+1(средняя группа)), (-1 (третья группа)).
В оригинале, думаю, доказательство будет другое, но это должно быть проще.
Fortpost, наверное, его нам опубликует  :)
ЗЫ: Мне задача понравилась - Fortpost, зачет!

что-то в рассуждениях про проводки я не понял доказательства
можно подробнее?

Постараюсь расшифровать.
Возьмем, к примеру, 3 группы. Равенство сумм номеров команд в каждой из групп гарантированно обеспечивается следующим равномерным заполнением:
1    2    3
6    5    4
7    8    9
12  11  10
13  14  15
Среди нечетного количества групп имеется центральная, где каждый номер симметричной ей команде (правее - (Дебет), а левее (Кредит)) «равноудален» от нее на одинаковое количество равных по модулю разниц (1). В указанном примере сумма номеров команд в каждой группе будет равна 39, 40, 41, где 40 – это баланс ((39+40+41)/3), от которого Актив отличается на (-1), а Пассив на (+1). Разумеется, итог не изменится, если изначально вести учет сразу «на разницу». Баланс формируется из операций и основан он на двойной записи по соответствующим счетам. Сумма операций постоянна и равна 1, т.е. на одном счет отражен 1, а на другом (-1). Если возник дисбаланс, это или неправильная арифметика или один из счетов отражен в противоположной части баланса. И если каждый счет соответствует конкретной операции, то (во втором случае) сумма дисбаланса, деленная на 2, должна это подтвердить, т.е. указать сумму операции. В нашем случае сумма операции постоянна и равна 1. Поэтому (1-(-1)/2=1 свидетельствует о том, что это ошибка операции и для баланса имеется реальная возможность поменять местами Актив с Пассивом (по результату этой операции). В нашем примере – это, допустим, развернуть связку 13-14 (Актив) и 8-9 (Пассив).
На всякий случай, пример с 5-тью группами:
1    2    3    4    5
10  9    8    7    6
11  12  13  14  15
20  19  18  17  16
21  22  23  24  25
30  29  28  27  26
31  32  33  34  35
_________________
124,125,126,127,128
-2    -1      0    -1    -2
Баланс = 126 (630/5).
Дисбаланс = 6.
6/2=3 - это две подлежащие исправлению операции: 1 - на разницу 2, а друга - на разницу 1.
Следовательно, баланса через операции исправляется.
Исправление (по связке):
- на операцию с суммой 2: (31-33) и (23-25), т.е. переносим (-2) из Дт. в Кт.
- на операцию с суммой 1: (12-13) и (3-4), т.е. переносим (-1) из Дт. в Кт.
В отношении же четных групп баланс невозможен, т.к. (1+2+3+…n)/n – нецелое число.

ага, понял, если n достаточно велико, то простора для манипуляций с балансом хватит, чтобы выровнять все разности.

а что делать, если n=3, а m - большое (например, 11) ?

По многочисленным просьбам трудящихся публикуется решение с доказательством.
Показать скрытый текст

ахвононокак!