Олимпиадные задачи из источника «Журнал "Квант"» для 10 класса - сложность 3 с решениями
Журнал "Квант"
НазадДокажите, что среди 50 человек найдутся двое, у которых чётное число общих знакомых (быть может, 0) среди остальных 48 человек.
а) Разбейте отрезок [0, 1] на чёрные и белые отрезки так, чтобы для любого многочлена <i>p</i>(<i>x</i>) степени не выше второй сумма приращений <i>p</i>(<i>x</i>) по всем чёрным отрезкам равнялась сумме приращений <i>p</i>(<i>x</i>) по всем белым интервалам.
(Приращением многочлена <i>p</i> по отрезку (<i>a, b</i>) называется число <i>p</i>(<i>b</i>) – <i>p</i>(<i>a</i>).) б) Удастся ли проделать аналогичную операцию для всех многочленов степени не выше 1995?
Геологи взяли в экспедицию 80 банок консервов, веса которых все известны и различны (имеется список). Через некоторое время надписи на консервах стали нечитаемыми, и только завхоз знает, где что. Он может это всем доказать (то есть обосновать, что в какой банке находится), не вскрывая консервов и пользуясь только сохранившимся списком и двухчашечными весами со стрелкой, показывающей разницу весов.
Докажите, что для этой цели ему
а) достаточно четырёх взвешиваний и
б) недостаточно трёх.
В какое наименьшее число цветов нужно раскрасить клетки бесконечного листа клетчатой бумаги, чтобы
а) каждые две клетки на расстоянии 6 были покрашены в разные цвета? б) каждые четыре клетки, образующие фигуру формы буквы Г, были покрашены в четыре разных цвета? (Расстояние между клетками – наименьшее число линий сетки, горизонтальных и вертикальных, которые должна пересечь ладья на пути из одной клетки в другую.)
В таблице <i>m</i> строк, <i>n</i> столбцов. <i>Горизонтальным ходом</i> называется такая перестановка элементов таблицы, при которой каждый элемент остаётся в той строке, в которой он был и до перестановки; аналогично определяется <i>вертикальный ход</i> ("строка" в предыдущем определении заменяется на "столбец"). Укажите такое <i>k</i>, что за <i>k</i> ходов (любых) можно получить любую перестановку элементов таблицы, но существует такая перестановка, которую нельзя получить за меньшее число ходов.
Пусть <i>n</i> и <i>b</i> – натуральные числа. Через <i>V</i>(<i>n, b</i>) обозначим число разложений <i>n</i> на сомножители, каждый из которых больше <i>b</i> (например:
36 = 6·6 = 4·9 = 3·3·4 = 3·12, так что <i>V</i>(36, 2) = 5). Докажите, что <i>V</i>(<i>n, b</i>) < <sup><i>n</i></sup>/<sub><i>b</i></sub>.
Даны три треугольника: <i>A</i><sub>1</sub><i>A</i><sub>2</sub><i>A</i><sub>3</sub>, <i>B</i><sub>1</sub><i>B</i><sub>2</sub><i>B</i><sub>3</sub>, <i>C</i><sub>1</sub><i>C</i><sub>2</sub><i>C</i><sub>3</sub>. Известно, что их центры тяжести (точки пересечения медиан) лежат на одной прямой, а никакие три из девяти вершин этих треугольников не лежат на одной прямой. Рассматриваются 27 треугольников вида <i>A<sub>i</sub>B<sub>j</sub>C<sub>k</sub></i>, где <i>i, j, k</i> независимо пробегают значения 1, 2, 3. Докажите, что...
Внутри окружности радиуса 1 расположена замкнутая ломаная (самопересекающаяся), содержащая 51 звено, причём известно, что длина каждого звена равна <img align="absmiddle" src="/storage/problem-media/98138/problem_98138_img_2.gif"> . Для каждого угла этой ломаной рассмотрим треугольник, двумя сторонами которого служат звенья ломаной, образующие этот угол (таких треугольников всего 51). Докажите, что сумма площадей этих треугольников не меньше, чем утроенная площадь правильного треугольника, вписанного в окружность.
На какое максимальное число частей могут разбить координатную плоскость <i>xOy</i> графики 100 квадратных трехчлёнов вида
<i>y = a<sub>n</sub>x</i>² + <i>b<sub>n</sub>x + c<sub>n</sub></i> (<i>n</i> = 1, 2, ..., 100)?
В прямоугольной таблице <i>m</i> строк и <i>n</i> столбцов (<i>m < n</i>). В некоторых клетках таблицы стоят звёздочки, так что в каждом столбце стоит хотя бы одна звёздочка. Докажите, что существует хотя бы одна такая звёздочка, что в одной строке с нею находится больше звёздочек, чем с нею в одном столбце.
Натуральный ряд представлен в виде объединения некоторого множества попарно непересекающихся целочисленных бесконечных арифметических прогрессий с положительными разностями <i>d</i><sub>1</sub>, <i>d</i><sub>2</sub>, <i>d</i><sub>3</sub>, ... . Может ли случиться, что при этом сумма <sup>1</sup>/<sub><i>d</i><sub>1</sub></sub> + <sup>1</sup>/<sub><i>d</i><sub>2</sub></sub> + ... + <sup>1</sup>/<i><sub>d<sub>k</sub></sub></i> не превышает 0,9? Рассмотрите случаи:
а) общее число прогрессий конечно;
б) прогрессий бесконечное число (в этом случае условие нужно понимат...
На плоскости дано <i>N</i> прямых (<i>N</i> > 1), никакие три из которых не пересекаются в одной точке и никакие две не параллельны. Докажите, что в частях, на которые эти прямые разбивают плоскость, можно расставить ненулевые целые числа, по модулю не превосходящие <i>N</i>, так, что суммы чисел по любую сторону от любой из данных прямых равны нулю.
Докажите, что если <i>K</i> чётно, то числа от 1 до <i>K</i> – 1 можно выписать в таком порядке, что сумма никаких нескольких подряд стоящих чисел не будет делиться на <i>K</i>.
В стране 1988 городов и 4000 дорог.
Докажите, что можно указать кольцевой маршрут, проходящий не более, чем через 20 городов (каждая дорога соединяет два города).
Числа 1, 2, 3, ..., <i>N</i> записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число <i>i</i>, то где-то слева от него встретится хотя бы одно из чисел <i>i</i> + 1 и <i>i</i> – 1. Сколькими способами это можно сделать?
Выпуклый <i>n</i>-угольник разрезан непересекающимися диагоналями на треугольники. Разрешается проделывать следующее преобразование (<i>перестройку</i>): взяв пару треугольников <i>ABD</i> и <i>BCD</i> с общей стороной, заменить их на треугольники <i>ABC</i> и <i>ACD</i>. Пусть <i>P</i>(<i>n</i>) – наименьшее число перестроек, за которое можно перевести каждое разбиение в любое. Докажите, что
а) <i>P</i>(<i>n</i>) ≥ <i>n</i> – 3;
б) <i>P</i>(<i>n</i>) ≤ 2<i>n</i> – 7;
в) <i>P</i>(<i>n</i>) ≤ 2<i>n</i> – 10 при <i>n</i> ≥ 13.
Прямой угол разбит на бесконечное число квадратных клеток со стороной единица. Будем рассматривать ряды клеток, параллельные сторонам угла (<i>вертикальные</i> и <i>горизонтальные</i> ряды). Можно ли в каждую клетку записать натуральное число так, чтобы каждый вертикальный и каждый горизонтальный ряд клеток содержал все натуральные числа по одному разу?
На окружности имеется 21 точка.
Докажите, что среди дуг, имеющих концами эти точки, найдётся не меньше ста таких, угловая мера которых не превышает 120°.
Последовательность чисел <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ... такова, что <i>x</i><sub>1</sub> = ½ и <img align="absmiddle" src="/storage/problem-media/97884/problem_97884_img_2.gif"> для всякого натурального <i>k</i>.
Найдите целую часть суммы <img align="absmiddle" src="/storage/problem-media/97884/problem_97884_img_3.gif">
В таблицу 10×10 нужно записать в каком-то порядке цифры 0, 1, 2, 3, ..., 9 так, что каждая цифра встречалась бы 10 раз.
а) Можно ли это сделать так, чтобы в каждой строке и в каждом столбце встречалось не более четырёх различных цифр?
б) Докажите, что найдётся строка или столбец, в которой (в котором) встречается не меньше четырёх различных чисел.
Из вершин основания тетраэдра в боковых гранях провели высоты, а затем в каждой из боковых граней основания двух лежащих в ней высот соединили прямой. Докажите, что эти три прямые параллельны одной плоскости.
Докажите, что существует бесконечное число пар таких соседних натуральных чисел, что разложение каждого из них содержит любой простой сомножитель не менее чем во второй степени. Примеры таких пар чисел: (8, 9), (288, 289).
В Швамбрании <i>N</i> городов, каждые два соединены дорогой. При этом дороги сходятся лишь в городах (нет перекрёстков, одна дорога поднята эстакадой над другой). Злой волшебник устанавливает на всех дорогах одностороннее движение таким образом, что если из города можно выехать, то в него нельзя вернуться. Доказать, что
а) волшебник может это сделать;
б) найдётся город, из которого можно добраться до всех, и найдётся город, из которого нельзя выехать;
в) существует единственный путь, обходящий все города;
г) волшебник может осуществить своё намерение <i>N</i>! способами.
Докажите для каждого натурального числа <i>n</i> > 1 равенство: [<i>n</i><sup>1/2</sup>] + [<i>n</i><sup>1/3</sup>] + ... + [<i>n</i><sup>1/<i>n</i></sup>] = [log<sub><sub>2</sub></sub><i>n</i>] + [log<sub><sub>3</sub></sub><i>n</i>] + ... + [log<i><sub>n</sub>n</i>].
В стране больше 101 города. Столица соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с десятью городами (если <i>A</i> соединён с <i>B</i>, то <i>B</i> соединён с <i>A</i>). Известно, что из каждого города можно попасть в любой другой (может быть, с пересадками). Доказать, что можно закрыть половину авиалиний, идущих из столицы, так, что возможность попасть из каждого города в любой другой сохранится.