Олимпиадные задачи по теме «Отношение порядка» для 11 класса - сложность 1-3 с решениями
Отношение порядка
НазадНа берегу круглого острова Гдетотам расположено 20 деревень, в каждой живёт по 20 борцов. Был проведён турнир, в котором каждый борец встретился со всеми борцами из всех других деревень. Деревня <i>А</i> считается сильнее деревни <i>Б</i>, если хотя бы <i>k</i> поединков между борцами из этих деревень заканчивается победой борца из деревни <i>А</i>. Выяснилось, что каждая деревня сильнее следующей за ней по часовой стрелке. Какое наибольшее значение может иметь <i>k</i>? (У всех борцов разная сила, и в поединке всегда побеждает сильнейший.)
На соревнованиях по фигурному велосипедированию было 100 судей. Каждый судья упорядочил всех участников (от лучшего по его мнению – к худшему). Оказалось, что ни для каких трёх участников <i>A, B, C</i> не нашлось трёх судей, один из которых считает, что <i>A</i> – лучший из трёх, а <i>B</i> – худший, другой – что <i>B</i> лучший, а <i>C</i> худший, а третий – что <i>C</i> лучший, а <i>A</i> худший. Докажите, что можно составить общий рейтинг участников так, чтобы для каждых двух участников <i>A</i> и <i>B</i> тот, кто выше в рейтинге, был бы лучше другого по мнению хотя бы половины судей.
Пусть <i>T</i><sub>α</sub>(<i>x, y, z</i>) ≥ <i>T</i><sub>β</sub>(<i>x, y, z</i>) для всех неотрицательных <i>x, y, z</i>. Докажите, что <img align="absmiddle" src="/storage/problem-media/61423/problem_61423_img_2.gif"> Определение многочленов <i>T</i><sub>α</sub> смотри в задаче <a href="https://mirolimp.ru/tasks/161417">161417</a>, про показатели смотри в <a href="https://problems.ru/thes.php?letter=4#diagramma_junga">справочнике</a>.
а) Диаграммы Юнга (4, 1, 1) и (3, 3, 0) не сравнимы, – ни одна из них не мажорирует другую. Есть ли еще такие несравнимые наборы с суммой 6? б) Найдите все несравнимые пары наборов для <i>s</i> = 7. Про диаграммы Юнга смотри <a href="https://problems.ru/thes.php?letter=4#diagramma_junga">здесь</a>.
Нарисуйте все лестницы из четырёх кирпичей в порядке убывания, начиная с самой крутой (4, 0, 0, 0) и заканчивая самой пологой (1, 1, 1, 1).
Докажите, что <img align="absmiddle" src="/storage/problem-media/61420/problem_61420_img_2.gif"> тогда и только тогда, когда β можно получить из α проделав несколько (может быть один раз или ни одного) операции вида <div align="CENTER">(<i>k, j, i</i>) ↔ (<i>k</i> – 1, <i>j</i> + 1, <i>i</i>), (<i>k, j, i</i>) ↔ (<i>k</i> – 1, <i>j, i</i> + 1), (<i>k, j, i</i>) ↔ (<i>k, j</i> – 1, <i>i</i> + 1). </div>(Эти операции можно представлять себе как сбрасывание одного кирпича вниз на диаграмме Юнга. Про диаграммы Юнга смотри <a href="https://problems.ru/thes.php?letter=4#diagramma_junga">зд...