301. На плоскости заданы 2n точек — синих и красных, причём никакие три точки не лежат на одной прямой. Докажите, что можно провести n отрезков так, что у каждого отрезка один конец — синяя точка, другой — красная, а никакие два отрезка не пересекаются.

302. Пусть O — точка пересечения диагоналей трапеции ABCD с основаниями AB и CD, а точки A' и B' симметричны соответственно точкам A и B относительно биссектрисы угла AOB. Докажите равенство углов ACA' и BDB'.

303. Прямоугольник размером 300×1000 разрезан на квадраты 1×1, и в некоторых 30 вершинах квадратов помещены одинаковые гирьки. Докажите, что можно выбрать две непересекающиеся группы гирек — не более чем по 10 в каждой — так, что их центры тяжести совпадут.

304. Будем обозначать звёздочкой некоторую операцию, применимую к любым двум целым неотрицательным числам a и b и дающую в результате тоже целое неотрицательное число a * b. Пусть операция * удовлетворяет следующим условиям:

• a * b = b * a;
• если a * b = c, то b * c = a;
• если a * b > c, то b + c < a или a * c < b.

а) Найдите 0 * 0, 0 * 1, 1 * 1 и 0 * 2.

б) Докажите равенство 0 * a = a и докажите, что 1 * a = a + 1, если a чётно, и a – 1, если a нечётно.

в) Существует не более чем одна такая операция. Докажите это.

г) Такая операция существует. Докажите это и укажите правило, позволяющее по заданным a и b вычислять a * b.

305*. а) На хордах AB и A'B' окружности выбрано по точке C и C' так, что прямые AA', BB' и CC' пересекаются в одной точке P. Обозначим AP · PA' = t, AC · CB = s, A'C' · C'B' = S, CP = q, C'P = Q. Докажите, что если q то квадратный корень из отношения S ⁄ s равен отношению Q ⁄ q, S ⁄ s, отношению (S + Q²) ⁄ t и отношению t ⁄ (q² + s).

б) Через точку P, не лежащую на данной сфере, и каждую точку некоторой окружности, лежащей на этой сфере, проведена прямая. Докажите, что вторые точки пересечения проведённых прямых со сферой также лежат на некоторой окружности.

Замечание. Пункт б) можно решить при помощи утверждения пункта а), поэтому они и объединены под одним номером. Подумайте, однако, как решить пункт б) при помощи инверсии.

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

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

308. Если при любом x сумма чисел a₁cos x, a₂cos 2x, ..., a_ncos nx больше или равна –1, то сумма a₁ + a₂ + ... + a_n не превышает n. Докажите это утверждение для а) n = 2; б) n = 3; в) любого натурального n.

309. а) При каких n многочлен x²ⁿ + xⁿ + 1 делится на x² + x + 1?

б) При каких n на 37 делится число 100...00100...001, где как между первой и второй, так и между второй и третьей единицами стоит по n нулей?

310. Для любого натурального числа n среди n-значных чисел существует более 8ⁿ таких, в десятичной записи которых никакая группа цифр (в частности, никакая цифра) не встречается два раза подряд. Докажите это.

311. Из одной бактерии получилось 1000 следующим образом: вначале бактерия разделилась на две, затем одна из двух получившихся бактерий разделилась на две, затем одна из трёх получившихся бактерий разделилась на две и так далее. Докажите, что в некоторый момент существовала такая бактерия, число потомков которой среди 1000 бактерий, получившихся в конце, заключено между 334 и 667.

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

313. Рассмотрим множество четвёртых вершин параллелограммов ONML, вершины N и L которых лежат на сторонах данного угла с вершиной O, а площадь равна данной величине. (Это множество — ветвь гиперболы.) Докажите, что на биссектрисе этого угла и на её продолжении существуют такие точки F₁ и F₂, что разность расстояний F₁M и F₂M одна и та же для всех точек M.

Можно доказать, что F₁O = OF₂ и существуют перпендикулярные биссектрисе данного угла такие прямые d₁ и d₂ (директрисы гиперболы), что отношение длины отрезка F₁M (или F₂M) к расстоянию от точки M до прямой d₁ (соответственно, d₂) одно и то же для всех точек M.

314. Среди всех 9-значных чисел, в десятичной записи которых нет цифры 0, найдите такое, для которого разность между самим числом и произведением его цифр а) наименьшая; б) наибольшая.

в) Каков ответ для n-значных чисел при любом n?

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

316. а) Сумма квадратов k последовательных натуральных чисел не может быть квадратом целого числа, если k равно 3, 5, 7 или 9. Докажите это.

б) Придумайте 11 последовательных натуральных чисел, сумма квадратов которых есть квадрат целого числа.

317*. На некоторой планете каждая страна граничит не более чем с 7 другими. В каждой стране имеется запас золота. Требуется распределить золото так, чтобы каждые две страны, граничащие друг с другом, отличались по количеству золота не более чем в 13 раз. Докажите, что распределение золота можно организовать так, чтобы каждая страна лишилась не более половины имевшегося у неё золота.

318. В треугольнике ABC проведены биссектрисы AD и CE. Докажите, что CE · AB = AD · BC тогда и только тогда, когда AB = BC или величина угла ABC равна 60°.

319. На плоскости заданы окружность γ и точка P внутри неё. Рассмотрим тетраэдры ABCD, у каждого из которых все грани равны, причём треугольник ABC вписан в окружность γ так, что его медианы пересекаются в точке P.

а) При каком положении точки P внутри γ такие тетраэдры существуют?

б) Докажите, что вершина D любого такого тетраэдра расположена в одной из двух фиксированных точек пространства (симметричных относительно данной плоскости).

320*. Какие выпуклые n-угольники можно разбить на треугольники так, чтобы никакие два из треугольников разбиения не имели общих (полностью совпадающих) сторон? (На рисунке показано, что треугольник так разбить можно.)

321. Для любого прямоугольного стола и для любого положительного числа ε можно указать такую систему покрывающих этот стол прямоугольных салфеток, края которых параллельны краям стола, что любая её подсистема, состоящая из неперекрывающихся салфеток, имеет площадь, меньшую ε.

322. а) Фигура, состоящая более, чем из одной точки, является пересечением N кругов. Докажите, что границу этой фигуры можно представить в виде объединения 2N – 2 дуг окружностей.

б) В алфавите N букв. Несколько букв выписано по окружности так, что никакая буква не встречается два раза подряд и для любых двух различных букв a и b можно провести прямую так, что все буквы a будут по одну сторону от прямой, а буквы b — по другую. Докажите, что выписано не более 2N – 2 букв.

323*. Любую функцию, определённую на всей числовой прямой, можно представить в виде суммы двух функций, график каждой из которых имеет центр симметрии. Докажите это.

324. Имеется несколько куч камней. Двое играют в игру, ход которой состоит в том, что игрок разбивает каждую кучу, состоящую более чем из одного камня, на две меньшие кучи. Ходы делают поочередно, пока во всех кучках не останется по одному камню. Победителем считается игрок, сделавший последний ход. Как должен играть начинающий, если сначала в каждой кучке было от 80 до 120 камней?

325. В некотором треугольнике верхнее число равно 1, крайние числа в каждой строке — тоже 1, а каждое из остальных чисел не меньше суммы двух чисел, стоящих над ним (в частности, этому условию удовлетворяет треугольник Паскаля). Натуральное число a, большее 1, встретилось в этом треугольнике k раз. Докажите неравенство 2^k < a² .

326. Хорда окружности удалена от центра на расстояние h. В каждый из сегментов, стягиваемых хордой, вписано по квадрату так, что две соседние вершины квадрата лежат на дуге, две другие — на хорде. Чему равна разность длин сторон этих квадратов?

327. В компании n человек. Каждому из них нравятся ровно k человек из этой компании. При каком наименьшем k можно утверждать, что обязательно найдутся два человека из этой компании, нравящиеся друг другу?

328. По правильному тетраэдру ползают два паука и муха. Муха ползает только по рёбрам, а пауки — по всей поверхности. Максимальная скорость мухи в 2 раза больше максимальной скорости пауков.

а) Докажите, что при любом начальном расположении пауки могут поймать муху.

б) Верно ли это, если максимальная скорость мухи более чем в 2 раза превосходит максимальную скорость пауков?

в) Как изменится ответ, если разрешить паукам ползать только по рёбрам тетраэдра? по всему объёму тетраэдра?

329. Среди вершин любого выпуклого n-угольника, расположенного внутри квадрата со стороной 1, обязательно есть такие три вершины, что площадь треугольника с вершинами в них меньше числа 8 ⁄ n² . Докажите это.

330*. На плоскости расположены два выпуклых многоугольника M₀ и M₁. Обозначим буквой M множество середин отрезков, один конец каждого из которых принадлежит M₀, а другой — M₁. Докажите, что M — выпуклый многоугольник.

а) Сколько сторон может иметь M, если M₀ имеет n₀, а M₁ — n₁ сторон?

б) Каким может быть периметр многоугольника M, если периметр M₀ равен P₀, а периметр M₁ равен P₁?

в) Какой может быть площадь многоугольника M, если площадь многоугольника M₀ равна S₀, а площадь M₁ равна S₁?

331. а) Треугольник A'B'C' получен из треугольника ABC поворотом вокруг центра описанной окружности на некоторый угол, меньший 180°. Докажите, что точки пересечения пар прямых: AB и A'B', BC и B'C', CA и C'A' — являются вершинами треугольника, подобного треугольнику ABC.

б) Четырёхугольник A'B'C'D' получен из вписанного в окружность четырёхугольника ABCD поворотом вокруг центра окружности на угол, меньший 180°. Докажите, что точки пересечения соответствующих прямых: AB и A'B', BC и B'C' , CD и C'D', DA и D'A' — являются вершинами параллелограмма.

332. При каких k можно составить куб с ребром k из белых и чёрных единичных кубиков так, чтобы для каждого кубика ровно два из его соседей были бы того же цвета, что и сам кубик? (Два кубика считаем соседними, если они имеют общую грань.)

333. Три мухи ползают по сторонам треугольника АВС так, что центр тяжести образуемого ими треугольника остаётся на одном месте. Докажите, что он совпадаёт с центром тяжести треугольника АВС, если известно, что одна из мух проползла по всей границе треугольника. (Центр тяжести треугольника — это точка пересечения его медиан.)

334*. Дан многочлен P с а) натуральными; б) целыми коэффициентами. Для каждого натурального числа n обозначим сумму цифр десятичной записи числа |P(n)| через a_n. Докажите существование числа, которое встречается в последовательности a₁, a₂, a₃, ... бесконечно много раз.

335*. а) В квадрате размером 7×7 клеток отмечены центры k клеток. При этом никакие четыре отмеченные точки не являются вершинами прямоугольника со сторонами, параллельными сторонам квадрата. При каком наибольшем k это возможно?

б) Решите ту же задачу для квадрата размером 13×13 клеток.

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

337. Дан равносторонний треугольник АВС со стороной 1. Первый игрок выбирает точку Х на стороне АВ, второй — точку Y на стороне ВС, затем первый — точку Z на стороне AC.

а) Цель первого игрока — получить треугольник XYZ как можно большей площади, второго — как можно меньшей площади. Какую наибольшую площадь может обеспечить первый?

б) Цель первого игрока — получить треугольник XYZ как можно меньшего периметра, второго — как можно большего периметра. Какой наименьший периметр может обеспечить первый?

338. На доске написано несколько нулей, единиц и двоек. Разрешено стереть две неравные цифры и вместо них написать одну цифру, отличную от стёртых (2 вместо 0 и 1, 1 вместо 0 и 2, 0 вместо 1 и 2). Докажите, что если в результате нескольких таких операций на доске останется одна-единственная цифра, то она не зависит от порядка, в котором производились стирания.

339. Дана горизонтальная полоса на плоскости, края которой — параллельные прямые, и n прямых, пересекающих эту полосу. Каждые две из этих n прямых пересекаются внутри полосы; никакие три не проходят через одну точку. Рассмотрим все пути, начинающиеся на нижней кромке полосы, идущие по данным прямым и заканчивающиеся на верхней кромке, обладающие такими свойствами: идя по такому пути, мы всё время поднимаемся вверх; дойдя до точки пересечения прямых, мы обязаны перейти на другую прямую. Докажите, что среди таких путей есть путь,

а) состоящий не менее чем из n отрезков;

б) проходящий не более чем по ⁿ⁄₂ + 1 прямым;

в) проходящий по всем n прямым.

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

а) Пусть про таблицу T известно, что любая таблица размером 2×2, получающаяся в пересечении двух столбцов и двух строк таблицы T, имеет седловую клетку. Докажите, что тогда таблица Т также имеет седловую клетку.

б) Пусть a₁, a₂, ..., a_m, b₁, b₂, ..., b_n — произвольные числа, p₁, p₂, ..., p_m, q₁, q₂, ..., q_n — положительные числа. Докажите, что таблица размером m×n, на пересечении i-й строки и j-го столбца которой стоит число (a_i + b_j) ⁄ (p_i + q_j), имеет седловую клетку.

Одно из решений пункта б) можно получить, используя пункт а). Подумайте, однако, как можно решить эту задачу другим способом.

341*. В чемпионате мира участвуют 20 команд. Среди них k европейских команд, результаты встреч между которыми на чемпионате мира идут в зачёт чемпионата Европы. Чемпионат проводится в один круг. При каком наибольшем k может оказаться, что европейская команда, набравшая строго наибольшее количество очков в чемпионате Европы, наберёт строго наименьшее количество очков в чемпионате мира, если это чемпионат по а) хоккею (допускаются ничьи); б) волейболу (ничьих не бывает)? Каковы ответы на эти вопросы, если команд не 20, а n?

342*. а) Из цифр 1 и 2 можно составить 2ⁿ⁺¹ чисел, каждое из которых 2ⁿ-значно и каждые два из которых различаются не менее чем в 2^n–1 разрядах. Докажите это.

б) Более 2ⁿ⁺¹ таких 2ⁿ-значных чисел составить нельзя. Докажите это.

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

344*. На шахматной доске отмечены центры всех 64 полей. Можно ли провести на доске 13 прямых так, чтобы в каждой из частей, на которые эти прямые делят доску, оказалось не более одной отмеченной точки? (Прямые не должны проходить через центры полей.)

345. В последовательности 197523... каждая цифра, начиная с пятой, равна последней цифре суммы предыдущих четырёх цифр. Встретятся ли в этой последовательности подряд а) четыре цифры 1, 2, 3, 4; б) вторично цифры 1, 9, 7, 5; в) цифры 8, 1, 9, 7?

346. Точка K — середина стороны AB квадрата ABCD, а точка L делит диагональ AC в отношении 3 : 1. Докажите, что угол KLD прямой.

347. Двое играют в такую игру. Первый загадывает два числа от 1 до 25, а второй должен их угадать. Он может назвать любые два числа от 1 до 25 и узнать у первого, сколько из названных им чисел — 0, 1 или 2 — совпадают с загаданными. За какое минимальное число вопросов он сможет наверняка определить загаданные числа?

348. В таблицу размером 10×10 записаны числа от 1 до 100 по порядку. Затем в каждой строке и в каждом столбце ровно у половины чисел поставлен знак минус. Докажите, что сумма чисел полученной таблицы равна нулю.

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

350*. С белого углового поля шахматной доски размера n×m (числа n и m больше 1) начинает двигаться слон. Дойдя до края доски, слон поворачивает под прямым углом. Попав в угол, он останавливается.

а) При каких n и m слон обойдёт все белые поля доски?

б) Сколько всего полей он обойдёт на доске n×m?

Рассмотрите в качестве примеров доски размерами 10×15, 10×25 и 15×25.

351. Восстановите треугольник, если на плоскости отмечены три точки: O — центр описанной окружности, Р — центр тяжести и Н — основание одной из высот этого треугольника.

352*. Целая часть тридцатой степени числа, являющегося суммой числа 45 и квадратного корня из 1975, является нечётным числом. Докажите это.

353*. Пусть ABCD — произвольный тетраэдр. Докажите, что:

а) сумма величин всех двугранных углов тетраэдра, рёбрами которых являются AB, BC, CD и DA, меньше 360°;

б) сумма величин всех двугранных углов тетраэдра больше 360°, но меньше 540°;

в) сумма косинусов всех двугранных углов тетраэдра положительна и не превосходит 2, причём эта сумма равна 2 в том и только в том случае, когда все грани тетраэдра — равные треугольники;

г) если AB + CD = BD + DA, то сумма величин двугранных углов, рёбрами которых являются АВ и CD, равна сумме величин двугранных углов тетраэдра, рёбрами которых являются ВС и AD.

354. Можно ли расставить числа 1, 2, 3, ..., 4n + 2 в вершинах и серединах сторон правильного (2n + 1)-угольника так, чтобы сумма трёх чисел, стоящих в концах и середине каждой стороны, была для всех сторон одинаковой? (Рассмотрите в качестве примеров случаи n = 3 или 8.)

355. N ребят перекидываются N мячами. В начале игры каждый из них бросает свой мяч кому-нибудь из своих товарищей и сам ловит брошенный кем-нибудь мяч (он может подбросить и поймать свой собственный мяч) так, что снова у всех оказывается по мячу. Затем ребята снова бросают мячи тем же, кому они бросали их в первый раз, и так далее. Игра останавливается, когда все мячи вернулись к своим владельцам (чтобы мячи не перепутались, будем считать их разноцветными). Докажите, что:

а) для любого участника мяч вернётся к нему не более чем через N бросаний;

б) игра обязательно закончится;

в) для 5, 10 и 15 участников она может закончиться самое большее через соответственно 6, 30 и 105 бросаний (а какова максимально возможная длительность игры для N = 7, 8 или 20?);

г) длительность игры является делителем числа N! = 1 · 2 · ... · N;

д) длительность игры не может превышать числа 3^N/3.

356. Из точки M, взятой внутри треугольника A₁B₁C₁, опущены перпендикуляры MA₂, MB₂ и MC₂ на прямые B₁C₁, A₁C₁ и A₁B₁ соответственно. Затем из той же точки M опущены перпендикуляры MA₃, MB₃ и MC₃ на прямые B₂C₂, A₂C₂ и A₂B₂, и так далее. Докажите, что треугольник A₄B₄C₄ подобен треугольнику A₁B₁C₁ и, следовательно, для любого натурального n треугольник A_3n+1B_3n+1C_3n+1 подобен треугольнику A₁B₁C₁.

357. Если x + ¹⁄_y = y + ¹⁄_z = z + ¹⁄_x, то x = y = z или x²y²z² = 1. Докажите это.

358. В любом многоугольнике, кроме треугольника, есть хотя бы одна диагональ, целиком лежащая внутри него. Докажите это. Для каждого n выясните, какое наименьшее число таких диагоналей может иметь n-угольник.

359*. Маленький шарик движется внутри биллиарда, имеющего форму эллипса с фокусами A и B, упруго отражаясь от его бортов, по ломаной P₁P₂P₃P₄..., где P₁, P₂, P₃, P₄, ... — точки эллипса. Докажите, что если звено P₁P₂ не пересекает отрезок AB, то

а) ни одно из следующих звеньев P₂P₃, P₃P₄, P₄P₅, ... не пересекает отрезок AB;

б) все эти звенья касаются одного и того же эллипса. (Подумайте, как построить этот эллипс.)

360. Последовательность a₁, a₂, a₃, ... обладает тем свойством, что |a₁ | = 1 и |a_k+1 | = |a_k + 1| для любого натурального k. Найдите наименьшее возможное значение суммы |a₁ + a₂ + ... + a_n|, если а) n = 1975; б) n = 1976.