Олимпиадные задачи по теме «Принцип крайнего» - сложность 3 с решениями
Принцип крайнего
НазадВ классе 27 учеников. Каждый из учеников класса занимается не более чем в двух кружках, причём для каждых двух учеников существует кружок, в котором они занимаются вместе. Докажите, что найдётся кружок, в котором занимаются не менее 18 учеников.
Каждый из учеников класса занимается не более чем в двух кружках, причём для любой пары учеников существует кружок, в котором они занимаются вместе. Докажите, что найдётся кружок, в котором занимается не менее ⅔ всего класса.
Компьютеры 1, 2, 3, ..., 100 соединены в кольцо (первый со вторым, второй с третьим, ..., сотый с первым). Хакеры подготовили 100 вирусов, занумеровали их и в различное время в произвольном порядке запускают каждый вирус на компьютер, имеющий тот же номер. Если вирус попадает на незаражённый компьютер, то он заражает его и переходит на следующий в цепи компьютер с большим номером до тех пор, пока не попадёт на уже заражённый компьютер (с компьютера 100 вирус переходит на компьютер 1). Тогда вирус погибает, а этот компьютер восстанавливается. Ни на один компьютер два вируса одновременно не попадают. Сколько компьютеров будет заражено в результате атаки этих 100 вирусов?
Даны <i>n</i> + 1 попарно различных натуральных чисел, меньших 2<i>n</i> (<i>n</i> > 1).
Докажите, что среди них найдутся три таких числа, что сумма двух из них равна третьему.
Внутри выпуклого многогранника выбрана точка <i>P</i> и несколько прямых <i>l</i><sub>1</sub>, ..., <i>l<sub>n</sub></i>, проходящих через <i>P</i> и не лежащих в одной плоскости. Каждой грани многогранника поставим в соответствие ту из прямых <i>l</i><sub>1</sub>, ..., <i>l<sub>n</sub></i>, которая образует наибольший угол с плоскостью этой грани (если таких прямых несколько, выберем любую из них). Докажите, что найдётся грань, которая пересекается с соответствующей ей прямой.
Внутри круга отмечены 100 точек, никакие три из которых не лежат на одной прямой.
Докажите, что их можно разбить на пары и провести прямую через каждую пару так, чтобы все точки пересечения прямых были в круге.
Пусть <i>p</i> – простое число. Набор из <i>p</i> + 2 натуральных чисел (не обязательно различных) назовём <i>интересным</i>, если сумма любых <i>p</i> из них делится на каждое из двух оставшихся чисел. Найдите все интересные наборы.
В команде сторожей у каждого есть разряд (натуральное число). Сторож <i>N</i>-го разряда <i>N</i> суток дежурит, потом <i>N</i> суток спит, снова <i>N</i> суток дежурит, <i>N</i> – спит, и так далее. Известно, что разряды любых двух сторожей различаются хотя бы в три раза. Может ли такая команда осуществлять ежедневное дежурство? (Приступить к дежурству сторожа могут не одновременно, в один день могут дежурить несколько сторожей.)
По кругу разложено чётное количество груш. Массы любых двух соседних отличаются не более чем на 1 г. Докажите, что можно все груши объединить в пары и разложить по кругу таким образом, чтобы массы любых двух соседних пар тоже отличались не более чем на 1 г.
Рациональные числа <i>x, y</i> и <i>z</i> таковы, что все числа <i>x + y</i>² + <i>z</i>², <i>x</i>² + <i>y</i> + <i>z</i>² и <i>x</i>² + <i>y</i>² + <i>z</i> целые. Докажите, что число 2<i>x</i> целое.
В каждой клетке таблицы 10×10 записано число. В каждой строке подчеркнули наибольшее число (или одно из наибольших, если их несколько), а в каждом столбце – наименьшее (или одно из наименьших). Оказалось, что все подчёркнутые числа подчёркнуты ровно два раза. Докажите, что все числа, записанные в таблице, между собой равны.
Для натурального <i>a</i> обозначим через <i>P</i>(<i>a</i>) наибольший простой делитель числа <i>a</i>² + 1.
Докажите, что существует бесконечно много таких троек различных натуральных чисел <i>a, b, c</i>, что <i>P</i>(<i>a</i>) = <i>P</i>(<i>b</i>) = <i>P</i>(<i>c</i>).
В Академии Наук 999 академиков. Каждая научная тема интересует ровно троих академиков, и у каждых двух академиков есть ровно одна тема, интересная им обоим. Докажите, что можно выбрать 250 тем из их общей области научных интересов так, чтобы каждый академик интересовался не более чем одной из них.
На доску выписаны 2011 чисел. Оказалось, что сумма каждых трёх выписанных чисел также является выписанным числом.
Какое наименьшее количество нулей может быть среди этих чисел?
В стране две столицы и несколько городов, некоторые из них соединены дорогами. Среди дорог есть платные. Известно, что на любом пути из южной столицы в северную имеется не меньше 10 платных дорог. Докажите, что все платные дороги можно раздать 10 компаниям так, чтобы на любом пути из южной столицы в северную имелись дороги каждой из компаний.
В каждой клетке квадратной таблицы написано по действительному числу. Известно, что в каждой строке таблицы сумма <i>k</i> наибольших чисел равна <i>a</i>, а в каждом столбце таблицы сумма <i>k</i> наибольших чисел равна <i>b</i>.
а) Докажите, что если <i>k</i> = 2, то <i>a = b</i>.
б) В случае <i>k</i> = 3 приведите пример такой таблицы, для которой <i>a ≠ b</i>.
На доске выписано (<i>n</i> – 1)<i>n</i> выражений: <i>x</i><sub>1</sub> – <i>x</i><sub>2</sub>, <i>x</i><sub>1</sub> – <i>x</i><sub>3</sub>, ..., <i>x</i><sub>1</sub> – <i>x<sub>n</sub></i>, <i>x</i><sub>2</sub> – <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub> – <i>x</i><sub>3</sub>, ..., <i>x</i><sub>2</sub> – <i>x<sub>n</sub></i>, ..., <i>x<sub>n</sub></i> – <i>x</i><sub><i>n</i>–1</sub>, где <i>n</i&...
В каждой клетке квадратной таблицы написано по числу. Известно, что в каждой строке таблицы сумма двух наибольших чисел равна <i>a</i>, а в каждом столбце сумма двух наибольших чисел равна <i>b</i>. Докажите, что <i>a = b</i>.
На кольцевом треке 2<i>n</i> велосипедистов стартовали одновременно из одной точки и поехали с постоянными различными скоростями (в одну сторону). Если после старта два велосипедиста снова оказываются одновременно в одной точке, назовём это встречей. До полудня каждые два велосипедиста встретились хотя бы раз, при этом никакие три или больше не встречались одновременно. Докажите, что до полудня у каждого велосипедиста было не менее <i>n</i>² встреч.
Клетчатый прямоугольник разбит на двухклеточные доминошки. В каждой доминошке провели одну из двух диагоналей. Оказалось, что никакие диагонали не имеют общих концов. Докажите, что ровно два из четырёх углов прямоугольника являются концами диагоналей.
Даны пять различных положительных чисел, сумма квадратов которых равна сумме всех десяти их попарных произведений. а) Докажите, что среди пяти данных чисел найдутся три, которые не могут быть длинами сторон одного треугольника.
б) Докажите, что таких троек найдется не менее шести (тройки, отличающиеся только порядком чисел, считаем одинаковыми).
На плоскости задано <i>n</i> точек, являющихся вершинами выпуклого <i>n</i>-угольника, <i>n</i> > 3. Известно, что существует ровно <i>k</i> равносторонних треугольников со стороной 1, вершины которых – заданные точки.
а) Докажите, что <i>k</i> < <sup>2<i>n</i></sup>/<sub>3</sub>.
б) Приведите пример конфигурации, для которой <i>k</i> > 0,666<i>n</i>.
Дано множество точек <i>O, A</i><sub>1</sub>, <i>A</i><sub>2</sub>, ..., <i>A<sub>n</sub></i> на плоскости. Расстояние между любыми двумя из этих точек является квадратным корнем из натурального числа. Докажите, что существуют такие векторы <i><b>x</b></i> и <i><b>y</b></i>, что для любой точки <i>A<sub>i</sub></i> выполняется равенство <img align="abs" src="/storage/problem-media/115863/problem_115863_img_2.gif"> где <i>k</i> и <i>l</i> – некоторые целые числа.
В неравнобедренном треугольнике две медианы равны двум высотам. Найдите отношение третьей медианы к третьей высоте.
В стране некоторые пары городов соединены дорогами, которые не пересекаются вне городов. В каждом городе установлена табличка, на которой указана минимальная длина маршрута, выходящего из этого города и проходящего по всем остальным городам страны (маршрут может проходить по некоторым городам больше одного раза и не обязан возвращаться в исходный город). Докажите, что любые два числа на табличках отличаются не более чем в полтора раза.