Страниц: 1 [2]
  Печать  
Автор Тема: Если меньше, то больше  (Прочитано 10990 раз)
0 Пользователей и 1 Гость смотрят эту тему.

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

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #15 : Ноябрь 08, 2013, 22:00:21 �

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

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #16 : Ноябрь 08, 2013, 22:05:02 �

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

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

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





 
Записан
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #17 : Ноябрь 08, 2013, 22:08:37 �

а где доказательство, что при n=3 и нечётном m это всегда получится?
И не только это нужно доказать. Нужно также доказать и то, что при четном m и нечетном n это не получится.
Вот поэтому и нужно корректировать условие задачи (ИМХО), т.к. в ней важен не очевидный ответ, а доказательство.
Записан
Tim
Гений-Говорун
*
Offline Offline

Сообщений: 1079

СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145



Просмотр профиля
Ответ #18 : Ноябрь 08, 2013, 22:34:56 �

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

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


Эти пользователи сказали вам СПАСИБО :

Питер Пен

За это сообщение 1 пользователь сказал спасибо!
Записан
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #19 : Ноябрь 08, 2013, 23:12:56 �

Ну для четного 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, наверное, его нам опубликует  Smiley
ЗЫ: Мне задача понравилась - Fortpost, зачет!





Последнее редактирование: Ноябрь 08, 2013, 23:18:08 от Питер Пен Записан
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #20 : Ноябрь 08, 2013, 23:29:04 �

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

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #21 : Ноябрь 09, 2013, 02:22:08 �

Постараюсь расшифровать.
Возьмем, к примеру, 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 – нецелое число.
Записан
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #22 : Ноябрь 09, 2013, 08:36:27 �

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

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

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
fortpost
Высший разум
****
Offline Offline

Сообщений: 6853

СПАСИБО
-вы поблагодарили: 1794
-вас поблагодарили: 2261



Просмотр профиля
Ответ #23 : Ноябрь 09, 2013, 17:23:14 �

По многочисленным просьбам трудящихся публикуется решение с доказательством.
Показать скрытый текст
Последнее редактирование: Ноябрь 09, 2013, 17:25:57 от fortpost Записан

Лучший способ оказаться в дураках, это считать себя умнее других. Ф. Ларошфуко
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #24 : Ноябрь 09, 2013, 19:45:20 �

ахвононокак!
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Страниц: 1 [2]
  Печать  
 
Перейти в: