Олимпиадные задачи по теме «Отношение порядка» - сложность 2-3 с решениями

Числа от 1 до 1000000 покрашены в два цвета – чёрный и белый. За ход разрешается выбрать любое число от 1 до 1000000 и перекрасить его и все числа, не взаимно простые с ним, в противоположный цвет. Вначале все числа были чёрными. Можно ли за несколько ходов добиться того, что все числа станут белыми?

В большую шкатулку положили 10 шкатулок поменьше. В каждую из вложенных шкатулок либо положили 10 еще поменьше, либо ничего не положили. В каждую из меньших опять положили или 10, или ни одной, и т.д. После этого оказалось ровно 2006 шкатулок с содержимым. Сколько пустых?

Некоторые из чисел<i>a</i>₁,<i>a</i>₂, ..., <i>a</i>₂₀₀написаны синим карандашом, а остальные — красным. Если стереть все красные числа, то останутся все натуральные числа от 1 до 100, записанные в порядке возрастания. Если же стереть все синие числа, то останутся все натуральные числа от 100 до 1, записанные в порядке убывания. Докажите, что среди чисел<i>a</i>₁,<i>a</i>₂, ..., <i>a</i>₁₀₀содержатся все натуральные числа от 1 до 100 включительно.

На берегу круглого острова Гдетотам расположено 20 деревень, в каждой живёт по 20 борцов. Был проведён турнир, в котором каждый борец встретился со всеми борцами из всех других деревень. Деревня <i>А</i> считается сильнее деревни <i>Б</i>, если хотя бы <i>k</i> поединков между борцами из этих деревень заканчивается победой борца из деревни <i>А</i>. Выяснилось, что каждая деревня сильнее следующей за ней по часовой стрелке. Какое наибольшее значение может иметь <i>k</i>? (У всех борцов разная сила, и в поединке всегда побеждает сильнейший.)

Во время бала каждый юноша танцевал вальс с девушкой либо более красивой, чем на предыдущем танце, либо более умной, но большинство (не меньше 80%) – с девушкой одновременно более красивой и более умной. Могло ли такое быть? (Юношей и девушек на балу было поровну.)

Во время бала каждый юноша танцевал вальс с девушкой либо более красивой, чем на предыдущем танце, либо более умной, а один – с девушкой одновременно более красивой и более умной. Могло ли такое быть? (Юношей и девушек на балу было поровну.)

Три шахматиста <i>A, B</i> и <i>C</i> сыграли матч-турнир (каждый с каждым сыграл одинаковое число партий). Может ли случиться, что по числу очков <i>A</i> занял первое место, <i>C</i> – последнее, а по числу побед, наоборот, <i>A</i> занял последнее место, <i>C</i> – первое (за победу присуждается одно очко, за ничью – пол-очка)?

Имеется 100 серебряных монет, упорядоченных по весу, и 101 золотая монета, они также упорядочены по весу. Известно, что все монеты по весу различны. В нашем распоряжении – двухчашечные весы, позволяющие про каждые две монеты установить, какая тяжелее. Как за наименьшее число взвешиваний найти монету, занимающую среди всех монет 101-е место?

Имеется 50 серебряных монет, упорядоченных по весу, и 51 золотая монета, они также упорядочены по весу. Известно, что все монеты по весу различны. В нашем распоряжении – двухчашечные весы, позволяющие про каждые две монеты установить, какая тяжелее. Как за семь взвешиваний найти монету, занимающую среди всех монет 51-е место?

В некотором королевстве было 32 рыцаря. Некоторые из них были вассалами других (вассал может иметь только одного сюзерена, причём сюзерен всегда богаче своего вассала). Рыцарь, имевший не менее четырёх вассалов, носил титул барона. Какое наибольшее число баронов могло быть при этих условиях?

(В королевстве действовал закон: "вассал моего вассала – не мой вассал".)

В соревновании участвуют 32 боксёра. Каждый боксёр в течение одного дня может проводить только один бой. Известно, что все боксёры имеют разную силу, и что сильнейший всегда выигрывает. Докажите, что за 15 дней можно определить место каждого боксёра.

(Расписание каждого дня соревнований составляется вечером накануне и в день соревнований не изменяется.)

Дан 101 прямоугольник с целыми сторонами, не превышающими 100.

Докажите, что среди них найдутся три прямоугольника <i>A, B, C</i>, которые можно поместить друг в друга (так что  <i>A</i> ⊂ <i>B</i> ⊂ <i>C</i>).

Числа 1, 2, 3, ..., <i>N</i> записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число <i>i</i>, то где-то слева от него встретится хотя бы одно из чисел  <i>i</i> + 1  и  <i>i</i> – 1.  Сколькими способами это можно сделать?

В Швамбрании <i>N</i> городов, каждые два соединены дорогой. При этом дороги сходятся лишь в городах (нет перекрёстков, одна дорога поднята эстакадой над другой). Злой волшебник устанавливает на всех дорогах одностороннее движение таким образом, что если из города можно выехать, то в него нельзя вернуться. Доказать, что

  а) волшебник может это сделать;

  б) найдётся город, из которого можно добраться до всех, и найдётся город, из которого нельзя выехать;

  в) существует единственный путь, обходящий все города;

  г) волшебник может осуществить своё намерение <i>N</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> тот, кто выше в рейтинге, был бы лучше другого по мнению хотя бы половины судей.

С начала учебного года Андрей записывал свои оценки по математике. Получая очередную оценку (2, 3, 4 или 5), он называл её <i>неожиданной</i>, если до этого момента она встречалась реже каждой из всех остальных возможных оценок. (Например, если бы он получил с начала года подряд оценки 3, 4, 2, 5, 5, 5, 2, 3, 4, 3, то неожиданными были бы первая пятерка и вторая четвёрка.) За весь учебный год Андрей получил 40 оценок – по 10 пятерок, четвёрок, троек и двоек (неизвестно, в каком порядке). Можно ли точно сказать, сколько оценок были для него неожиданными?

Пусть  <i>T</i>_α(<i>x, y, z</i>) ≥ <i>T</i>_β(<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>_α смотри в задаче <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">зд...

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

Три бегуна А, Б, В несколько раз совершили забег на 100 метров. При подведении результатов оказалось, что А обогнал Б больше, чем в половине забегов, Б обогнал В больше, чем в половине забегов, а В обогнал А больше, чем в половине забегов. Могло ли это случиться?

Некто расставил в произвольном порядке 10-томное собрание сочинений. Назовём <i>беспорядком</i> пару томов, для которых том с большим номером стоит левее. Для данной расстановки томов посчитано число <i>S</i> всех беспорядков. Какие значения может принимать <i>S</i>?

Человечество бессмертно и начинает свою историю от Адама и Евы; каждый человек - смертен. Докажите, что найдется бесконечная мужская цепочка, начинающаяся с Адама, в который каждый следующий человек - сын предыдущего.