1411. Каждый житель острова Невезения либо всегда говорит правду, либо всегда лжёт, причём правдивых — не менее четверти всех жителей. На выборах президента, в которых участвовали все невезенцы, было только два кандидата: Ёлкин и Палкин. На вопрос наблюдателя ООН «за кого Вы голосовали?» большинство невезенцев ответило: «За Палкина»,— а на вопрос «кто победил?» большинство ответило: «Ёлкин».

а) Кто победил на выборах?

б) Можно ли это наверняка определить, если правдивых на острове — лишь одна пятая всех жителей?

1412. Натуральные числа x и y таковы, что сумма чисел, первое из которых равно (x² – 1)/(y + 1), а второе равно (y² – 1)/(x + 1), является целым числом. Докажите, что каждая из дробей - целое число.

1413. Точка M — середина стороны BC выпуклого четырёхугольника ABCD. Величина угла AMD равна 120°. Докажите неравенство AD £ AB + ^BC ⁄ ₂ + CD.

1414. Существует функция f, определённая на множестве всех неотрицательных чисел и такая, что значение f (f (f (...(x)))), где функция f применена n раз, равно: а) x/(x + 1); б) 1 + x + 2x^1/2. Докажите это.

1415. Дано два правильных 10-угольника. В каждой вершине того и другого написано натуральное число, причём сумма чисел на каждом 10-угольнике равна 99. Докажите, что можно отметить на том и другом 10-угольнике несколько подряд стоящих вершин (может быть, одну, но не все) так, что суммы отмеченных чисел будут одинаковы.

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

1417. На сторонах AC и BC треугольника ABC выбраны точки D и E. Отношение величины угла CDE к величине угла BDE равно отношению величины угла CED к величине угла AFD. Обязательно ли треугольник ABC равнобедренный, если отрезки AE и BD являются а) медианами; б) высотами; в) биссектрисами этого треугольника?

1418. На плоскости задано конечное множество векторов с длинами не больше 1 и суммой S. Докажите, что для любого числа λ между 0 и 1 найдётся некоторое подмножество этих векторов, сумма которых отличается от λS на вектор длиной не больше 1/2^1/2.

1419. Пусть f (x) = xⁿ + 5x^{n – 1} + 3, где n > 1. Докажите, что многочлен f нельзя представить в виде произведения многочленов степени больше 1 с целыми коэффициентами.

1420. Для любых трёх точек P, Q и R плоскости обозначим через m(PQR) наименьшую из высот треугольника PQR. (Если точки лежат на одной прямой, то m(PQR) = 0.) Докажите для любых четырёх точек A, B,C и X плоскости неравенство m(ABC) £ m(ABX) + m(AXC) + m(XBC).

1421. а) В выпуклый четырёхугольник ABCD, у которого углы при вершинах B и D прямые, вписан четырёхугольник с периметром P (его вершины лежат по одной на сторонах четырёхугольника ABCD). Докажите неравенство P > 2BD.

б) В каких случаях это неравенство превращается в равенство?

1422. Числа 312 500 051 и 1280 000 401 — составные. Докажите это.

1423. Три шахматиста A, B и C сыграли матч-турнир (каждый с каждым сыграл одинаковое число партий). Могло ли случиться, что по числу очков A занял первое место, C — последнее, а по числу побед, наоборот, A занял последнее место, C — первое? (За победу присуждают одно очко, за ничью — половину очка.)

1424. В строчку выписано 10 целых чисел. Вторую строку выписываем так: под каждым числом a первой строки пишем число, равное количеству чисел первой строчки, которые больше a и при этом стоят правее a. По второй строке аналогично строим третью и так далее.

а) Докажите, что все строки, начиная с некоторой, нулевые (состоят только из нулей).

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

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

1426. Через S(n) обозначим сумму цифр десятичной записи числа n. Существуют ли такие три различных числа m, n и k, что

1427. В каждой клетке квадрата 8 × 8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть больше а) 15; б) 20?

в) Может ли в аналогичной задаче про квадрат n × n клеток получиться больше чем ⁿ²⁄₄ частей (для n > 8)?

1428. Подряд выписаны десятичные записи всех натуральных чисел, начиная с единицы, до некоторого n включительно: 12345678910111213....(n). Существует ли такое n, что в этой записи все десять цифр встречаются одинаковое количество раз?

1429. Выпуклый многоугольник разрезан на выпуклые семиугольники (так, что каждая сторона многоугольника является стороной одного из семиугольников.) Докажите, что найдутся четыре соседние вершины многоугольника, принадлежащие одному семиугольнику.

1430. Монотонно возрастающая последовательность целых чисел a₁, a₂, a₃,... обладает тем свойством, что для любой пары взаимно простых чисел m и n верно равенство a_mn = a_m · a_n; кроме того, a₁ = 1 и a₂ = 2.

а) Докажите равенство a₃ = 3.

б) Докажите равенство a_n = n для любого натурального n.

Взаимно простыми называют числа, не имеющие общего делителя, большего 1.

1431. С натуральным числом проделываем следующую операцию: его последнюю цифру отделяем, умножаем на 4 и прибавляем к оставшемуся числу (скажем, из 1993 получаем 199 + 4 · 3 = 211). С полученным числом проделываем то же самое, и так далее. Докажите, что если в полученной последовательности встретилось число 1001, то в ней нет ни одного простого числа.

1432. Докажите, что для любой последовательности положительных чисел a₁, a₂, a₃,... целые части квадратных корней из чисел b_n = (a₁ + a₂ + ... + a_n)((1/a₁) + (1/a₂) + ... + (1/a_n)).

1433. ABCD — выпуклый четырёхугольник. На лучах BA и DC отложим отрезки BM и DP длиной (AB + CD)/2. Аналогично, на лучах CB и AD отложим отрезки CN и AQ длиной (BC + AD)/2. Докажите, что MNPQ — прямоугольник, площадь которого равна площади четырёхугольника ABCD.

1434. Пусть Земля плоская. Любой ли выпуклый многогранник можно осветить точечным фонарём из некоторой точки пространства так, что его тень будет многоугольником, хотя бы один угол которого острый?

1435. Докажите, что в любой многочлен P степени больше 1 можно подставить некоторый многочлен Q так, что многочлен P(Q(x)) разлагается на два множителя ненулевой степени. (Коэффициенты всех этих многочленов — целые числа.)

1436. Каков наибольший объём тетраэдра, о котором известно, что длины некоторых а) 4; б) 5; в) всех 6 рёбер не превосходят 1?

1437*. Если первые три члена последовательности — целые неотрицательные числа и если каждый следующий член равен сумме предпредыдущего и предпредпредыдущего, то для любого натурального числа n и для любого простого числа p число a_{n + 3p + 1} – a_{n + p + 1} – a_{n + 1} делится на p.

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

1439. а) Длину каждой медианы треугольника разделим на длину соответствующей стороны и сложим эти отношения. Докажите, что полученная сумма не меньше полутора корней квадратных из 3.

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

1440*. Прямоугольная доска покрыта одинаковыми плитками размера 1×k каждая. Разрешено вынуть любой состоящий из таких плиток квадрат со стороной k и повернуть его на 90°. Докажите, что такими операциями можно добиться того, чтобы направления всех плиток совпали.

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

1442. Две окружности пересекаются в точках A и B. В точке A к обеим проведены касательные, пересекающие окружности в точках M и N. Прямые BM и BN пересекают окружности ещё раз в точках P и Q, причём P лежит на прямой BM, а Q — на BN. Докажите равенство длин отрезков MP и NQ.

1443. Последовательность x₁, x₂, x₃, ... задана числом x₁, принадлежашщим отрезку [0;1], и рекуррентной формулой x_n+1 = 1 – |1 – 2x_n |. а) Последовательность периодическая тогда и только тогда, когда число x₁ рациональное. Докажите это.

б*) Сколько существует для данного натурального числа t таких чисел x₁ отрезка [0;1], что длина наименьшего периода последовательности x₁, x₂, x₃, ... равна t?

1444. Существует ли многочлен P, один из коэффициентов которого отрицателен, а все коэффициенты многочленов P², P³, P⁴, ... положительны?

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

1446. Из выпуклого многогранника с 9 вершинами, одна из которых A, параллельными переносами, переводящими A в каждую из остальных вершин, образованы 8 конгруэнтных многогранников. Докажите, что хотя бы два из этих многогранников имеют общую внутреннюю точку.

1447. В квадрате размером 10×10 нужно расставить один корабль 1×4, два — 1×3, три — 1×2 и четыре — 1×1. Корабли не должны иметь общих точек (даже вершин) друг с другом, но могут прилегать к границам квадрата. Докажите, что если расставлять их в

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

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

1448. а) В любом ли многоугольнике можно провести хорду, которая делит его на две части равной площади?

б) Любой многоугольник можно разделить некоторой хордой на части, площадь каждой из которых не меньше ¹⁄₃ площади многоугольника. Докажите это.

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

1449. Продолжения сторон AB и CD выпуклого четырёхугольника ABCD пересекаются в точке P, а продолжения сторон BC и AD — в точке Q. Докажите, что если каждая из трёх пар биссектрис: внешних углов при вершинах A и C, внешних углов при вершинах B и D, а также внешних углов при вершинах Q и P (треугольников QAB и PBC соответственно) имеет точку пересечения, то эти три точки лежат на одной прямой.

1450. Для любого натурального k > 1 есть такая степень числа 2, что среди k последних цифр её десятичной записи не менее половины составляют девятки. (Например, 2¹² = ...96, 2⁵³ = ...992.)

1451. Натуральные числа a и b таковы, что сумма дробей (a + 1) ⁄ b и (a + 1) ⁄ b целая. Докажите, что квадрат наибольшего общего делителя чисел a и b не превосходит суммы a + b.

1452. Окружности ω₁ и ω₂ касаются внешним образом в точке F. Их общая касательная касается ω₁ и ω₂ в точках A и B соответственно. Прямая, параллельная AB, касается окружности ω₂ в точке C и пересекает окружность ω₁ в точках D и E. Докажите, что а) точки A, F и C лежат на одной прямой; б) общая хорда окружностей, описанных около треугольников ABC и BDE, проходит через точку F.

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

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

1455. В вершинах выпуклого n-угольника расставлены более чем n фишек. За один ход разрешено передвинуть две фишки, стоящие в одной вершине, в соседние вершины: одну вправо, другую влево. После m ходов в каждой вершине n-угольника оказалось столько же фишек, сколько было вначале. Докажите, что m делится на n.

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

1457. Высоты AA', BB', CC' и DD' тетраэдра ABCD пересекаются в центре H вписанной сферы тетраэдра A'B'C'D'. Докажите, что тетраэдр ABCD правильный.

1458. В правильном (6n + 1)-угольнике k вершин покрашены в красный цвет, а остальные — в синий. Докажите, что количество равнобедренных треугольников с одноцветными вершинами не зависит от способа раскраски.

1459. Петя и Витя по очереди ходят конём на доске размером 1994×1994. Петя может делать только «горизонтальные» ходы, то есть такие, при которых конь перемещается на соседнюю горизонталь. Вите разрешены только «вертикальные» ходы, то есть такие, при которых конь перемещается на соседнюю вертикаль. Петя ставит коня на поле, с которого начинается игра, и делает первый ход. И Вите, и Пете запрещено ставить коня на поле, где конь уже побывал в данной игре. Проигравшим считают игрока, который не может сделать ход. Докажите, что для Пети существует выигрышная стратегия.

1460. В клетках бесконечного листа клетчатой бумаги записаны вещественные числа. Рассматриваем две фигуры, каждая из которых состоит из конечного числа клеток. Фигуры можно перемещать параллельно линиям сетки на целое число клеток. Известно, что для любого положения первой фигуры сумма чисел, записанных в накрываемых ею клетках, положительна. Докажите, что существует положение второй фигуры, при котором сумма чисел в накрытых ею клетках положительна.

1461. Профессор Тарантого дал n определений сепульки. Аспиранты профессора постепенно доказали равносильность всех этих определений. Каждый из аспирантов защитил диссертацию на тему: «Сепулька в смысле j-го определения является сепулькой в смысле k-го определения.» Какое максимальное количество аспирантов могло быть у Тарантоги, если диссертации защищали последовательно и основной результат любой очередной диссертации не следовал из ранее защищённых?

1462. Для любого натурального n > 1 квадрат корня n-й степени из n! не меньше произведения корня (n + 1)-й степени из (n – 1)! на корень (n – 1)-й степени из (n + 1)!. Докажите это.

1463. Существуют ли такие натуральные числа x и y, что каждое из чисел а) x + y, 2x + y и x + 2y; б) x + y, 2x + y и x + 3y является квадратом натурального числа?

1464. R и r — радиусы описанной и вписанной окружностей треугольника; ρ — радиус окружности, вписанной в треугольник с вершинами в точках касания вписанной окружности со сторонами треугольника. Докажите, что 2ρ не больше r, а r² не превосходит Rρ.

1465. P, Q, R — многочлены, причём степени многочленов P и Q различны и положительны. а) Докажите, что ни для какого натурального числа k не существует более одного многочлена f степени k со старшим коэффициентом 1 такого, что f (P(x))f (Q(x)) = f (R(x)).

б) Найдите хотя бы один такой непостоянный многочлен f, что f (x)f (2x²) = f (2x³ + x).

в) Найдите все такие многочлены.

1466. Играют два художника. Первый рисует на плоскости (первоначально пустой) один за другим многоугольники, не имеющие общих внутренних точек, а второй последовательно красит их так, чтобы многоугольники, имеющие хотя бы один общий отрезок, были разного цвета. Может ли первый художник заставить второго использовать более а) пяти; б) десяти цветов?

1467. a₁ < a₂ < ... < a_m £ n — такие натуральные числа, что любая сумма вида a_r + a_s, где 1 £ r £ s £ n, либо больше n, либо принадлежит множеству {a₁, a₂, ..., a_n}. Докажите, что среднее арифметическое чисел a₁ < a₂ < ... < a_m не меньше половины числа n + 1.

1468. ABC — треугольник; AB = AC; M — середина отрезка BC; O — такая точка прямой AM, что угол OBA прямой; Q — внутренняя точка отрезка BC; точки E и F лежат на прямых AB и AC соответственно; точки E, Q и F различны и лежат на одной прямой. Докажите, что отрезок OQ перпендикулярен EF тогда и только тогда, когда EQ = QF.

1469. Для любого натурального числа k обозначим через f (k) количество элементов множества { k, k + 1, . . . , 2k }, двоичная запись которых содержит ровно три единицы.

а) Докажите, что для любого натурального числа m существует такое k, что m = f (k).

б) Для каких m такое k единственно?

1470*. Докажите существование такого множества A натуральных чисел, что для любого бесконечного множества S простых чисел существует такое k > 1, что в виде произведения k различных элементов множества S представим как некоторый элемент множества A, так и некоторое натуральное число, не принадлежащее множеству A.