Задача #2

[Av_vA 3044]

Напиши

[Qutuzoff 1057]

Я вот никак не могу придумать такое распределение, чтоб 16 ответ был) Поэтому +1 к написанию ответа.ЗЫ. Чтоб ответ был 16, нада чтобы в каждой группе было больше половины группы таких учеников, которые учатся лучше большинства из этой же группы. То-есть больше половины учаться лучше чем остальные. которых тоже больше чем половина)То-есть:x>1/2y>1/2x+y=1Так не бывает)

Edited December 27, 2012 by Qutuzoff

[Mopak 880]

Вкратце подкину идею. Не надо делить их на группы! Если Вася дружит с Петей и Димой, то это не значит, что Петя и Дима дружат друг с другом.

Edited December 28, 2012 by Mopak

[Koofer 65]

Морак +1

Но поскольку ответ без особых пояснений, то не понятно откуда он взял 16. Поясняю:

Проанализируем:

Назовем ученика, который учится лучше большинства своих друзей "хорошим". Пусть n - общее число хороших учеников, тогда k - число друзей у хорошего ученика. Докажем, что n <= 16

Для этого разберем два случая.

1) k ≥ 8. Тогда пять худших учеников класса не являются хорошими. (действительно, не трудно проверить, что начиная с 8, количество "хороших" учеников в классе будет уменьшаться и не будет максимальным при 8ми.)

2) k ≤ 7. Лучший ученик класса является лучшим в k парах друзей, а любой другой хороший ученик – не менее, чем в (k+1)/2

парах. Поэтому хорошие ученики являются лучшими не менее, чем в k + (n-1)*(k+1)/2 парах. Это число не может превышать числа всех пар друзей в классе, равного 10k. Отсюда 2k + (n-1)(k+1) ≤ 20k, то есть n-1 <= 18*k/(k+1), Подставим k=7. n<= 18*7/8 +1 n<=16.5 но так как n число целое и не может быть округлено в большую сторону, то n <=16

Покажем, что n может равняться 16 (в принципе с этого можно начать решение). Занумеруем учеников числами от 1 до 20 в порядке ухудшения успеваемости и расположим номера в таблице 5×4:

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

Перебрав несколько вариантов (необязательно выписывать пары всех друзей, достаточно это делать для первых 3-4 учеников), мы получим, что идеальный вариант это:

Пара учеников является парой друзей, если их номера расположены одним из трех способов: а) в соседних строках и в разных столбцах (кроме последнего элемента если идти сверху-вниз и справа-налево); б) в одном столбце и один из номеров при этом находится в нижней строке; в) в одном столбце и один из номеров при этом находится в верхней строке.

При этом, как нетрудно проверить, все требуемые условия выполнены.

Задача не сводится к знанию каких-то математических законов. Тут чистая логика, масштабное мышление и способность к анализу.

Подобная задача встречалась на финалах Всероссийской олимпиаде по математике для 11х классов.

Edited December 28, 2012 by Koofer

[Koofer 65]

Так же, можно построить дерево графов, установить связи вершин по условию задачи и мы получим, что именно 16 вершин дерева будут иметь необходимое максимальное количество связей.

[Mopak 880]

Жесть, чёрт ногу сломит в таком решении)Попроще:Методом перебора или просто слегка подумав становится ясно, что 20 должно нацело делится на число друзей у каждого ученика. Таких чисел у нас шесть: 1,2,4,5,10,20.20 не может быть ни у кого, разве что у кого-то раздовение личности. Так же кэп подсказывает, что для того, чтобы определить большинство, нужно чтобы число друзей было нечётным. Остаются 2 числа. 1,5. Дальше считаем и выбираем наибольший ответ.

Edited December 28, 2012 by Mopak

[Koofer 65]

С первого взгляда, возможно, но если разобраться, то ничего сложного =)ммм, интересно. Да, действительно это так.Если учесть, что суть задачи - переборка, то Морак сделал правильные выводы и сузил количество вариантов до минимума.