Олимпиадные задачи по теме «Примеры и контрпримеры. Конструкции» - сложность 4 с решениями

Докажите, что для любого натурального числа <i>a</i>₁ > 1 существует такая возрастающая последовательность натуральных чисел  <i>a</i>₁, <i>a</i>₂, <i>a</i>₃, ...,

что   <img align="absmiddle" src="/storage/problem-media/109599/problem_109599_img_2.gif">   делится на  <i>a</i>₁ + <i>a</i>₂ + ... + <i>a_k</i>  при всех  <i>k</i> ≥ 1.

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

Можно ли разбить правильный тетраэдр с ребром 1 на правильные тетраэдры и октаэдры, длины ребер каждого из которых меньше 1/100?

Можно ли раскрасить все точки квадрата и круга в чёрный и белый цвета так, чтобы множества белых точек этих фигур были подобны друг другу и множества чёрных точек также были подобны друг другу (возможно, с различными коэффициентами подобия)?

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

Можно ли расположить бесконечное число равных выпуклых многогранников в слое, ограниченном двумя параллельными плоскостями, так чтобы ни один многогранник нельзя было вынуть из слоя, не сдвигая остальных?

В круговом шахматном турнире каждый участник сыграл с каждым из остальных один раз. Назовём партию <i>неправильной</i>, если выигравший её шахматист в итоге набрал очков меньше чем проигравший. (Победа даёт 1 очко, ничья – ½, поражение – 0.) Могут ли неправильные партии составлять

  а) более 75% от общего количества партий в турнире;

  б) более 70%?

У Феди есть три палочки. Если из них нельзя сложить треугольник, Федя укорачивает самую длинную из палочек на сумму длин двух других. Если длина палочки не обратилась в нуль и треугольник снова нельзя сложить, то Федя повторяет операцию, и т. д. Может ли этот процесс продолжаться бесконечно?

В круговом шахматном турнире каждый участник играет с каждым из остальных один раз. За выигрыш присуждается одно очко, за ничью – пол-очка, за проигрыш – ноль. Назовём партию <i>неправильной</i>, если выигравший её шахматист в итоге набрал очков меньше проигравшего.

  а) Докажите, что неправильные партии составляют меньше ¾ общего числа партий в турнире.

  б) Докажите, что в пункте а) число ¾ нельзя заменить на меньшее.

Каждая сторона правильного треугольника разбита на <i>n</i> равных отрезков, и через все точки деления проведены прямые, параллельные сторонам. Данный треугольник разбился на <i>n</i>² маленьких треугольников-клеток. Треугольники, расположенные между двумя соседними параллельными прямыми, образуют полоску.

  а) Какое наибольшее число клеток можно отметить, чтобы никакие две отмеченные клетки не принадлежали одной полоске ни по одному из трёх направлений, если  <i>n</i> = 10?

  б) Тот же вопрос для  <i>n</i> = 9.

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

б) Тот же вопрос про правильные пятиугольники.

В некотором государстве человек может быть зачислен в полицию только в том случае, если он выше ростом чем 80% (или больше) его соседей. Чтобы доказать свое право на зачисление в полицию, человек сам называет число <i>R</i> (радиус), после чего его "соседями" считаются все, кто живёт на расстоянии меньше <i>R</i> от него (число соседей, разумеется, должно быть не нулевое). В этом же государстве человек освобождается от службы в армии только в том случае, если он ниже ростом, чем 80% (или больше) его соседей. Определение "соседей" аналогично; человек сам называет число <i>r</i> (радиус) и т. д., причём <i>R</i> и <i>r</i> не обязательно совпадают. Может ли случиться, что не менее 90% населения имеют право на зач...

Число рёбер многогранника равно 100.

  а) Какое наибольшее число рёбер может пересечь плоскость, не проходящая через его вершины, если многогранник выпуклый?

  б) Докажите, что для невыпуклого многогранника это число может равняться 96,

  в) но не может равняться 100.

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

  а) Докажите, что это возможно.

  б) Докажите, что если в формулировке заменить число 5 на число 4, то желание короля станет неосуществимым.

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

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

На бесконечной во все стороны шахматной доске выделено некоторое множество клеток <i>A</i>. На всех клетках доски, кроме множества <i>A</i>, стоят короли. Все короли могут по команде одновременно сделать ход, заключающийся в том, что король либо остаётся на месте, либо занимает соседнее поле, то есть делает "ход короля". При этом он может занять и то поле, с которого сходит другой король, но в результате хода двум королям оказаться в одной клетке запрещается. Существует ли такое <i>k</i> и такой способ движения королей, что после <i>k</i> ходов вся доска будет заполнена королями? Рассмотрите варианты:

  а) <i>A</i> есть множество всех клеток, у которых обе координаты кратны 100 (предполагается, что одна горизонтальная...

а) Доказать, что для любых положительных чисел  <i>x</i>₁, <i>x</i>₂, ..., <i>x_k</i>  (<i>k</i> > 3)  выполняется неравенство: <div align="center"><img src="/storage/problem-media/97781/problem_97781_img_2.gif"></div>б) Доказать, что это неравенство ни для какого  <i>k</i> > 3  нельзя усилить, то есть доказать, что для каждого фиксированного <i>k</i> нельзя заменить двойку в правой части на большее число так, чтобы полученное неравенство было справедливо для любого набора из <i>k</i> положительных чисел.

<i>N</i> друзей одновременно узнали <i>N</i> новостей, причём каждый узнал одну новость. Они стали звонить друг другу и обмениваться новостями.

Каждый разговор длится 1 час. За один разговор можно передать сколько угодно новостей.

Какое минимальное количество часов необходимо, чтобы все узнали все новости? Рассмотрите три случая:

  а)  <i>N</i> = 64,

  б)  <i>N</i> = 55,

  в)  <i>N</i> = 100.

За круглым столом сидят <i>n</i> человек. Разрешается любых двух людей, сидящих рядом, поменять местами. Какое наименьшее число таких перестановок необходимо сделать, чтобы в результате каждые два соседа остались бы соседями, но сидели бы в обратном порядке?

а) Существует ли последовательность натуральных чисел <i>a</i>₁, <i>a</i>₂, <i>a</i>₃, ..., обладающая следующим свойством: ни один член последовательности не равен сумме нескольких других и  <i>a_n ≤ n</i>¹⁰  при любом <i>n</i>? б) Тот же вопрос, если  <i>a_n ≤ n</i><img width="27" height="33" align="MIDDLE" border="0" src="/storage/problem-media/79370/problem_79370_img_2.gif">  при любом <i>n</i>.

Существует ли такое натуральное число <i>A</i>, что если приписать его к самому себе справа, то полученное число окажется полным квадратом?

Можно ли каждую сторону квадрата так разделить на 100 частей, чтобы из полученных 400 отрезков нельзя было бы составить контура никакого прямоугольника, отличного от исходного квадрата?

Для каких <i>n</i> существует такая замкнутая несамопересекающаяся ломаная из <i>n</i> звеньев, что каждая прямая, содержащая одно из звеньев этой ломаной, содержит ещё хотя бы одно её звено?

Несколько человек в течение <i>t</i> минут наблюдали за улиткой. Каждый наблюдал за ней ровно 1 минуту и заметил, что за эту минуту улитка проползла ровно 1 метр. Ни в один момент времени улитка не оставалась без наблюдения. Какой наименьший и какой наибольший путь могла она проползти за эти <i>t</i> минут?

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

  а) Докажите существование такого числа <i>c</i>, что сумма чисел в любом прямоугольнике, стороны которого идут по линиям сетки, не больше <i>c</i>; другими словами, докажите, что суммы чисел в прямоугольниках ограничены.

  б) Докажите, что можно взять  <i>c</i> = 4.

  в) Улучшите эту оценку – докажите, что утверждение верно для  <i>c</i> = 3.

  г) Постройте пример, показывающий, что при  <i>c</i> > 3  утверждение неверно.