1756. Среди любых трёх из нескольких данных натуральных чисел можно выбрать два, одно из которых делится на другое. Докажите, что все числа можно так покрасить двумя красками, что из любых чисел одного цвета одно делится на другое.

1757*. Если выпуклый многоугольник можно разрезать на 20 параллелограммов, то его можно разрезать и на 15 параллелограммов.

1758. Всякий депутат имеет свой абсолютный рейтинг — некоторое присвоенное ему компетентными органами положительное число. Сразу после избрания депутатов распределили по фракциям и каждый из них вычислил свой относительный рейтинг — частное от деления абсолютного рейтинга на сумму абсолютных рейтингов всех (включая его самого) депутатов его фракции. Депутат может перейти из фракции в другую, если его относительный рейтинг при этом увеличивается. Ни в какой момент времени не может произойти более одного такого перехода. Докажите, что спустя конечное время переходы прекратятся.

1759. Если остроугольный треугольник можно разбить на две фигуры, диаметр каждой из которых не превосходит длины наименьшей стороны этого треугольника, то величина ни одного из его углов не меньше 36°. Докажите это. (Диаметр фигуры — это точная верхняя грань расстояний между её точками.)

1760. Таблицу размером n×n называем удивительной, если сумма всяких n её чисел, расположенных в разных строках и разных столбцах, не зависит от того, какие именно такие числа выбраны. Докажите, что каждую удивительную таблицу можно представить в виде суммы двух таблиц, у одной из которых все строки равны, а у другой равны все столбцы.

1761. У фокусника 100 карточек, занумерованных чисалми от 1 до 100. Он раскладывает все карточки в три ящика — красный, белый и синий — так, чтобы в каждом ящике лежала хотя бы одна карточка. Зритель выбирает по одной карточке из некоторых двух ящиков и сообщает фокуснику сумму номеров этих карточек. Фокусник по этой сумме сообщает, из какого ящика карточка не была взята. Сколькими способами может фокусник разложить карточки по ящикам, чтобы фокус всегда удавался? (Задать способ — указать для каждой карточки, в каком ящике ей лежать.)

1762. Существует ли такое натуральное число n, что 2ⁿ + 1 делится на n, а число n имеет ровно 2000 различных простых делителей?

1763*. AH₁, BH₂ и CH₃ — высоты треугольника ABC. Вписанная в треугольник ABC окружность касается сторон BC, CA и AB в точках T₁, T₂ и T₃ соответственно. Прямые l₁, l₂ и l₃ являются образами прямых H₂H₃, H₃H₁ и H₁H₂ относительно прямых T₂T₃, T₃T₁ и T₁T₂ соответственно. Докажите, что каждые две из прямых l₁, l₂ и l₃ пересекаются на вписанной окружности треугольника ABC.

1764. Функция f возрастает на [0; 1]. Если f (0) = 0 и для любых положительных чисел a и b, сумма которых не превосходит 1, верно неравенство f (a) + f (b) ³ f (a + b). Докажите неограниченность последовательности, n-й член которой равен сумме значений функции f в точках вида 1 ⁄ k, где 1 £ k £ n.

1765*. Длина ребра правильного тетраэдра равна 1. Докажите, что существуют две точки, рассстояние между которыми не превосходит 1/2, среди любых а) пяти точек, расположенных на его рёбрах; б) девяти точек, расположенных на его поверхности; в*) девяти точек, расположенных на поверхности или внутри тетраэдра.

1766. На бесконечной шахматной доске находятся ферзь и невидимый король, которому запрещено ходить по диагонали. Они ходят по очереди. Может ли ферзь ходить так, чтобы король рано или поздно попал под шах?

1767. Внутри квадрата ABCD расположены точки P и Q так, что величины углов PAQ и PCQ равна 45°. Докажите равенство PQ² = BP² + QD².

1768. а) Расположите первые 100 натуральных чисел в таком порядке, чтобы для любых нескольких (но не всех) из этих чисел сумма номеров занятых ими мест не равнялась сумме самих этих чисел.

б*) При посадке в аэробус пассажиры сели куда попало. В итоге все места оказались заняты, а для любого множества, в котором не более 100 пассажиров, среднее арифметическое номеров занятых ими мест не менее чем на 1 отличается от среднего арифметического номеров мест, указанных в билетах. Каково наименьшее возможное число мест в таком аэробусе?

1769*. Концы 2n непересекающихся хорд разделили окружность на 4n равных дуг. Докажите, что среди этих хорд существуют две параллельные.

1770. Дан многочлен степени 10 с целыми коэффициентами. Двое по очереди заменяют заменяют буквы на числа (каждым ходом — одну букву на одно число). После десятого хода получают некоторый многочлен f с числовыми коэффициентами. Если максимальное из значений, принимаемых функцией f на отрезке [–1; 0], меньше максимального из значений, принимаемых функцией f на отрезке [0; 1], то победил первый игрок, а если максимальное из значений, принимаемых функцией f на отрезке [–1; 0], больше максимального из значений, принимаемых функцией f на отрезке [0; 1], то второй. Кто из игроков имеет выигрышную стратегию?

1771. В результате деления числа, десятичная запись которого состоит из 3ⁿ единиц, на число 3ⁿ получили число M. Докажите, что число M целое и его можно разложить на n различных и отличных от 1 натуральных множителей.

1772. Каждое число последовательности a₁, a₂, a₃, ..., a_2n, a_2n+1 равно 2, 5 или 9. При этом a₁ = a_2n+1, но любые два соседних числа различных. Докажите равенство a₁a₂ – a₂a₃ + a₃a₄ – ... + a_2n–1a_2n – a_2na_2n+1 = 0.

1773. Проведённая из вершины C прямого угла высота CD и биссектриса AE треугольника ABC пересекаются в точке F. Обозначим буквой G точку пересечения прямых DE и BF. Докажите равенство площадей четырёхугольника CEGF и треугольника BDG.

1774. Король сказочной страны пригласил на пир людоедов своей страны. Среди них есть людоеды, которые хотят съесть других людоедов. Наидлиннейшая цепочка, в которой первый людоед хочет съесть второго, второй — третьего и так далее, состоит из 6 людоедов. Докажите, что людоедов можно так рассадить по шести комнатам, чтобы ни в какой комнате никто никого не хотел съесть.

1775. а) Существует ли квадрат, все вершины и все середины сторон которого лежат на гиперболах xy = ±1?

б) Существует бесконечно много параллелограммов, одна из вершин каждого из которых — начало координат, две другие лежат на гиперболе xy = 1, а четвёртая — на гиперболе xy = –1. Докажите это.

в) Площадь каждого такого параллелограмма равна квадратному корню из 5. Докажите это.

г) Рассмотрим для любого такого параллелограмма OABC порождённую им решётку, то есть множество таких точек M, что вектор OM равен сумме умноженного на некоторое целое число вектора OA и умноженного на некоторое целое число вектора OC. Докажите, что внутренность <креста>, ограниченного гиперболами xy = ±1, не содержит ни одной точки этой решётки, кроме начала координат.

1776. Вчера каждый брат был в ссоре с одинаковым количеством сестёр, а каждая сестра — с различным количеством братьев. Сейчас некоторые из них помирились, и каждая сестра в ссоре с одним и тем же количеством братьев, а каждый брат — с различным количеством сестёр. Сколько сестёр и сколько братьев в этой семье?

1777. В квадрат со стороной 1 вписан четырёхугольник. Его стороны являются гипотенузами четырёх прямоугольных треугольников, в каждый из которых вписана окружность. Докажите, что сумма радиусов этих окружностей не превосходит разности числа 2 и числа корень квадратный из 2 и равна этому числу лишь тогда, когда стороны вписанного четырёхугольника параллельны диагоналям квадрата.

1778*. На доске написано комплексное число 1 + i. Разрешено любое число раз и в любом порядке выполнять следующие операции: стереть любое число a + bi и записать взамен

• два раза число a + 1 + bi;
• три числа a + 1 + bi, a + bi + i и a + 1 + bi + i;
• четыре числа, два из которых равны a + bi + i, а два других равны a + 1 + bi + i.

После нескольких таких операций оказалось, что модули всех выписанных чисел больше 3. Докажите, что среди выписанных чисел есть хотя бы два одинаковых.

1779. Найдите все такие многочлены f, что а) для любых чисел x и y верно равенство f (x + y) = f (x) + f (y); б) для любого x и некоторого a верно равенство af(x) = f (2001x); в) для любых чисел x и y и некоторых чисел a, b, c и d верно равенство af(x) + bf(y) = f (cx + dy).

1780*. Каждая точка сферы окрашена в красный или синий цвет. Докажите существование трёх одноцветных точек, являющихся вершинами равностороннего треугольника.

1781. Начальник охраны хочет расставить часовых вокруг лагеря так, чтобы ни к лагерю, ни к часовым нельзя было незаметно подкрасться. У каждого часового есть прожектор, который освещает отрезок длиной 100 метров. Сможет ли начальник исполнить свой замысел?

1782. Для любого натурального числа n существует лишь конечное множество пар натуральных чисел x и y таких, что модуль разности чисел x! и y^y меньше числа n. Докажите это.

1783. В треугольнике ABC проведены высота AH, биссектриса BL и медиана CM. Оказалось, что треугольник HML равносторонний. Докажите, что треугольник ABC равносторонний.

1784*. На доске записаны все целые числа от 1 до 2000. а) Наугад стирают 998 чисел. Докажите, что среди оставшихся чисел можно указать несколько (не менее двух) так, что их сумма тоже имеется на доске. б)* Наугад стирают 89 чисел. Докажите, что среди оставшихся можно указать 20 чисел так, что их сумма тоже имеется на доске. Останутся ли справедливы утверждения, если стереть ещё одно число?

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

а) Каждое княжество представлено на карте острова равносторонним треугольником. Докажите, что для правильной раскраски карты достаточно двух красок.

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

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

1787*. Пусть p и q — натуральные числа, не равные 1. Докажите, что если q³ – 1 делится на p, а p – 1 делится на q, то p = q² + q + 1 или (p – 1)² = q³.

1788. В треугольнике ABC точка I — центр вписанной окружности, A', B' и C' — точки её касания со сторонами BC, CA и AB соответственно. Прямые AA' и BB' пересекаются в точке P, прямые AC и A'C' — в точке M, а BC и B'C' — в точке N. Докажите перпендикулярность прямых IP и MN.

1789. а) Из ста гирек массами 1 г, 2 г, 3 г, ..., 100 г выбраны 50 гирь, сумма масс которых равна сумме масс оставшихся гирь. Массы никаких двух выбранных гирь не отличаются на 50 г. Докажите, что в наборе есть две гири, сумма масс которых равна 101 г.

б) Из двухсот гирек массами 1 г, 2 г, 3 г, ..., 200 г выбраны 100 гирь, сумма масс которых равна сумме масс оставшихся гирь. Массы никаких двух выбранных гирь не отличаются на 100 г и не дают в сумме 201 г. Докажите, что сумма масс 50 самых лёгких выбранных гирек равна 2525 г.

1790. Имеется несколько равносторонних треугольников, у каждого из которых одна сторона жёлтая, другая красная, а третья синяя. Можно прикладывать треугольники друг к другу одноцветными сторонами или участками одноцветных сторон. Таким образом составлен большой равносторонний треугольник. Докажите, что сумма длин жёлтых участков границы полученного равностороннего треугольника равна сумме длин красных участков его границы.

1791. а) На плоскости расположены 5 окружностей, любые четыре из которых имеют общую касательную. Обязательно ли все 5 окружностей имеют общую касательную?

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

1792. В компании из 2n + 1 человек для любых n человек есть отличный от них человек, знакомый со всеми ними. Докажите, что в этой компании есть человек, знакомый со всеми остальными.

1793*. В магическом квадрате размером n×n, составленном из первых n² чисел, центры любых двух его клеток соединили вектором в направлении от большего числа к меньшему. Докажите, что сумма полученных векторов равна нулю. (Магическим называем квадрат, заполненный числами таким образом, что сумма чисел любой его строки равна сумме чисел любого его столбца.)

1794. На прямой выбрано 100 множеств, каждое из которых является объединением 100 отрезков. Докажите, что пересечение этих 100 множеств является объединением не более чем 9901 отрезков. (Точку также считаем отрезком.)

1795. На сфере определена непрерывная функция. Докажите, что некоторое своё значение эта функция принимает на каждой из больших окружностей сферы. (Окружность на сфере называем большой, если её центр совпадает с центром сферы.)

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

1797. Красные и синие точки, чередуясь, делят окружность на 2n дуг. Длины любых двух смежных дуг отличаются на 1. Докажите, что периметр n-угольника с красными вершинами равен периметру n-угольника с синими вершинами.

1798. В некотором городе живут 1000 человек. Из них 300 честные, 700 — хитрые. Хитрые на некоторые вопросы отвечают правдиво, а на некоторые лгут по собственному желанию. Честные всегда говорят правду. Сколько хитрецов можно гарантированно выявить при помощи сколь угодно длинного допроса, если жители знают друг о друге всё?

1799*. Натуральные числа x и y таковы, что число x + y + xy является квадратом натурального числа. Докажите существование такого натурального числа z, что каждая из семи сумм xy + z, yz + x, xz + y, x + z + xz, y + z + yz, xy + yz + zx и xy + yz + zx + x + y + z является квадратом натурального числа.

1800. Сумма квадратов площадей граней любого тетраэдра равна учетверённой сумме квадратов площадей трёх его сечений, каждое из которых проходит через середины рёбер рассматриваемого тетраэдра. Докажите это.