Олимпиадные задачи по теме «Отношение порядка» для 8-11 класса

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

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

В большую шкатулку положили 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 дней можно определить место каждого боксёра.

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

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

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

Дан 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>! способами.

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

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

Натуральные числа от 1 до 100 раскрашены в три цвета: 50 чисел – в красный, 25 чисел – в жёлтый и 25 – в зелёный. Известно, что все красные и жёлтые числа можно разбить на 25 троек так, чтобы в каждой тройке было два красных числа и одно жёлтое, которое больше одного красного и меньше другого. Аналогичное утверждение верно для красных и зелёных чисел. Обязательно ли все 100 чисел можно разбить на 25 четвёрок, в каждой из которых два красных числа, одно жёлтое и одно зелёное, при этом жёлтое и зелёное числа лежат между красными?

На соревнованиях по фигурному велосипедированию было 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>n</i>)  и  β = (β₁, ..., β_<i>n</i>)  – два набора показателей с равной суммой.

Докажите, что, если  α ≠ β,  то при всех неотрицательных  <i>x</i>₁, ..., <i>x_n</i>  выполняется неравенство  <i>T</i>_α(<i>x</i>₁, ..., <i>x_n</i>) ≥ <i>T</i>_β(<i>x</i>₁, ..., <i>x_n</i>).

Определение многочленов <i>T</i>_α смотри в задаче <a href="https://...

Пусть  <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).