5*. В множестве E, состоящем из n элементов, выделены m различных подмножеств (отличных от самого E) так, что для любых двух элементов множества E существует единственное выделенное подмножество, содержащее оба элемента. Докажите неравенство m ³ n.

6. Перед вами часы. Сколько существует положений стрелок, по которым нельзя определить время, если не знать, какая стрелка часовая, а какая — минутная? (Положения стрелок можно определить точно, но следить за движением стрелок нельзя.)

7. a, b, c — длины сторон треугольника. Докажите, что сумма чисел ^a⁄_{(b + c – a)}, ^b⁄_{(c + a – b)} и ^c⁄_{(a + b – c)} больше или равна 3.

8. Двое играют в такую игру. Из кучки, где имеется 25 спичек, каждый берёт себе по очереди одну, две или три спички. Выигрывает тот, у кого в конце игры — после того, как все спички будут разобраны,— окажется чётное число спичек. Кто выигрывает при правильной игре — начинающий или его партнёр? Как он должен играть, чтобы выиграть? Как изменится ответ, если считать, что выигрывает забравший нечётное число спичек?

Исследуйте эту игру в общем случае, когда спичек 2n + 1 и разрешено брать любое число спичек от 1 до m.

9. Рассмотрим следующие свойства тетраэдра (тетраэдр — это произвольная треугольная пирамида):

1. все грани одной площади;
2. каждое ребро равно противоположному;
3. все грани конгруэнтны;
4. центры описанной и вписанной сфер совпадают;
5. для любой вершины тетраэдра сумма величин сходящихся в этой вершине плоских углов равна 180°.

Докажите, что все эти свойства эквивалентны. Найдите ещё два-три эквивалентных им свойства.

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

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

б) А если чижей и деревьев n?

12. Какие четырёхугольники можно разрезать прямой линией на два подобных между собой четырёхугольника?

13. Если разность между наибольшим и наименьшим из n данных вещественных чисел равна d, а сумма модулей всех n(n – 1) ⁄ 2 попарных разностей этих чисел равна s, то (n – 1)d £ s £ n²d ⁄ 4. Докажите это.

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

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

16. Многочлен с целыми коэффициентами, который при трёх различных целых значениях переменной принимает значение 1, не может иметь ни одного целого корня. Докажите это.

17. Крестьянин, подойдя к развилке двух дорог, расходящихся под углом 60°, спросил: «Как пройти в село NN?» Ему ответили: «Иди по левой дороге до деревни N — это в восьми верстах отсюда,— там увидишь, что направо под прямым углом отходит большая ровная дорога,— это как раз дорога в NN. А можешь идти другим путём: сейчас по правой дороге; как выйдешь к железной дороге,— значит, половину пути прошёл; тут поверни налево и иди прямо по шпалам до самого NN.» —«Ну, а какой путь короче-то будет?» —«Да всё равно, что так, что этак, никакой разницы». И пошёл крестьянин по правой дороге.

Сколько вёрст ему придётся идти до NN? Больше десяти или меньше? А если идти от развилки до NN напрямик? (Все дороги прямые.)

18. а) Для любой точки М описанной около правильного треугольника АВС окружности длина одного из отрезков МА, МВ и МС равна сумме длин двух других. Докажите это.

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

19. В бесконечной цепочке нервных клеток каждая может находиться в одном из двух состояний: «покой» и «возбуждение». Если в данный момент клетка возбудилась, то она посылает сигнал, который через единицу времени (скажем, через одну миллисекунду) доходит до обеих соседних с ней клеток. Каждая клетка возбуждается в том и только в том случае, если к ней приходит сигнал от одной из соседних клеток; если сигналы приходят одновременно с двух сторон, то они погашаются, и клетка не возбуждается. Например, если в начальной момент времени возбудить три соседние клетки, а остальные оставить в покое, то возбуждение будет распространяться так, как показано на рисунке.

а) Пусть в начальный момент времени возбуждена только одна клетка. Сколько клеток будет находится в возбужденном состоянии через 15 мсек? через 65 мсек? через 1000 мсек? вообще через t мсек?

б) Что будет в том случае, если цепочка не бесконечная, а состоит из N клеток, соединённых в окружность,— будет ли возбуждение поддерживаться бесконечно долго или затухнет?

20. Разбейте правильный треугольник на миллион многоугольников так, чтобы никакая прямая не пересекала более сорока них. (Прямая пересекает многоугольник, если она имеет с ним хотя бы одну общую точку.)

21. Внутри квадрата со стороной 1 расположено несколько окружностей, сумма длин которых равна 10. Докажите существование прямой, пересекающей по крайней мере четыре из этих окружностей.

22. а) В угол вписаны две окружности; у них есть общая внутренняя касательная Т₁Т₂ (где Т₁ и Т₂ — точки касания), пересекающая стороны угла в точках А₁ и А₂. Докажите равенство А₁Т₁ = А₂Т₂ (или, что эквивалентно, А₁Т₂ = А₂Т₁).

б) В угол вписаны две окружности, одна из которых касается сторон угла в точках K₁ и K₂, другая — в точках L₁ и L₂. Докажите, что прямая К₁L₂ высекает на окружностях хорды равной длины.

23. Для любого натурального числа n, большего единицы, квадрат отношения произведения первых n чётных чисел к произведению первых n нечётных чисел больше числа ⁸ⁿ⁄₃, но меньше числа 4n. Докажите это.

24. Любую дробь ^m⁄_n, где m, n — натуральные числа, 1 < m < n, можно представить в виде суммы нескольких дробей вида ¹⁄_q, причём таких, что знаменатель каждой следующей из этих дробей делится на знаменатель предыдущей дроби. Докажите это. (Например, дробь ³⁄₄₃ является суммой дробей ¹⁄₁₅, ¹⁄₃₃₀ и ¹⁄_14 190.)

25. В множестве, состоящем из n элементов, выбрано 2^{n – 1} подмножеств, каждые три из которых имеют общий элемент. Докажите, что все эти подмножества имеют общий элемент.

26. Предположим, что в каждом номере задачника «Кванта» будет пять задач по математике. Обозначим через f (x, y) номер первой из задач x-го номера за y-й год. Напишите общую формулу для f (x, y), где 1 £ x £ 12 и 1970 £ x £ 1989. Решите уравнение f (x, y) = y.

Например, f (6, 1970) = 26. Начиная с 1990 года, количество задач стало менее предсказуемым. Например, несколько лет подряд в половине номеров было по 5 задач, а в других номерах по 10; с 2009 года практика ещё раз изменилась: в некоторых номерах 7 задач, а в некоторых — 8. Да и самих номеров журнала сейчас уже не 12, а 6. Задачник четвёртого номера 2006 года начинается с задачи М2006.

27. Если сумма дробей ^a⁄_{(b – c)}, ^b⁄_{(c – a)} и ^c⁄_{(a – b)} равна 0, то сумма дробей ^a⁄_{(b – c)²}, ^b⁄_{(c – a)²} и ^c⁄_{(a – b)²} тоже равна 0. Докажите это.

28*. а) Из 19 шаров 2 радиоактивны. Про любую кучку шаров за одну проверку можно узнать, есть в ней хотя бы один радиоактивный шар или нет, но нельзя узнать, сколько таких шаров в кучке. Докажите, что за 8 проверок можно выделить оба радиоактивных шара.

б) Из 11 шаров 2 радиоактивны. Докажите, что менее чем за 7 проверок нельзя гарантировать выделение обоих радиоактивных шаров.

29. На столе лежат n одинаковых монет, образуя замкнутую цепочку. Центры монет образуют выпуклый многоугольник. Сколько оборотов сделает монета такого же размера за время, пока она один раз прокатится по внешней стороне всей цепочки, как показано на рисунке?

Как изменится ответ, если радиус этой монеты в k раз больше радиуса каждой из монет цепочки?

30. Любую конечную систему точек плоскости можно покрыть несколькими непересекающимися кругами, сумма диаметров которых меньше количества точек и расстояние между любыми двумя из которых больше 1. Докажите это. (Расстояние между двумя кругами — это расстояние между их ближайшими точками.)

31. Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов нужно сделать, чтобы среди полученных частей могло оказаться ровно 100 двадцатиугольников?

32. Во всех клетках таблицы размером 100×100 стоят плюсы. Разрешено одновременно изменить знаки во всех клетках одной строки или во всех клетках одного столбца. Можно ли, проделав такие операции несколько раз, получить таблицу, где ровно 1970 минусов?

33*. Рассмотрим натуральное число n > 1000. Найдём остатки от деления числа 2ⁿ на числа 1, 2, 3, ..., n и сложим все эти остатки. Докажите, что сумма больше 2n.

34. Если натуральное число делится на 10 101 010 101, то по крайней мере шесть цифр его десятичной записи отличны от нуля. Докажите это.

35*. Около сферы с радиусом 10 описан некоторый 19-гранник. Докажите, что на его поверхности есть две точки, расстояние между которыми больше 21.

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

37*. В каждую клетку бесконечного листа клетчатой бумаги вписано некоторое число так, что сумма чисел в любом квадрате, стороны которого идут по линиям сетки, по модулю не превосходит единицы. а) Докажите существование такого числа c, что сумма чисел в любом прямоугольнике, стороны которого идут по линиям сетки, не больше c; другими словами, докажите, что суммы чисел в прямоугольниках ограничены.

б) Докажите, что можно взять c = 4.

в) Улучшите эту оценку — докажите, что утверждение верно для c = 3.

г) Постройте пример, показывающий, что при c < 3 утверждение неверно.

38. Окружность, построенная на высоте АD прямоугольного треугольника АВС как на диаметре, пересекает катет АВ в точке K, а катет АС — в точке М. Отрезок KМ пересекает высоту АD в точке L. Длины отрезков АK, АL и AM составляют геометрическую прогрессию (то есть AK/AL = AL/AM). Найдите величины острых углов треугольника АВС.

39*. Пусть m — натуральное число, m > 1. Целые неотрицательные числа x и y удовлетворяют равенству

Этот красивый факт был использован в работе Ю.В. Матиясевича, посвящённой десятой проблеме Д. Гильберта, о которой рассказано в седьмом номере «Кванта» за 1970 год.

40. а) Найдите сумму 1 · n + 2 · (n – 1) + 3 · (n – 2) + ... + n · 1.

б) Решите следующую, более общую задачу: найдите величину S_n,k, являющуюся суммой n – k + 1 слагаемых, m-е из которых равно произведению произведения чисел от m до k + m – 1 и произведения чисел от n – k + 2 – m до n + 1 – m.

41. Дана окружность, её диаметр AB и точка C на этом диаметре. Постройте на окружности две точки X и Y, симметричные относительно диаметра АВ, для которых прямая YC перпендикулярна прямой ХА.

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

43. Каждая сторона равностороннего треугольника разбита на n равных частей. Через точки деления проведены прямые, параллельные сторонам. В результате треугольник разбит на n² треугольничков. Каково наибольшее возможное количество треугольничков в цепочке, в которой ни один треугольничек не появляется дважды и каждый последующий имеет общую сторону с предыдущим?

44. Для любого натурального числа k существует бесконечно много натуральных чисел t, не содержащих в десятичной записи нулей и таких, что сумма цифр числа kt равна сумме цифр числа t. Докажите это.

45*. а) Из любых двухсот целых чисел можно выбрать сто чисел, сумма которых делится на 100. Докажите это.

б) Из любых 2n – 1 целых чисел можно выбрать n, сумма которых делится на n. Докажите это.

46. Сколько в выпуклом многоугольнике может быть сторон, равных наибольшей диагонали?

47. Из цифр 1 и 2 составили пять n-значных чисел так, что у каждых двух чисел совпали цифры ровно в m разрядах, но ни в одном разряде не совпали все пять чисел. Докажите, что отношение ^m⁄_n не меньше ²⁄₅ и не больше ³⁄₅.

48. Биссектриса AD, медиана BM и высота CH остроугольного треугольника ABC пересекаются в одной точке. Докажите, что величина угла BAC больше 45°.

49. На карточках написали все числа от 11 111 до 99 999 включительно и выложили эти карточки в цепочку в произвольном порядке. Докажите, что полученное 444 445-значное число не является степенью двойки.

50*. Вершины правильного n-угольника покрашены несколькими красками (каждая — одной краской) так, что точки одного и того же цвета служат вершинами правильного многоугольника. Докажите, что среди этих многоугольников есть два конгруэнтных.

51. Если произведение трёх положительных чисел равно 1, а сумма этих чисел больше суммы их обратных величин, то ровно одно из этих чисел больше 1. Докажите это.

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

53. В треугольнике АВС через середину М стороны ВС и центр О вписанной в этот треугольник окружности проведена прямая МО, пересекающая высоту АН в точке Е. Докажите, что отрезок АЕ равен радиусу вписанной окружности.

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

55. Множество всех натуральных чисел, в десятичных записях которых не больше n цифр, разбили на два подмножества следующим образом. В первое входят числа с нечётной суммой цифр, а во второе — c чётной. Докажите, что для любого натурального числа k £ n сумма k-х степеней всех чисел первого подмножества равна сумме k-х степеней всех чисел второго подмножества.

56. На окружности выписаны в произвольном порядке четыре единицы и пять нулей. В промежутке между двумя одинаковыми числами пишем нуль, между разными цифрами — единицу, а после этого первоначальные цифры стираем. Докажите, что сколько бы раз мы ни повтoрили этот процесс, мы никогда не получим набор из девяти нулей.

57. a) Найдите число, которое делится на 2 и на 9 и имеет всего 14 делителей (включая 1 и само число).

б) Докажите, что если заменить 14 на 15, то таких чисел несколько, а если на 17 — ни одного.

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

59. При каких n гири массами 1 г, 2 г, 3 г, ..., n г можно разложить на три равные по массе кучки?

60. Рассмотрим все натуральные числа, в десятичной записи которых участвуют лишь цифры 1 и 0. Разбейте эти числа на два непересекающихся подмножества так, чтобы сумма любых двух различных чисел из одного и того же подмножества содержала в своей десятичной записи не менее двух единиц.