Составители: С.Л.Берлов, С.В.Иванов, К.П.Кохась
e-mail:
kpk@kkl437.spb.edu
svivaiiov@pdmi .ras.ru
СОДЕРЖАНИЕ
Победители олимпиады 1998 года 2
Статистические данные олимпиады 1998 года 5
Задачи первого тура, 6-11 классы 6
Задачи второго тура, 6-11 классы 10
Задачи отборочного тура, 9-11 классы 16
Задачи олимпиады ФМЛ №239 19
Ответы, указания, решения 21
Данное издание выполнено при поддержке ФЦП "Интеграция",
per. номер 326.53

Санкт-Петербургский государственный университет
ЗАДАЧИ САНКТ-ПЕТЕРБУРГСКОЙ
ОЛИМПИАДЫ ШКОЛЬНИКОВ ПО МАТЕМАТИКЕ
В этом году прошла 64-я городская олимпиада школьников
по математике. Первый тур проходил 25 января, в нем
приняло участие более 10 тысяч школьников Санкт-Петербурга.
Победители первого тура, а также победители городской
олимпиады прошлого года были приглашены на второй тур. Для 6-8
классов второй тур олимпиады проходил 15 февраля на
математическом факультете РГПУ, для 9-11 классов - 1 марта на
математико-механическом факультете СПбГУ. Наконец, 15
марта в помещении Физико-математического лицея №239 прошел
отборочный тур, предназначенный для формирования команды
города на Всероссийскую олимпиаду.
На решение задач отводилось следующее время: первый тур -
3 часа, второй тур (во всех классах, кроме шестого) - 3 часа
в довыводных аудиториях плюс еще один час для участников,
решивших не менее трех "довыводных" задач (из первых четырех
задач варианта). В шестом классе - соответственно 2.5 и 3.5 часа.
На решение задач отборочного тура было дано 5 часов.
В этом году в составлении вариантов олимпиады
участвовали: Ю.М.Базлов, С.Л.Берлов, А.С.Голованов, М.Н.Гусаров,
С.В.Иванов, Р.А.Исмаилов, Д.В.Карпов, К.П.Кохась, О.Г.Мале-
ва, А.В.Пастор, М.Я.Пратусевич, Р.А.Семизаров, А.И.Храбров.
Много сил в организацию олимпиады вложили Л.А.Жигулев,
В.В.Крылов. Проведение олимпиады также было бы невозможно
без помощи многочисленных энтузиастов: студентов/учителей и
преподавателей вузов, вложивших свой труд в проведение всех
туров олимпиады.
Финансовую поддержку олимпиаде оказал Ю.О.Латов, на
средства гранта ФЦП "Интеграция" изготовлены призы для
победителей олимпиады - футболки с символикой олимпиады
(фирма "Appli", ул. Блохина д. б, тел. 233-12-52).
-1-

ПОБЕДИТЕЛИ ОЛИМПИАДЫ 1998 ГОДА
16КЛАСС1
1 диплом Аверьянов Петр
Антипов Дмитрий
Дворкин Михаил
Зинченко Дмитрий
2 диплом
Школа
105
261
582
30
Район
Выб.
Кир.
Прим.
Антонов Сергей 76 Выб.
Белокопытов Артем 366 Моск.
Вальтман Виталий 610 Петр.
Гравин Николай 366 Моск.
Гутов Дмитрий 489 Моск.
Иванов Александр 30
Назаров Максим 238 Адмир.
Синев Игорь 468 Выб.
Солодуха Иван 344 Нев.
Чихачев Кирилл 166 Центр.
3 диплом
Артеменко Николай 30
Груздев Михаил 205
Дубашинский Мих. 527
Железнов Дмитрий 43
Смирнов Александр 596
Храбрый Александр 636
Семенов Вадим 73 Выб.
Фрунз. Сикулер Ярослав 41 Прим.
Нев. Кузнецов Антон 144 Калин.
Прим. Струкова Ольга 159 Калин,
Прим. Преснова Алена 261 Кир.
Центр. Ширяев Дмитрий 207 Центр.
17 КЛАСС
1 диплом Антипов Дмитрий 261 Кир.
2 диплом Захарова Виктория 642 В.О.
Панферов Василий 1
Сухов Кирилл 470 Калин.
3 диплом
V
Власов Всеволод
Клименко Виктор
Новицкий Михаил
Филиппов Вячеслав
642АГ В.О.
187 Кргв.
52 Прим.
98 Калин.
-2-

Похвальный отзыв 1-й степени
Белянцев Алексей 196 Кргв.
Иваньков Никита 366 Моск.
Иванова Вера 580 Прим.
Мухина Ольга 66 Прим.
Руцкий Дмитрий 30
Смирнов Кирилл
Тирских Юлия
Хитров Виталий
Цыбанев Максим
38 Прим.
30
30
147 Кргв.
18КЛАСС1
1 диплом
2 диплом
3 диплом
Смирнов Филипп 239
Варягин Андрей 239
Me двинский Михаил 366
Бондарева Елена 239
Мясников Родион 239
Привалов Игорь 239
Моск.
Похвальный отзыв 1-й степени
Васильев Антон 30
Воробьев Андрей 239
Ефремов Алексей 239
Назаров Антон 239
Оршанский Сергей 239
Паперно Денис 642 В.О.
19 КЛАСС!
1 диплом
2 диплом
Смирнов Филипп
Сафарова Юлия 239
Сергеева Ольга 239
Солощева Елена 239
Трофимов Вадим 292
Чашников Николай 239
Эфроимский Борис 239
239
Фр.
3 диплом
Ваганов Никита
Лифшиц Юрий
Me двинский Михаил
Тихомиров Сергей
Федотов Алексей
Грибов Александр
Ицыксон Дмитрий
Крысталь Борис
Незлобии Александр
Привалов Игорь
Пчелинцева Ирина
239
239
366
239
239
239
239
239
ФТШ
239
98
Моск.
Калин.
-3-

110 КЛАСС!
1 диплом
2 диплом
3 диплом
Петров Федор
Назаров Александр
Проскурников Антон
Ушаков Егор
Фару тин Александр
Ананьевский Михаил
Буртный Павел
Кургузов Леонид
239
г. Нарва
239
239
G10 Петр
АЛ
239
239
11 КЛАСС
1 диплом
2 диплом
(4-5 место)
2 диплом
(6-13 место)
Беленький Алексей 239
Дуров Николай 239
Розенберг Антон 419
Барыгин Илья ФТШ
Етеревский Олег 239
Бахарев Федор 239
Белов Юрий 239
Егоров Арсений 30
Зильбербург Константин 239
Машевский Александр 239
Мельник Сергей 239
Сопкина Екатерина 239
Франк Владислав 239
П/дв.
3 диплом Железняк Александр 239
Короткевич Алексей АЛ
Левина Анна 239
Лопатин Андрей 238
Малкин Юрий 30
Мнев Павел 610
Мясников Андрей 239
Адм.
Петр.
-4-

СТАТИСТИЧЕСКИЕ ДАННЫЕ ОЛИМПИАДЫ 1998 ГОДА
Критерий пропуска на второй тур олимпиады
к л ас* с
число задач
гт~
| 2.5
7
3
8
3
9
4-
10
3-
11 1
з 1
второй тур
В левой таблице по каждой задаче приведено количество
решивших ее участников; такжо указано общее количество
приглашенных на олимпиаду и количество прошедших в выводную
аудиторию. В правой таблице указано количество участников,
решивших данное число задач.
Номер задачи Всего Вывод Количество задач
G кл.
7 кл.
8 кл.
9 кл.
10 кл.
11 кл.
1
^89
70
31
'5G
39
G8
2
79
29
39
32
24
49
3
56
14
27
17
23
47
4
20
9
17
33
20
21
5
17
3
1
6
5
18
G
12
6
3
1
2
11
7
^П
10
1
1
0
з 1
107
95
97
84
74
G0
39
18
26
21
106 36
1
Il5
35
31
21
12
|21
2
18
2Q
12
13
12
24
3
31
9
12
14
13
16
4
11
4
3
6
3
7
5
10
3
2
5
4
8
6
4
1
1
1
1
2
7
11
0
0
0
0
3 |
отборочный тур
Номер задачи
9 кл.
10 кл. |
11 кл.
1
21
12
10
2
9
10
9
3
15
4
6
4
9
5
10
5
7
5
4
6
3
2
8
7
2
1
2
8
7Л
0
lj
25
17
14
Количество задач
1 2 3 4 5 6 7
пг
6
[з
4
3
2
7
1
1
4
3
3
3
1
3
0
0
1
0
1
1
"о]
0
о]

ЗАДАЧИ ПЕРВОГО ТУРА, 6-11 КЛАССЫ
В квадратных скобках помещены сведения о втором
варианте. Все задачи давались на олимпиаде без рисунков. Рисунки
добавлены для удобства читателя.
6 КЛАСС
1. Расставьте крестики и нолики в квадрате 5x5 клеток так,
чтобы в каждой строке, кроме, быть может, первой, крестиков
было бы больше, чем ноликов, а в каждом столбце кроме, быть
может, последнего, ноликов было бы больше, чем крестиков [в
каждом столбце, кроме, быть может, первого, крестиков было
бы больше, чем ноликов, а в каждой строке, кроме, быть может,
последней, ноликов было бы больше,
чем крестиков]. (Ю. Баллов)
2. Винни-Пух, Сова, Кролик и
Пятачок съели 70 бананов [85 желудей],
причем каждому досталось хотя бы
по одному банану [желудю]. Винни-
Пух [Пятачок] съел больше, чем
катти ^«гтьмцр •ЧГЧ|ГИ! ждый из остальных; Сова и Кролик
•♦^■*~lrjA5^f=i' ~* - '** вместе съели 45 бананов [55 желудей].
Сколько бананов [желудей] съел
Пятачок [Винни-Пух]? (К Кохась)
3. На доске написано число 23 [81]. Каждую минуту число
стирают с доски и записывают на его место произведение его
цифр, увеличенное на 12 [г5]. Что окажется на доске через час?
Не забудьте обосновать ответ. (А. Голованов)
4. Можно ли в квадрате 10 х 10 клеток так расставить
натуральные числа, чтобы при любом расположении фигурки вида
j-j-j-J Ш сумма чисел в ее пяти клетках была равна 105 [155],
а в каждой фигуре вида СП или Ц сумма чисел была равна 40
[60]? Не забудьте обосновать ответ. (О. Малева)
7 КЛАСС
5. Как разрезать квадрат со стороной 4 [3] см на
прямоугольники, сумма периметров которых равна 25 [19] см?
(Ю. Базлов, Р. Семизаров)
-6-

6. Можно ли так расставить по кругу все целые числа от —7
до 7 [от —9 до 9] (включая нуль), чтобы у каждого числа
произвел дснис двух ого соседей было неотрицательным? Если да
приведите пример, если нет объясните, почему. (К). Базлов)
7. На складе стеклотары могут храниться банки из-под
консервированных овощей по 0.5 л, 0.7 л и 1 л. Сейчас на складе
имеется 2500 [2600] банок общей вместимостью 1998 л.
Докажите, что на складе есть хотя бы одна поллитровая банка.
(А. Храброе)
8. Докажите, что в любом шестидесятизначном [пятидесяти-
значном] числе, десятичная запись которого не содержит нулей,
можно зачеркнуть несколько цифр так. что получившееся в
результате этого число будет делиться на 1001 [101]. (Жюри)
8 КЛАСС
9. Можно ли подобрать такие четыре различных
натуральных числа, чтобы сумма любых двух из них была степенью
числа 5 [3]? (С. Берлов)
10. См. задачу 7.
11. AF - медиана треугольника ABC. D -
середина отрезка AF, E точка пересечения
прямой CD со стороной АВ. Оказалось, что
BD = BF = CF. Докажите, что АЕ = DE.
[AF медиана треугольника ABC. На про- А
должении стороны АВ за точку В отмече- six,
на точка D, Е - точка пересечения пря- sT \J?
мой DF со стороной АС. Оказалось, что ^/^^1^^\
AB = BD = AF. Докажите, что СЕ = EF.) jC^^^k
{С. Берлов) С^ ^^D
12. Из прямоугольника на клетчатой бумаге можно вырезать
(по клеточкам) 360 квадратов 2x2. Докажите, что из него можно
вырезать 200 [280] прямоугольников 1 х 7 [1 х 5]. (А. Голованов)
9 класс
13. Найдите наименьшее положительное число я,
удовлетворяющее неравенству [.г] • {л} ^ 3 [ [х] {х} ^ 4 ]. Как обычно,
[х] обозначает целую часть х, {х} = х — [х] - дробная часть х.
(А. Храброе)
А
-7-

14. Сумма четырех корней квадратных трехчленов / и д с
одинаковыми старшими коэффициентами равна нулю. Трехчлен
/ -+•■</ имеет два корня. Докажите, что сумма этих корней
также равна нулю. [/ и д - квадратные трехчлены с одинаковыми
старшими коэффициентами, имеющие по два корня. Сумма двух
корней трехчлена / -+• д равна нулю. Докажите, что сумма всех
четырех корней трехчленов / и д равна нулю.] (С. Берлов)
15. Из множества натуральных чисел от 1 до 1000 [500]
выбрано 860 [430] чисел. Докажите, что произведение каких-то двух из
них делится на 21 [35]. (С. Берлов)
16. Точки Л" и L на сторонах АВ и
АС остроугольного треугольника ABC
таковы, что KL || ВС. М - точка
пересечения перпендикуляров, восставленных в
точках Л' и L к отрезкам АВ и АС. Докажите,
что .4, М и центр О описанной окружности
треугольника ABC лежат на одной прямой.
[А' - точка пересечения перпендикуляров,
восставленных в вершинах А и С
остроугольного треугольника ABC к отрезкам АВ
и ВС. На сторонах АВ и ВС взяты точки L
и М так, что LM || АС. Докажите, что точки
В, К и центр О описанной окружности
треугольника BLM лежат на одной прямой.]
(А. Храброе)
17. В клетках таблицы 100 х 100 расставлены числа. Известно,
что в каждой строке можно выбрать не менее 10 различных чисел,
а из любых двух соседних строк нельзя выбрать больше 15 [16]
различных чисел. Докажите, что в таблице всего не более 505
[604] различных чисел. (С. Иванов)
10 КЛАСС
18. Положительное число х удовлетворяет неравенству
И2 - х[х] + 3 < 0 [ [х]2 - х[х] + 4 < 0 ] .
Докажите, что х ^ 4.75 [5.8]. Как обычно, [х] обозначает целую
часть числа х. (А. Храброе)
19. В Клубе Любителей Вкусной Еды состоят 58 человек [62
человека], причем каждый из них - либо толстый, либо тонкий.

На очередное» заседание каждый толстый член клуба принес 15
пончиков и раздал их тонким, а каждый тонкий принес 14 [16]
пончиков и раздал их толстым. Оказалось, что все толстые
члены клуба получили поровну пончиков и все тонкие - тоже.
Сколько среди членов клуба толстых и сколько тонких? Приведите все
возможные ответы и докажите, что других нет. (А. Голованов)
20. Две дробно-линейные функции /(;/;) и д(х) таковы, что
/(«''') ~ у(х) > 1^97 [/(.г) + у(х) < 1997] для всех ж, при
которых обе функции определены. Докажите, что функция f(x) — д(х)
[f(x) + У(х)] постоянна на своей области определения
(напомним, что дробно-линейной функцией называется частное двух
линейных функций). (А. Голованов)
21. В выпуклом четырёхугольнике ABCD
диагонали АС и BD равны. Кроме того,
ABAC = /ADB, /.CAD + /ADC = /ABD
[/.ВАС = /CBD, /CAB+/CBA = /ADB].
Найдите /BAD. (А. Пастор)
22. В клетках таблицы 100 х 100
расставлены числа. Известно, что в каждой
строке можно выбрать не менее 10 различных
чисел, а в любых трех подряд идущих строках имеется не больше
16 [15] различных чисел. Докажите, что в таблице всего не более
310 [260] различных чисел. (С. Иванов)
11 КЛАСС
23. Положительное число х удовлетворяет неравенству
lg[*] + lg{*}>3[2]
Докажите, что х > 1001.998 [101.98]. Как обычно, [х] обозначает
целую часть числа #, {х} = х — [х] обозначает дробную часть х.
(А. Храброе)
24. Арифметическая прогрессия состоит из натуральных
чисел и содержит бесконечно много чисел вида (2п)! [(2п + 1)!].
Докажите, что первый член прогрессии делится на ее разность.
Выражение п\ обозначает произведение всех натуральных чисел
от 1 до п. (А. Голованов)
„9-

25. Докажите, что в любом тридцатипятизначном числе без
нулей и пятерок в десятичной записи [пятидесятизначном числе
без нулей] можно вычеркнуть несколько цифр так, чтобы
полученное в результате этого число делилось на 41 [271]. (Жюри)
26. Костя взял многочлен f(x) с вещественными
коэффициентами и стал решать уравнение /(./:) = 10 [1G]. У этого уравнения
оказалось 10 [11] различных вещественных корней. А у уравнения
f(x) — 15 [11] оказалось 15 [1G] различных вещественных корней.
Докажите, что среди 25 [27] найденных Костей чисел хотя бы
одно удовлетворяет уравнению f(x) = 0. (К, Кохась)
27. На ребрах АД ВС, CCL, С1Д, А{Вг, AA{ куба
ABCDA\B\C\D\ выбраны точки Р, Q, J?, S, Т, U соответственно.
Оказалось, что при этом
/PQB = /RQC, /RSC{ = /TSDU /TUA{ = /PUA,
/QRC = /.SBC i, /STB{ = /UTAi, /UP A = /QPD.
Найдите длину замкнутой ломаной PQRSTUP, если длина ребра
куба равна 1.
[На ребрах АД DC, ССи ВВ{, A{BV, A{D{ куба ABCDAiBiC\ Д
выбраны точки Р, Q, i?, S, Т, U соответственно. Оказалось, что
/PQD = /RQC, /RSB = /TSB{, /TUAX = ZPt/Д,
/дЛС = Z5i?d, /STB{ = ZC/TAi, /U PA = ZQPD.
Найдите длину замкнутой ломаной PQRSTUP, если длина ребра
куба равна 1.] (М. Гусаров)
ЗАДАЧИ ВТОРОГО ТУРА, 6-11 КЛАССЫ
6 КЛАСС
28. Дети, построенные парами, выходят из лесу, где они
собирали орехи. В каждой паре идут мальчик и девочка, причем
у мальчика орехов либо вдвое больше, либо вдвое меньше, чем
у девочки. Могло ли так случиться, что у всех вместе 1000
орехов? (А. Голованов)
29. Можно ли расставить в клетках шахматной доски 8x8
натуральные числа так, чтобы любые два числа, стоящие в
соседних (по стороне) клетках, отличались на 1, а любые два числа,
- 10-

стоящие в клетках, связанных ходом 'коня, отличались на 3?
{А. Голованов)
30. Двоечник Федя выставляет (по одной) шашки на клетки
доски К) х 10 для стоклеточных шашек. Докажите, что в какой-то
момент одна из шашек сможет съесть другую шашку.
(Ф. Бахарев)
31. На доске написано 10 двоек. Разрешается стереть любые
два числа и записать на доску их сумму или их произведение.
Может ли после нескольких таких операций на доске остаться
число 1002? (О. Малева)
32. Пятизначное число называется неразложимым, если оно
не раскладывается в произведение двух трехзначных чисел.
Какое наибольшее число неразложимых пятизначных чисел может
идти подряд? (С. Берлов)
33. Малыш и Карлсон
играют в такую игру: они берут
шоколадку 1001 х 1001 и по очереди
выкусывают из нее "по клеточкам"
кусочки (не обязательно с краю):
Карлсон — 2x2, Малыш — 1x1.
Если не осталось ни одного
кусочка 2x2, то все остальные кусочки
достаются Малышу. Выигрывает тот, кто съест больше
шоколада. Первый ход делает Малыш. Кто выиграет при правильной
игре? {С. Берлов)
7 КЛАСС
34. На пальме сидело много мартышек. Двадцать из них
получили по пинку. Пнутая мартышка срывает с пальмы три финика
и раздает подружкам. Мартышка, получившая два финика,
съедает их и пинает другую мартышку. После того как произошло
30 новых пинков, мартышки успокоились. Сколько фиников
осталось у мартышек? (Р. Семизаров)
35. Через клетчатый квадрат 1000 х 1000 проведено по линиям
сетки несколько прямых. Образовавшиеся при этом
прямоугольные части раскрашены в шахматном порядке в черный и белый
цвета. Докажите, что количество черных клеточек четно.
(С. Иванов)
-- 11 -

36. Несколько государственных служащих получили
одинаковую зарплату. После этого время от времени кто-нибудь из них
брал часть своих денег и раздавал их поровну остальным.
Через несколько таких операций у одного из служащих оказалось
24 копейки, а еще у одного - 17 копеек. Сколько было служащих?
(Р. Исмаилов)
37. На доске написано 11 двоек. Разрешается стереть любые
два числа и записать на доску их сумму или их произведение.
Может ли после нескольких таких операций на доске остаться
число 774? (О. Малева)
38. Шестизначное число называется неразложимым, если оно
не раскладывается в произведение трехзначного и
четырехзначного чисел. Какое наибольшее число неразложимых
шестизначных чисел может идти подряд? (С. Берлов)
39. На прямой отмечено несколько отрезков (быть может,
пересекающихся). Левую половину каждого отрезка покрасили в
красный цвет. Оказалось, что закрашенные точки образовали
сплошной красный отрезок. Если бы вместо этого правую
половину каждого из исходных отрезков покрасили в синий цвет,
то синие точки образовали бы сплошной синий отрезок на 20 см
короче красного. Докажите, что среди исходных отмеченных
отрезков найдутся два, длины которых отличаются не менее чем
на 40 см. (А. Храброе)
40. Малыш и Карлсон играют в такую игру: они берут
шоколадку 1997 х 1998 и по очереди выкусывают из нее "по клеточкам"
кусочки (не обязательно с краю): Карлсон — 2x2, Малыш —
1x1. Если не осталось ни одного кусочка 2 х 2, то весь
оставшийся шоколад доедает Малыш. Выигрывает тот, кто больше
съест. Начинает игру Малыш. Кто выиграет при правильной
игре? (С Берлов)
8 класс
41. Найдите все такие пары натуральных чисел т и п, что
17111
HOK(m,n) - НОД(т,п) = ~ .
О
(А. Голованов)
-12-

42. Точка D середина стороны АС
треугольника ABC. На стороне* ВС выбрана
такая точка Е, что /.BEA = /.CED.
Найдите отношение длин АЕ : DE. (С. Берлов)
43. См. задачу 32.
44. См. задачу 40.
45. По кругу расставлены числа от 1 до 30. Стоящие на
соседних местах числа можно поменять местами. После некоторого
количества таких операций оказалось, что каждое число
переместилось на диаметрально противоположное место. Докажите,
что в некоторый момент меняли местами числа, сумма которых
равна 31. (С. Берлов)
46. Дана бесконечная последовательность натуральных чисел
ап, в которой при всех п выполняется соотношение
оп+2 - НОД(ап, оп+1) + 1.
Может ли эта последовательность содержать более 1998
различных чисел? (А. Голованов)
47. В оздоровительный лагерь приехало несколько
школьников, каждый из которых имеет среди приехавших от 2 до 30
знакомых. Докажите, что опытный вожатый сможет расселить их в
GO комнат так, чтобы никакие* два знакомых не оказались в одной
комнате, и чтобы не было школьника, все знакомые которого
живут в одной комнате. {Д. Карпов)
9 класс
48. Числа х, т/, z, t удовлетворяют неравенству
(х + у + z + f )2 ^ 4(;с2 + У2 + г2 + *2).
Докажите, что существует такое вещественное число а, что
(х - а)(у — a) -f (г — a)(t — а) = 0. (С. Берлов)
49. Вдоль окружности расставлены числа от 1 до 100 (в
произвольном порядке). Для каждых трех чисел, стоящих подряд,
вычислили их сумму. Докажите, что какие-то две из
вычисленных сумм отличаются не меньше, чем на 3. (С. Берлов)
50. В треугольнике ABC точка М - середина стороны ВС;
АА\, ВВ\, CCi - высоты. Прямые АВ и А\В\ пересекаются в
-13-

точке Лг, а прямые МС\ и АС - в точке У.
Докажите, что XY \\ ВС. (Д. Ростовский)
51. Найдите все целочисленные решения
уравнения
15г2 . (А. Голованов)
p2 + q2+pq.
К М
A Q В X
52. В десятичной записи несократимой дроби т/п каждая
цифра после запятой, кроме первой, меньше суммы двух соседних
с ней цифр на одно и то же натуральное число к. Докажите, что
п < 819. (Ю. Базлов)
53. Точка М - середина стороны АС
треугольника ABC. На отрезке AM выбрали
точку А', на отрезке ВМ - точку L, на
отрезке В К - точку N. Оказалось, что KL \\ АВ,
MN || ВС, CL = 2КМ. Докажите, что CN -
С биссектриса угла ACL. (С. Верлов)
54. В стране 2п городов и несколько авиалиний. Любые
четыре города соединены друг с другом не более чем четырьмя
авиалиниями. Какое наибольшее количество авиалиний может
быть в этой стране? (С. Берлов)
10 КЛАСС
55. Числа а, 6, с удовлетворяют неравенству
шах(а, Ь) + шах(с, 1997) = min(a, с) + min(6,1998).
Докажите, что Ь ^ г. [А. Храброе)
56. О - центр описанной окружности
остроугольного треугольника ABC. Прямая ВО
вторично пересекает описанную окружность в
точке D, а продолжение высоты, опущенной из вершины Ал
пересекает окружность в точке Е. Докажите, что площадь
четырехугольника BECD равна площади треугольника ABC.
(М.Пратусевич)
57. Город расположен на нескольких островах, соединенных
между собой мостами. При поездках по городу жители
выражают длину своего пути числом мостов, которые им приходится
переезжать. После того как один из мостов1 закрыли на ремонт,
1 Болыиеохтинский.
-14-

каждый горожанин заявил: "У меня есть друг, кратчайший путь
к которому содержит теперь на один мост больше, чем раньше".
Докажите, что хотя бы один из островов - необитаемый.
(Ф. Назаров)
58. См. задачу 51.
59. См. задачу 52.
60. 999 непересекающихся отрезков с концами в вершинах
правильного 1998-угольника разбивают эти вершины на пары.
Докажите, что на отрезках можно так расставить стрелки, что сумма
полученных векторов будет равна нулю. (С. Берлов)
61. С последовательностью чисел (ai, a*i,.. • ,«п) разрешается
делать следующее: выбрать произвольный номер &, 1 ^ к < та, и
заменить в последовательности число «*. на — (ai -Ья<2Н \-ап)~-к.
Сколько различных последовательностей можно получить
такими преобразованиями из -последовательности (0,0,..., 0)?
(М. Всемирное)
11 КЛАСС
62. Найдите все положительные решения уравнения
шах(а, Ь) шах(г, 1998) = min(a, с) min(&, 1998) • t A у с \
63. Натуральное число п таково, что п +1 делится на [у/п\ +1.
Докажите, что (п — 1)(« — 3) делится на [\/п\ — 1. (А. Голованов)
64. См. задачу 57.
65. Две плоскости делят куб на четыре равновеликие части.
Докажите, что его поверхность они тоже делят на четыре
равновеликие части. (М, Гусаров)
66. Докажите, что для любого натурального п выполнено
неравенство
67. В клетках квадрата 8x8 расставлены целые числа. Каждая
клетка закрыта карточкой, на которой написана сумма чисел в
квадрате 3 х 3 с центром в этой клетке. Какое наибольшее
количество чисел в клетках квадрата можно заведомо определить,
если известны только числа на карточках? (С. Волченков)
68. См. задачу 61.
-15*-

ЗАДАЧИ ОТБОРОЧНОГО ТУРА, 9-11 КЛАССЫ
9 КЛАСС
69. На сколько нулей может оканчиваться число 1П+2П+3П+4П
(п £ N)? (А. Храброе)
70. Диагонали параллелограмма ABCD пересекаются в
Л С точке О. Окружность, описанная вокруг
треугольника АВО, пересекает сторону
AD в точке Е. Окружность,
описанная вокруг треугольника DOE,
пересекает отрезок BE в точке F. Докажите, что
/.ВСА = Z.FCD. (С. Берлое)
71. На листе клетчатой бумаги нарисована несамопересека-
ющаяся замкнутая ломаная, не проходящая через узлы сетки. В
области, ограниченной ломаной, лежит не менее 91 узла.
Докажите, что ломаная пересекает линии сетки по крайней мере в 40
точках. (С. Иванов)
72. Докажите, что количество таких натуральных чисел
атат-\ ...«! (т > 1998), что
-2 ,7= г? уг-2
awaw_i ... oi = amaw-i ... a1999 + ^1998«1997 • • • «l , — четно.
(А. Храброе)
73. В квадрате 10 x 10 расставлены все натуральные числа от
1 до 100. В каждой строке отметили третье по величине число
(считая от наибольшего). Докажите, что сумма всех отмеченных
чисел не меньше суммы чисел в некоторой строке. (С, Берлое)
74. Докажите, что проекции точки пересечения диагоналей
вписанного четырехугольника на две его противоположные
стороны симметричны относительно прямой, соединяющей
середины двух других противоположных сторон этого
четырехугольника. (С. Берлое)
75. Множество М состоит из п точек плоскости, никакие три
из которых не лежат на одной прямой. Для каждого
треугольника с вершинами из М подсчитали количество точек М внутри
него. Докажите, что среднее арифметическое всех найденных
чисел не превосходит н/4. (С. Иванов)
76. На очень большом столе лежат две кучи спичек. В первой
куче 2100 спичек, во второй - З100. Два игрока по очереди берут
спички из куч. Одним ходом разрешается брать из одной кучи к
-16-

спичек, из другой - m так, чтобы \к2 — т2\ ^ 1000. Выигрывает
взявший последнюю спичку. Кто выиграет при правильной игре?
(С. Б ер лов)
10КЛАСС
77. В троллейбусе едут 175 пассажиров и два кондуктора.
Каждый пассажир покупает билет только после того, как его три
раза об этом попросят. Сначала первый кондуктор просит
приобрести билет одного из еще безбилетных пассажиров, потом то
же самое делает второй, и так далее до тех пор, пока все не
купят билеты. Продажу какого наибольшего количества билетов
может обеспечить себе первый кондуктор? (Ф. Назаров)
78. На каждом из 10 листов бумаги написано несколько
степеней двойки. Суммы чисел на всех листах одинаковы. Докажите,
что какая-то из степеней двойки встречается на этих листах не
менее 6 раз. (С. Иванов)
79. В стране 1998 городов, любые два города соединены
авиалинией. Цены билетов на всех авиалиниях различны. Могут
ли все круговые маршруты (проходящие через каждый город по
одному разу и возвращающиеся в исходный пункт) иметь
одинаковую стоимость? (К Кохась)
80. На отрезке АС как на основании в
разных полуплоскостях построены
равнобедренные треугольники ABC и ADC, причем
Z.ADC = 3/.АСВ. АЕ - биссектриса
треугольника ABC, отрезки DE и АС
пересекаются в точке F. Докажите, что треугольник j)
CEF - равнобедренный. (С. Иванов)
81. Докажите, что для всякого натурального п > 1 между
числами пг и (/i-fl)2 можно выбрать три различных натуральных
числа «, бис так, что а2 4- &2 делится на с. (С. Берлов)
82. См. задачу 74.
83. См. задачу 75.
84. На^окружности отмечены 999 точек. Сколькими способами
можно расставить в этих точках буквы Д, В и К так, чтобы на
любой дуге между любыми двумя одинаковыми буквами стояло
четное число отличных от них? (Д. Карпов)
- 17-

11 КЛАСС
85. В куче 666 спичек. Два игрока ходят по очереди. Каждый
своим ходом может либо взять из кучи от 1 до 5 спичек, либо
обменять у судьи ранее взятые 5 спичек на ириску. Выигрывает
взявший последнюю спичку. Кто выиграет при правильной игре?
(К. Кохасъ)
86. Окружность, проходящая через вер-
£ Г 1 \ шины А и С треугольника ABC,
пересекает сторону АВ. в ее середине D, а сторону
ВС - в точке Е. Окружность, проходящая
через точку Е и касающаяся в точке С
прямой АС, пересекает прямую DE в точке F.
К - точка пересечения прямых АС и DE. Докажите, что прямые
CF, АЕ и В К пересекаются в одной точке. (С. Берлов)
87. Можно ли в "клетчатом" кубе 8x8x8 отметить 64 клетки
так, чтобы в каждом слое кубиков, параллельном грани, было
отмечено ровно 8 клеток, а среди любых 8 отмеченных клеток
какие-то две обязательно находились в одном таком слое?
(А. Вершик)
88. Найдите все многочлены Р(х> у) от двух переменных такие,
что при любых х иу Р(х -f у, у — х) = Р(ж, у). (А. Голованов)
89. 2п-угольник А\ А2 ... А2п вписан в окружность с центром О
и радиусом 1. Докажите, что
\A1A2+Aza1 + - • -+A2n-iA2n\ <2sin(-(A7^2 + .-. + A2n^iOA2n))-
(Ю. Базлов)
90. Пусть d(n) обозначает количество натуральных делителей
числа п. Докажите, что последовательность d(n2 + 1) ни с какого
места не становится строго монотонной. (А. Голованов)
91. В дружине 169 человек. Каждый день четверо из них
выходят на дежурство. Может ли через некоторое время случиться,
что любые двое отдежурили вместе ровно один раз? (К Кохасъ)
92. Можно ли в клетках таблицы 11 х 11 так расставить
буквы П, А, С, чтобы в верхней строчке таблицы было написано:
"ПАПАСПАСПСА", ни одна из остальных клеток, прилегающих
к границе, не содержала бы букву С и чтобы ни в одной фигурке
вида П-j или ЕД не было трех различных букв? (Я. Филонов)
-18-

ЗАДАЧИ ОЛИМПИАДЫ ФМЛ № 239
Осенью 1997 года состоялась очередная открытая олимпиада
ФМЛ №239. Она проходила в 1 тур, в котором приняло участие
около 80 школьников, в том числе почти все сильнейшие "олим-
пиадники" города. Олимпиада продолжалась 5 часов. При этом
все равно (как и во все предыдущие годы) нашлись задачи,
которые никто не решил.
8-9 КЛАСС
93. По окружности расставлены 20 единиц и 30 двоек так, что
никакие три одинаковые цифры не стоят подряд. Найти сумму
произведений всех троек подряд идущих цифр. (С. Берлов)
94. В треугольнике ЛВС К £ АВ, В
N Е ВС, М - середина АС. Известно, что /\
Z.BKM = /.BNM. Докажите, что перпенди- jq / \N
куляры к сторонам исходного треугольника /x^t/ \
в точках A", N, М пересекаются в одной точ- ^/ < v й \ q
ке. (С. Берлов) М
95. Вершины связного графа раскрашены в 4 цвета так, что
ребра соединяют вершины разных цветов, причем каждая
вершина соединена с одинаковым количеством вершин трех других
цветов. Докажите, что при выкидывании любых двух ребер,
выходящих из одной вершины, граф останется связным.
(С. Берлов)
96. На плоскости дано несколько равных параллельно
расположенных квадратов, причем среди любых п из них два имеют
общую точку. Доказать, что эти квадраты можно разбить на не
более чем 2п — 1 подсистем, в каждой из которых все квадраты
имеют общую точку. (В. Дольников)
97. Биссектрисы вписанного четырехугольника образуют в
пересечении выпуклый четырехугольник. Докажите, что
диагонали полученного четырехугольника перпендикулярны.
(С. Берлов)
98. Докажите, что любое число, большее п4/16 (п 6
^раскладывается в произведение двух сомножителей, разность которых
не превосходит га, не более, чем одним способом. (С. Берлов)
99. На единичной решетке дан выпуклый 2п-угольник.
Доказать, что его площадь не меньше, чем п(п — 1)/2. (С: Иванов)
-19-

100. На плоскости дано несколько векторов, сумма длин
которых равна 1. Доказать, что их можно разбить на три группы
(возможно, пустые) так, что сумма длин сумм векторов в этих
группах будет больше Zy/b/2-к. (С. Берлов)
10-11 класс
101. См. задачу 94.
102. См. задачу 95.
103. Существуют ли
многочлен Р с целыми
коэффициентами, отличный
от константы, и
натуральное число к такие, что все
числа вида F(kn) попарно
взаимно просты?
(А. Пастор)
104. См. задачу 98.
105. Точка / - центр
вписанной окружности треугольника ABC. Некоторая
окружность с центром в / пересекает сторону ВС в точках А\ и А2у
сторону С А в точках В\ и В2, сторону АВ в точках С\ и С2.
Полученные точки расположены на окружности в порядке Ai, А2,
Ви В2, Си С2. Точки А3, #з, Сз - середины дуг AiA2, ВгВ2) С\С2
соответственно. Прямые А2Аз и В\В$ пересекаются в точке С±,
прямые B2Bz и С\С$ - в точке А4, а прямые С2Сз и AiA3 - в
точке В$. Докажите, что отрезки А3А4, BzB±, С3С4 пересекаются в
одной точке. (С. Берлов)
106. На единичной решетке дан выпуклый 2п-угольник.
Докажите, что его площадь не меньше, чем п3/100. (С. Иванов)
107. Дано натуральное число п. Докажите, что существует
такое е > 0, что для любых п положительных чисел а1? а2, ... ,
ап найдется положительное вещественное число £, для которого
е< {fai},{ta2},.. '>{tan} < |. (С. Иванов, К. Кохась)
108. На плоскости дано несколько равных параллельно
расположенных квадратов, причем среди любых п из них можно
выбрать четыре имеющих общую точку. Докажите, что эти
квадраты можно разбить на не более чем п — 3 подсистем, в каждой
из которых все квадраты имеют общую точку. (В. Дольников)
-20-

ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ
1. Можно расставить крестики и нолики так:
1 вариант:
0
X
0
X
0
0
0
А'
0
X
0
X
0
X
0
0
0
X
0
X
0
Л'
А'
X
X
2 вариант:
0
0
о
0
0
X
X
0
0
X
X
X
0
0
X
0
0
X
X
X
0
0
X
X
х\
2. Ответ: 1 банан. Поскольку Сова и Кролик вместе съели 45
бананов, то кто-то из них съел не менее 23 бананов, тогда Винни
Пух съел не менее 24 бананов. Значит, Сова, Кролик и Винни
Пух съели вместе не менее 69 бананов. Но так как Пятачку тоже
что-то досталось, то Сова, Кролик и Пух съели вместе ровно 69
бананов, а Пятачок - 1 банан.
Во втором варианте решение аналогично, ответ: 1 желудь.
3. Ответ: 16 [19]. Посмотрим, какие числа появятся на доске
в течение нескольких первых минут:
23
18
20
12
14
16
18
Мы видим, что, начиная со второй минуты, числа повторяются с
периодом 5. Так как 60 = 1 + 5 • 11 + 4, то через час на доске будет
записано пятое число из (двенадцатого) периода, то есть 16. Во
втором варианте решение аналогично.
4, Ответ: нельзя. Рассмотрим внутри квадрата фигуру вида
1111111. С одной стороны, сумма чисел в этой фигуре
должна быть равна 210, так как эта фигура есть объединение двух
пятиклеточных фигур из условия; с другой стороны, эту
фигуру легко представить в виде объединения пяти прямоугольников
1x2, значит, сумма чисел в ней должна быть равна 5 • 40 = 200:
Итак, требования нашей расстановки противоре- гГП
чивы, и расставить числа нельзя. Во втором
варианте, аналогично, можно рассмотреть фигуру вида
♦ В квадрате 10 х 10 клеток расставлены натуральные числа
так, что при любом расположении фигурки вида [J [J сумма
чисел в ней равна 105. Верно ли, что сумма чисел во всей таблице
делится на 105?
еР
21

5. См. рисунок.
2 см 2 см
1.5 см 1.5 см
0.5 см
3.5 см
0.5 см
2.5 см
4 см
Существуют и другие способы.
6. Ответ: нельзя.
Предположим, что такая расстановка чисел существует. По
условию, любые два числа, стоящие через одно, имеют
неотрицательное произведение, то есть либо это числа одного знака,
либо одно из них - нуль. Занумеруем места, на которых стоят
числа, номерами от 1 до 15 [19] (всего чисел от —7 до 7 ровно 15
штук [от —9 до 9 ровно 19]), начиная с того места, где стоит нуль.
Рассмотрим по очереди числа, стоящие на местах с номерами
3,5,7,9,11,13,15,2,4,6,8,10,12,14
[3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18].
Каждые два числа, номера мест которых - соседние в этом
списке, стоят на окружности через одно. При этом среди них нет
нуля, так как нуль стоит на первом месте. Значит, все они -
одного знака. С другой стороны, список включает все места, кроме
первого, значит, все расставленные числа, кроме нуля, должны
быть одного знака. Противоречие.
7. Решение 1 (уравнение). Пусть на складе лежит х банок
по 0.7 л, а банок по 0.5 л нет. Тогда банок по 1 л всего 2500 — х
[2G00 — х]. Общая ёмкость банок равна 1998 л, значит,
0.7а: 4-1 • (2500 - х) = 1998 [0.7* + 1 • (2600 - я?) = 1998].
Преобразуя, получаем, что 0.3а: = 502 [0.3а: = 602], откуда
х = 1673^ [х = 200б|]. Но х должно быть целым числом,
значит, предположение о том, что на складе нет поллитровых банок,
неверно.
Решение 2 (делимость на 3). Предположим, что на складе
нет поллитровых банок. Измеряя емкость в единицах по 0.1 л, мы
получим, что 19980 единиц представлено в виде суммы 2500 [2600]
-22-

слагаемых, каждое из которых равно 7 или 10 единиц. Числа 7
и 10 дают остаток 1 при делении на 3, значит сумма 2500 [2600]
таких чисел должна давать тот же остаток при делении на 3, что
и число 2500 [2600], т. е. 1 [2]. Но 19980 дает остаток 0 при делении
на три.
8. Заметим, что есть цифра, которая встречается в записи
числа по крайней мере 6 раз (если каждая цифра встречается не
более 5 раз, то всего в числе не более 5 • 9 = 45 цифр). Значит,
можно вычеркнуть цифры так, что останется число из 6
одинаковых цифр. Оно делится на 111111 = 111 • 1001, значит, делится и
на 1001.
Во втором варианте достаточно оставить 4 одинаковые цифры,
1111 = 11-101.
9» Решение1 (четность). Из четырех данных чисел найдутся
2 числа одинаковой четности. Ясно, что их сумма будет четна и
поэтому не может быть равна степени нечетного числа.
Решение 2 (неравенство). Допустим, что мы нашли
требуемые числа а, Ь, с, ri, а < Ь < с < (L Пусть c + d= 5*, тогда d > 5fc/2
и 5А'/2 < b + d < 5*\ Значит, число Ь -f d никак не может быть
степенью числа 5.
11. Требуется доказать, что
треугольник EAD равнобедренный. Для этого
достаточно проверить, что /LEAD = LED А.
А так как /LEDA = ZFDC, то докажем,
что /LEAD — /.FDC. Заметим, что
треугольник DBF равнобедренный. Значит,
/LBDF = /LBFD. Тогда ZADB = ZDFC.
Теперь мы видим, что треугольники ADB и DFC равны по двум
сторонам и углу. Значит, /LEAD = /.FDC, что и требовалось.
Во втором варианте, как видно из картинки к условию, речь
идет о той же самой задаче.
т-а а
12. Пусть т и п - длины сторон исходно- I 1 I
го прямоугольника, а и b - их остатки при ln-b
делении на 7. Тогда исходный прямоуголь- I I
ник можно разрезать на 3 прямоугольника | "" """ [ 15
размерами (т — а) х гс, а х (л — Ь) и а х 6.
Поскольку у первых двух прямоугольников разрезания длина
одной из сторон делится на 7, то их можно разрезать на
прямоугольники 1x7. Так как площадь оставшегося прямоугольника
-23-

a x h не превосходит 30, а площадь исходного была не меньше
4 • 360 = 1440, то суммарная площадь разрезанной части - не
менее 1404, откуда следует, что вырезано более двухсот
прямоугольников 1x7.
13. Ответ: 4.75 [во втором варианте - 5.8]. Из неравенств
[х]{х\ ^ 3 и {х} < 1 следует, что [.т] > 3. При [х] = 4 получаем
{х} ^ 3/[#] = 0.75, т. е. х ^ 4.75. Если же [х] ^ 5, то х ^ [х] ^
5 > 4.75. Значит, наименьшее возможное значение х равно 4.75.
Второй вариант решается аналогично.
14. Пусть f(x) = ах2 + Ь\х -f сА, д(х) = ах2 + Ь2х + сг, тогда
f(x) + y(x) = 2ax2 + (bi +b>2)x + (c[ + 02) и по теореме Виета (или из
формулы для корней квадратного уравнения) сумма корней f(x)
равна (—Ь[/а), сумма корней д(х) равна (—62/а), следовательно,
—Ь\/а — Ы/а = 0, откуда -~(b\ -f Ь2)/2а — 0, а это - сумма корней
f(x)+g(x).
15. Заметим, что существует ровно 142 делящихся на 7
натуральных числа, не превосходящих 1000, и 858 не делящихся,
следовательно, хотя бы одно из выбранных чисел делится на 7.
Аналогично, существуют ровно 333 натуральных числа, которые
не превосходят 1000 и делятся на 3, значит, какое-то из
выбранных чисел делится на 3. Тогда произведение этих чисел будет
делиться на 21, если же они совпадают, то в качестве второго
сомножителя можно взять любое другое выбранное число.
В Решение второго варианта аналогично.
16. Пусть D и Е - середины сторон
АВ и АС соответственно. Заметим, что
DE || ВС || АХ, DO - серединный
перпендикуляр к АВ, значит, DO \\ КМ, аналогично
Л Е L С ОЕ || LM, тогда гомотетия с центром в
точке А, переводящая точку Е в точку L, переводит D в А", а О в М,
поэтому Д, О и М лежат на одной прямой.
Решение второго варианта аналогично, чертеж задачи
отличается, тем, что отрезок LK построен вне основного треугольника,
и сделаны переобозначения.
17. В первых двух строках не больше 15 различных чисел. В
третьей строке добавляется самое большее 5 новых чисел, так
как во второй и третьей строках всего не более 15 чисел, и по
крайней мере 10 из них встречаются во второй строке.
Аналогично, в четвертой строке добавляется не более 5 новых чисел
Ш\
-24-

и т. д. Значит, всего различных чисел не больше 15 + 98-5 = 505.
18. После подстановки х = [.'»-'] +{я} и раскрытия скобок данное
неравенство приводится к виду [#]{#} ^ 3. Далее - см. решение
задачи 13.
19. Ответ: либо толстых и тонких поровну (по 29), либо в
клубе 28 толстых и 30 тонких. (Во втором варианте
соответственно либо по 31, либо 32 толстых и 30 тонких.)
Решение 1. Пусть .т - количество толстых, ау- количество
тонких. Тогда х + /у = 58, 15.г делится на у (так как 15л: пончиков,
принесенных толстыми, поровну разделились между тонкими) и,
аналогично, 14// делится на х. Пусть d - наибольший общий
делитель х и у. Тогда d является делителем числа 58, т. е. d - одно
из чисел 1, 2, 29, 58. Рассмотрим эти случаи.
1 случай: d = 1. Это означает, что х и у взаимно просты. Так
как 15:с делится на //, а х не имеет общих простых делителей с /у,
15 должно делиться на у. Аналогично, 14 делится на х. Отсюда
х ^ 14 и у 4, 15, что противоречит равенству х -Ь у = 58.
2 случай: d = 2. Тогда .г* = 2;/;о, у = 2#о, где xq и уо - взаимно
простые натуральные числа. Условия на х и у выражаются через
xq и г/о следующим образом: ,г'о + уо == 29, 15а?о делится на j/o? 14|/o
делится на xQ. Так же, как в первом случае, отсюда следует, что
х0 ^ 14 и //о ^ 15. Значит, х0 = 14 и у0 = 15, иначе xq + уо < 29.
Значит, х = 28 и у = 30. Этот ответ подходит: 15 • 28 делится на
30, 14 • 30 делится на 28.
3 случай: d = 29. Поскольку числа х иу делятся на 29, они оба
не меньше 29. Значит, х = у — 29, иначе х -f у > 58. Этот ответ
тоже подходит.
4 случай: d = 58. Этот случай невозможен, так как х и у
должны быть не меньше 58, а тогда их сумма больше 58.
Р е ш е н и е 2. Пусть х - количество толстых, тогда количество
тонких равно 58 — х, и они вместе принесли 14(58 — х) пончиков.
Пусть каждый толстый получил по п пончиков, тогда 14(58 — х) =
их. Преобразуя, получаем, что (п + 14)х = 14 • 58. Значит, х -
делитель числа 14-58 = 2 • 2 • 7 • 29. Подставляя вместо х все
делители этого числа, меньшие 58 (а именно, 1, 2, 4, 7, 14, 28 и
29), можно убедиться, что условию удовлетворяют только х = 28
и х = 29, а для остальных получается, что 15х (число пончиков,
принесенных толстыми) не делится на 58— я (количество тонких).
20. Сделаем сначала полезное замечание: если две линей-
-25-

ные функции обращаются в нуль в одной и той же точке, то они
пропорциональны, т. е. одна из них получается из другой
умножением на некоторую константу,
Пусть f(x) = f~£j, гДе с Ф U. Знаменатель обращается в нуль
в точке х = —d/c. Если числитель тоже обращается в нуль в этой
точке, то числитель и знаменатель пропорциональны, а значит,
функция является константой (этот случай мы рассмотрим в
конце). Если же числитель не обращается в нуль при х = —d/c, то
функция принимает сколь угодно большие значения вблизи этой
точки (ее график имеет там вертикальную асимптоту).
Поскольку функция / — д ограничена снизу числом 1997, функция д тоже
должна принимать сколь угодно большие значения вблизи точки
х = —d/c. Значит, знаменатель функции д в этой точке
обращается в нуль, следовательно, он пропорционален сх + d.
Поскольку функции / и д имеют пропорциональные (можно считать, что
одинаковые) знаменатели, их разность - тоже дробно-линейная
функция со знаменателем сх + d. Значит, она либо постоянна,
либо имеет вертикальную асимптоту при х = —d/c (это
объяснено выше применительно к функции /). Наличие вертикальной
асимптоты противоречит тому, что f(x) — д(х) > 1997 для всех х*,
значит, / — д может быть только постоянной функцией.
Таким образом, мы разобрали случай, когда одна из функций
(неважно, / или д) имеет вертикальную асимптоту. Если они
обе не имеют вертикальных асимптот (т. е. если у каждой из
них знаменатель постоянен или пропорционален числителю), то
это две линейные функции. Тогда их разность - тоже линейная
функция, а поскольку она ограничена снизу, она постоянна.
♦ Как легко убедиться, разность двух дробно-линейных
функций является дробно-квадратичной функцией, т. е. отношением
двух многочленов степени не выше второй. Придумайте дробно-
квадратичную функцию, все значения которой больше 1997, но
которая не постоянна на своей области определения. Может ли
такая функция иметь знаменатель, представимый в виде
произведения двух линейных функций? А знаменатель, имеющий два
корня?
21. Решение 1 (дополнительное построение - равные
треугольники). Пусть F - точка на луче DC, расположенная за
точкой С так, что CF = В А. Так как
LABD = Z.CAD + Z.ADC = 180° - ZACD = ZiACF,
-26-

то треугольник DBA равен треугольнику ACF по двум сторонам
и углу между ними. Тогда AD = AF и
/FAC = LAD В = /БАС.
Следовательно, точка F лежит на
прямой АВ и /.BAD = /.AFC, что
равносильно равенству отрезков AD и DF.
Итак, AD = AF = DF, треугольник AFD
равносторонний, значит, /BAD = 60°.
Решение 2 (дополнительное
построение - окружность). Как и в решении
1, заметим, что /ABD = 180° - /ACD.
Пусть С\ - точка, симметричная
точке С относительно прямой AD. Тогда
/ABD + /ACXD = 180° и BD = ACi.
Значит, четырехугольник ABDC\
вписанный. Заметим, что
ZBAD = /АВСи /DAd = ZDBCi
как углы, опирающиеся на равные
хорды, /BDC\ = /ADВ из симметрии. Сумма углов треугольника
ABD равна 180°, следовательно,
180° = /BAD + /ADB + /DBCi + /АВСг =
= /BAD + /ВАС + /CAD + /BAD = 3/BAD.
Отсюда /BAD = 60°.
Решение 3 (теорема синусов). По теореме синусов для
треугольников ABD и ACD имеем
sin /BAD sin /ABD
sin /ADC sin /ACD
BD
AD
AC
AD
Как и в первых двух решениях, заметим, что /ABD + /ACD =
180°. Следовательно, sinZARD = sin ZAC£>, и правые части двух
выписанных равенств совпадают. Поскольку АС = BD,
получаем, что sin/BAD = sin/ADC. Следовательно, /ADC = /BAD
или /ADC = 180° — /BAD. Второе равенство невозможно, так
как из него следует, что АВ || CD, а это противоречит тому, что
/ABD + /ACD = 180°. Значит, /ADC = /BAD. Пользуясь
этим равенством и данными в условии соотношениями, напишем
-27-

сумму углов треугольника ABD:
180° = /BAD + /ADB + /ABD =
= /.BAD + /ADB + /CAD + /ADC =
= /BAD + /ВАС + /CAD + /BAD = 3/BAD.
Отсюда /BAD = 60°.
Замечание. Из первого решения легко увидеть, что условия
задачи эквивалентны следующему набору свойств
четырехугольника ABCD: /A = /D = 60° и АВ + CD = AD.
22. Рассмотрим какие-нибудь три строки подряд. В них, по
условию, имеется не более 16 различных чисел, из которых по
крайней мере 10 встречаются в самой верхней из трех строк.
Значит, в двух нижних строках имеется самое большее 6 чисел,
которые не встречаются выше. Разобьем все строки на пары
соседних и будем рассматривать их сверху вниз. В первой паре
строк имеется не более 16 различных чисел, так как даже в
первых трех строках их не более 16. С каждой следующей парой
строк (а этих пар, кроме первой, всего 49) добавляется не
более 6 новых чисел, поэтому всего мы насчитаем самое большее
16 + 6 • 49 = 310 различных чисел.
♦ Оценка 310 - точная: в таблице может быть ровно 310
различных чисел. Придумайте пример такой таблицы.
23. Для положительных х данное неравенство равносильно
неравенству
[х] • {х} > 1000 [ [х] - {х} £ 100 ] .
Дальше решение аналогично решению задачи 13.
24. Пусть (i[ - первый член прогрессии, d - её разность. Из
условия следует, что прогрессия содержит хотя бы одно число
вида ш!, где т > d. Это значит, что при каком-то к ai+kd = га!.
Заметим, что в этом равенстве выражения т! и kd делятся на d.
Значит, а\ тоже делится на d.
25. 41 • 271 = 11111. Дальше - см. решение задачи 8.
26. Если ни одно из найденных чисел не является корнем
производной, то среди найденных значений х не встречаются ни
локальные минимумы, ни локальные максимумы исходного
многочлена. Тогда многочлен f(x) - 10 [f(x) -11] меняет знак в
четном числе точек, поэтому значения многочлена при х ~> —со
-28-

и при х —у -foo имеют один и тот же знак, следовательно, этот
многочлен имеет четную степень. Но, с другой стороны,
многочлен f(x) — 15 [/(#) — 16] меняет знак в нечетном числе точек и,
следовательно, имеет нечетную степень. Этого не может быть,
поскольку упомянутые многочлены имеют одинаковые степени.
Таким образом, хотя бы одно из найденных чисел должно быть
корнем производной многочлена.
27. Ответ: \/20- Как нетрудно проверить, каждое из
равенств, данных в условии, означает, что угол между каждым
звеном ломаной и соответствующим ребром куба равен углу между
следующим звеном ломаной и этим же ребром куба. Отсюда
следует, что, построив подходящую развертку куба, мы сможем
добиться того, что ломаная будет изображена на ней отрезком
прямой линии. Указанные развертки для обоих вариантов
даны на рисунке. Из рисунков ясно, что в обоих случаях длина
ломаной равна >/20.
Q
A Q д
в
р
R
12
^s
A D
и
'т
С В А
4 А
[
А В
28. Заметим, что в каждой паре суммарное число орехов
должно делиться на 3, значит, и общее число орехов должно
делиться на 3 и не может быть равно 1000.
29. (См. рисунок.) Пусть в клетке А стоит
число п, а в клетке В - число п + 3. Тогда в
клетках С и D должны стоять числа п + 1 и п -f 2,
так же как и в клетках Е и F. Но тогда числа в
клетках С и F, связанных ходом коня, будут отличаться на 1,
что противоречит условию задачи. Следовательно, требуемым
образом числа расставить нельзя.
30. Рассмотрим момент, когда осталась ровно одна незанятая
клетка. Тогда одна из шашек может побить шашку, стоящую
рядом со свободной клеткой.
с
А
D
Е
В
F
-29-

31. Ответ: нет. Сначала заметим, что сумма двух
натуральных чисел, больших единицы, не превосходит их
произведения, следовательно, при проведении данных операций с п двойка,-
ми получится число, не превосходящее 2П. Рассмотрим
последнюю проведенную операцию. Так как в результате выполнения
этой операции получилось число 1002, не делящееся на 4, то эта
операция не могла быть умножением (двух четных чисел).
Значит, последней проведенной операцией было сложение. Но тогда
большее из складываемых чисел превосходило 500, поэтому оно
было получено операциями с 9 двойками (так как 28 = 256 < 500).
Но тогда меньшее число равно 2, и их сумма не превосходит
512 + 2 = 514 < 1002.
32. Ответ: 99. Пример: числа от 10001 до 10099
включительно. Действительно, все эти числа лежат в промежутке от
100 х 100 до 100 х 101, поэтому не могут быть представлены в
виде произведения двух трехзначных чисел, так как 100 х 100 и
100 х 101 - два наименьших произведения трехзначных чисел. С
другой стороны, среди любых 100 подряд идущих пятизначных
чисел обязательно встретится число, кратное 100, которое не
будет неразложимым.
33. Ответ: выигрывает Малыш.
Отметим в шоколадке следующие дольки:— см.
рисунок,. Пусть Малыш каждым своим
ходом съедает одну из отмеченных долек.
Поскольку каждым ходом Карлсон также
съедает ровно 1 отмеченную дольку, то после 125000-го хода
Карлсона отмеченных долек не останется, а значит, не останется
ни одного квадрата 2 х 2, и дальнейшие ходы будет делать
только Малыш. Осталось заметить, что Карлсон съел только 500000
долек, что меньше половины шоколадки.
34. Ответ: 90 фиников. Всего мартышки получили 50
пинков, значит, они собрали 150 фиников. 30 новых пинков сделали
те мартышки, которые съели перед этим два финика, значит, 60
фиников было съедено. Осталось 90 фиников.
35. Решение 1 (разбиение на части). Разрежем данный
квадрат на вертикальные полосы 2 х 1000. Если вдоль такой
полосы проходит одна из проведенных вертикальных прямых, то
тогда в этой полосе поровну черных и белых клеток, так как в
каждой строчке этой полосы одна клетка черная, а другая - белая.
-30-

Если же полоса не содержит продольную проведенную прямую,
то черные клетки в этой полосе образуют несколько
прямоугольников ширины 2. В обоих случаях количество черных клеточек
в полосе четно. Значит, и во всем квадрате количество черных
клеток четно.
Замечание. Вот еще одно рассуждение с разбиением на части.
Любой блок 2x2 внутри данного квадрата либо весь окрашен в
один цвет, либо две его клетки - черные, а две - белые.
Поскольку квадрат 1000 х 1000 разбивается на блоки 2 х 2 и в каждом
блоке количество черных клеток четно, во всем квадрате
количество черных клеток тоже четно.
Решение 2 (прямоугольники с нечетной площадью).
Будем называть прямоугольники с нечетной площадью нечетными.
Для доказательства утверждения задачи достаточно проверить,
что количество черных нечетных прямоугольников в данном
квадрате четно.
Проведенные прямые разбивают стороны квадрата на
отрезки. Отметим на одной вертикальной и одной горизонтальной
стороне квадрата все отрезки нечетной длины. Поскольку длина
стороны квадрата четна, на каждой из сторон мы отметили
четное число отрезков. Рассмотрим вертикальные и
горизонтальные полосы, проходящие через отмеченные отрезки, эти полосы
также будем называть нечетными. Все нечетные
прямоугольники (и только они) лежат на пересечении вертикальных и
горизонтальных нечетных полос. Проверим, что количество черных
прямоугольников среди них четно. Для каждой горизонтальной
нечетной полосы посмотрим, в какие цвета покрашены нечетные
прямоугольники в этой полосе, если двигаться по ней слева
направо, полученную последовательность цветов будем называть
раскраской (нечетных прямоугольников) в данной полосе.
Заметим, что раскраски нечетных прямоугольников в любых двух
горизонтальных полосах либо совпадают, либо
"противоположны" (вместо черных прямоугольников - белые, а вместо белых -
черные; это следует из того, что все прямоугольники на доске
покрашены в шахматном порядке). Напомним, что в любой
полосе лежит четное число нечетных прямоугольников. Поскольку
при любой раскраске четного числа объектов в два цвета
число черных объектов в "противоположной" раскраске имеет ту же
четность, что и в исходной, мы можем сделать вывод, что
четность количества черных нечетных прямоугольников в нечетных
- 31-

горизонтальных полосах одна и та же. А так как всего этих полое-
четное число, то количество черных нечетных прямоугольников
в них четно.
Решение 3 (индукция). Индукцией по числу прямых,
пересекающих наш квадрат, докажем, что количество черных клеточек
четно. База индукции, когда нет ни одной прямой, очевидна.
Допустим, что утверждение задачи верно, если число прямых не
превосходит п. Рассмотрим квадрат, пересеченный п + 1
прямыми, и соответствующую шахматную раскраску. Можно
считать, что среди прямых есть вертикальные. Сотрем самую левую
прямую и изменим на противоположные цвета всех клеток,
расположенных слева от нее. По индукционному предположению,
полученная картинка содержит четное число черных клеточек.
Заметим, что мы изменили цвета у всех клеток "вертикального"
прямоугольника со стороной 1000. Его площадь четна,
поэтому количества черных и белых клеток в нем имеют одинаковую
четность. Следовательно, перекрашивание клеток в этом
прямоугольнике не изменило четность количества черных клеток в
нем, а значит, и во всем квадрате. Таким образом, число черных
клеточек в квадрате, пересеченном п + 1 прямыми, четно.
36. Ответ: 7 служащих. Когда один из служащих раздаёт
другим часть своих денег, мы можем считать, что сначала он
дает каждому из остальных служащих по копейке, потом - ещё по
копейке и так далее, пока не отдаст все, что хотел. Заметим, что
разность количеств денег у первого и второго служащего всегда
будет делиться на А:, где А: - количество служащих.
Действительно, сразу после зарплаты эта разность была равна нулю,
т.е. делилась на к. Если первый даст остальным по копейке, то
у него станет на к - 1 копеек меньше, а у второго - на одну
копейку больше, и разность изменится на к\ т.е. по-прежнему будет
делиться на к. Аналогично, если деньги раздает второй
служащий. Если же деньги раздает какой-то из остальных служащих,
то количество денег у первого и второго увеличивается на одну
и ту же величину, т.е. разность не изменится, и опять-таки будет
делиться на к. По условию, в какой-то момент эта разность
стала равна 7 копейкам. Значит, 7 делится на к. Так как в условии
упомянуты двое служащих, то к > 1. Следовательно, к = 7.
37. Ответ: нет. Последнее действие не могло быть
умножением, так как на доске всегда все числа четные, произведение
двух четных чисел делится на 4, а 774 не делится на 4. Зна-
-32-

чит, последнее действие было сложением, и тогда одно из
слагаемых было больше 256 (можно утверждать, что одно из
слагаемых больше 387, но нам не нужна такая точность). Заметим, что
произведение двух четных натуральных чисел всегда не меньше,
чем сумма. Так как 256 = 28, то для того, чтобы получить число,
превосходящее 256, нам понадобится не менее девяти двоек.
Значит, второе слагаемое "построено" из не более чем двух двоек,
то есть оно равно 4 или 2. Первый случай не подходит, так как в
этом случае первое слагаемое не превосходит 29 = 512, и сумма
меньше 774. Во втором случае нам нужно получить число 772 из
десяти двоек. Аналогично сделанным рассмотрениям, последнее
действие при этом не может быть сложением, и мы сводим все
к задаче получить число 386 из девяти двоек. Это число не
делится на 4, значит, оно может быть получено только сложением.
Но сложением его не получить опять по аналогичным
соображениям: для большего слагаемого потребуется не меньше семи, а
если посмотреть на то, каким маленьким при этом оказывается
второе слагаемое, то не меньше восьми, а значит, ровно восемь
двоек. Самое большое число, которое можно получить из восьми
двоек, - это 256, и сумма опять мала.
38. Ответ: 99. Решение такое же, как у задачи 32.
39. Чтобы не запутаться, будем называть "сплошной
красный отрезок" (и аналогично синий) из условия задачи полосой.
Отметим середины всех отрезков. Пусть L - самая левая из
отмеченных середин, R - самая правая. Тогда и красная и синяя
полоса обе содержат отрезок LR, причем R - правый конец
красной полосы, L - левый конец синей. Красная полоса выступает
влево от точки L не более чем на половину длины
максимального отрезка, а синяя полоса выступает вправо от точки R не
менее чем на половину длины минимального отрезка. Поэтому
разность половин длин максимального и минимального отрезков
не меньше, чем разность длин полос, т. е. 20 см. Итак,
найдутся два отрезка, длины которых отличаются по крайней мере на
40 см.
40. Ответ: выигрывает Малыш. Решение аналогично
решению задачи 33.
41. Ответ. Существует единственное (с точностью до
перестановки) решение: т — 2, п — 6.
Решение 1. НОК(?п,п) является делителем числа тп, при-
-33-

чем из уравнения следует, что НОК(т, п) > тп/3. Значит,
HOK(ra,n) = ran или Б.ОК(?п,п) = тп/2. В первом случае га
и и взаимно просты, т. е. НОД(га, п) = 1. Подставляя в
уравнение, получаем, что mn — 1 = тп/3, откуда ran = 3/2. Значит, этот
случай невозможен. Во втором случае НОД(?п,«) = 2, и
уравнение переписывается в виде тп/2 — 2 = тп/3, откуда ran = 12. Но
число 12 единственным образом представляется в виде
произведения двух чисел с наибольшим общим делителем, равным 2, а
именно 12 = 2-6.
Решение 2. Пусть d = НОД(га,п), тогда га = xd и п = t/d,
где я и у - взаимно простые натуральные числа. При этом
НОК(га, 7*) = xyd, поэтому xyd — d = xyd2/3. Преобразуя,
получаем, что ху(3 — d) = 3. Значит, 3 делится на 3 — г/, откуда
3 — d = 1, т. е. d = 2. Остается уравнение #у = 3, из которого
ж = 1 и у = 3 (или наоборот). Значит, га = .rd = 2, n = yd = 6 (или
наоборот).
Решение 3. Пусть НОД(га,п) = х, НОК(га,п) = у. Тогда
тп = ху, и исходное уравнение имеет вид у — я = #у/3.
Преобразуя, получаем, что (3—a;)(y-f3) = 9. Так как у+3 — положительное
число, то 3 — х - положительный делитель девяти, меньший трех.
Отсюда .г* = 2, у = 6. Теперь нетрудно сообразить, что га = 2,
п = б (или наоборот).
42, Ответ. 2 : 1.
Решение 1. Проведем через точку D
прямую, параллельную ВС, и пусть F -
точка пересечения этой прямой с АЕ. По
С теореме Фалеса точка F делит отрезок АЕ
пополам, т. е. АЕ : FE = 2:1. С другой
стороны, FE = DE, так как в треугольнике DEF углы D и F
равны. Действительно, Z.FDE = I.CED и Z.DFE = ZBEF из
равенства накрест лежащих углов, а углы CED и BEF равны по
условию. Значит, АЕ : DE = АЕ : FE = 2 : 1.
Решение 2. Опустим из точек А и D
*В перпендикуляры АХ и DY на прямую £?С
X \у Прямоугольные треугольники АХЕ и DYE
/ ^s\e подобны, так как их углы в вершине Е рав-
/s^^&b^ ны п0 условию. Значит, AE:DE = AX:DY.
4 ^ii /||—-Д С Прямоугольные треугольники АХ С и DYC
D подобны, так как угол С у них общий,
поэтому АХ : DY = АС : DC = 2 : 1. Значит, А£ : DE = 2 : 1.
-34-

Решение 3. Построим треугольник А'ВС, симметричный
треугольнику ABC относительно прямой ВС. Пусть D' -
середина отрезка А'С, проведем отрезок
ED'. Так как LAEB = ZDEC = #~ Г?7А*
LD'EC, точки А, Е, D* лежат на од- Х\ ^^/
ной прямой. По построению, пря- / ^^е\^*7т\*
мая ЕС- ось симметрии и, в част- /^^^s^^/
ности, медиана треугольника АА!С. . ^^[Рц \/
Тогда АЕ: DE = AE: D'E = 2:1, D C
поскольку медианы в точке пересечения делятся в отношении 2:1.
45. Будем считать, что при перемещении в соседнюю позицию
против часовой стрелки число сдвигается на +1, а при
перемещении по часовой стрелке - на —1. Сумма всех сдвигов всех
чисел равна нулю, так как она равна нулю при каждом обмене.
Если занумеровать все позиции числами от 0 до 29 против
часовой стрелки, то позиция каждого числа в любой момент времени
равна остатку по модулю 30 суммы его начальной позиции и
накопленных к этому моменту сдвигов. Значит, суммарный сдвиг
каждого числа имеет остаток 15 по модулю 30, так как его
конечная позиция отличается от начальной ровно на 15.
Докажем теперь, что если числа х и 31—ж не менялись местами,
то их суммарные сдвиги равны. Для этого проследим за
расстоянием между х и 31—х вдоль дуги, проходящей от х к 31-ж против
часовой стрелки (считая расстояние между соседними числами
равным 1). Это расстояние может принимать значения от 1 до
29. При обмене, в котором участвует число #, из расстояния
вычитается его сдвиг. При обмене, в котором участвует число
31 — ж, к расстоянию прибавляется его сдвиг. Если
обмениваются два числа, отличных от х и 31 — х, то расстояние не
изменяется. Значит, если х и 31 — х не менялись местами друг с другом,
то расстояние между ними изменилось на разность суммарного
сдвига числа 31 —х и суммарного сдвига числа х. Но расстояния
в начале и в конце равны, значит, и суммарные сдвиги равны.
Таким образом, если х и 31 — х не менялись местами, то сумма
их сдвигов равна удвоенному сдвигу числа ж, то есть числу вида
60к + 30. Числа от 1 до 30 разбиваются на 15 пар вида (#, 31 — ж).
Если ни в какой паре числа не менялись местами, то общая сумма
всех сдвигов равна сумме пятнадцати чисел вида 60к + 30. Но
такая сумма имеет остаток 30 по модулю 60, а сумма всех сдвигов
должна быть равна нулю.
-35-

46. Да, может. Приведем пример такой последовательности.
Положим а2ооо = 3, ai999 = 4. Числа an, начиная с п = 2001,
определим по индукции с помощью данной в условии формулы. Числа
an, где 1 ^ п ^ 1998, построим "обратным ходом" (т. е. сначала
aiggs, потом ai997, и т. д. до ах) по формуле a„ = (an+i-l)(an+2-l).
По индукции легко доказывается, что числа агооо» «1999» • • •, «1 все
не меньше трех и возрастают. В частности, они все различны.
Убедимся, что построенная последовательность удовлетворяет
соотношению an+2 = НОД(ап,ап+1) + 1. При п > 1999 это
выполняется автоматически. При п = 1998 имеем ап =3-2 = 6,
НОД(ап,ап+1) + 1 = НОД(6,4) + 1=3 = ап+2. Пусть п ^ 1997.
Тогда
НОД(ап,ап+1) = НОД((ап+1 - 1)(ап+2 - l),an+i) =
= НОД(ап+2 - 1, an+i) = НОД(ап+2 - 1, (оп+2 - 1)(ап+з - 1)) =
= Gn+2 ~ 1»
что и требовалось. (Второе равенство в цепочке следует из того,
что an+i - 1 взаимно просто с an+i.)
47. Обобщим немного условие задачи, а именно будем
считать, что количество знакомых одного школьника может быть
от 0 до 30, но требование, чтобы все знакомые не жили в одной
комнате, будем применять только к тем, у кого не меньше двух
знакомых.
Докажем обобщенное утверждение задачи индукцией по числу
школьников. База (нуль школьников) очевидна. Предположим,
что приехало п школьников, и что для любого их количества,
меньшего п, утверждение уже доказано. Если среди приехавших
никто ни с кем не знаком, расселим их как угодно. В противном
случае выберем двоих знакомых (пусть это Вася и Петя) и
расселим всех остальных в соответствии с обобщенным условием.
Будем называть комнату неподходящей для Васи, если
выполняется хотя бы одно из следующих условий:
1) в ней живет кто-то из знакомых Васи;
2) у Васи есть знакомый (не Петя), который имеет кроме
Васи ровно одного знакомого, и этот знакомый знакомого живет в
данной комнате;
3) у Пети есть еще знакомые, кроме Васи, и все они живут в
данной комнате.
-36-

Аналогично определим комнаты, неподходящие для Пети.
Легко проверить, что если поселить Васю и Петю в разные
подходящие для них комнаты, то условие будет выполнено.
Посмотрим, сколько комнат могут быть неподходящими для Васи.
Первое и второе условие (по отдельности) делают неподходящими
самое большее столько комнат, сколько есть знакомых у Васи,
кроме Пети, то есть не более 29 комнат. Третьему условию
может удовлетворять только одна комната. Всего получается не
больше 59 комнат. Заметим, однако, что если их ровно 59, то все
знакомые Пети живут в одной комнате, а тогда при аналогичном
подсчете для Пети мы получим не более 1 -f 29 + 1 = 31 комнат.
Таким образом, для каждого из них неподходящими являются не
более 59 комнат, причем если у одного их ровно 59, то у другого
меньше. Значит, для любого из них есть хотя бы одна
подходящая комната, и при этом для кого-то из них подходящих
комнат хотя бы две. Пусть есть хотя бы две комнаты, подходящие
для Пети. Тогда сначала поселим Васю в подходящую для него
комнату, а потом поселим Петю в подходящую для него
комнату, отличную от той, куда поселили Васю. Таким образом, все
школьники окажутся расселенными в соответствии с
(обобщенным) условием.
48. Решение 1: заметим, что левая часть данного в условии
равенства представляет собой квадратный трехчлен
относительно (I. Если равенство не выполняется ни при каких значениях а,
то дискриминант данного трехчлена будет отрицателен, т. е.
(х + у + z + tf - 8{ху + **) < 0 ,
откуда
(х + y + z + tf < 8{ху + zt) < 4(х2 + y2 + z2 + t2),
что противоречит данному в условии неравенству.
Решение 2: после несложных преобразований данное в
условии неравенство приводится к виду/
(:, _ yf + (:с _ zf + (Х _ tf + („ _ zf + (у _ tf + (Z _ tf ^ 0 ,
которое выполняется только при х = у = z = t. Теперь можно
взять а = х.
49. Разобьем все числа, кроме 100, на 33 непересекающиеся
тройки подряд стоящих чисел. Поскольку сумма всех чисел в
тройках равна 1 + 2 Н Ь 99 = 4950, то найдется тройка, сумма
-37-

чисел в которой не более 150. Теперь разобьем на, 33
непересекающиеся тройки все числа, за исключением 1. Сумма чисел в
этих тройках равна 5049, следовательно, одна из сумм в них не
менее 153. Таким образом, мы нашли две тройки, суммы чисел в
которых различаются не менее чем на 3.
50. Поскольку ААХу ВВ\,
СС\ - высоты, то
четырехугольники АВА\В\ и ВСВ\С\
~ вписанные, значит,
Z.ClBM = /LClBlA =
= ZAi£1C = a.
Так как С\М - медиана
прямоугольного треугольника
ВС\С^ выходящая из
прямого угла, то /LBC\M = а,
откуда ZYC\X = /УВ\Х = а и четырехугольник XYC\B\ -
вписанный, поэтому ZYXCi = /YBiCi = ZCiBM, значит, XY || ВС.
51. Ответ. р = g = г = 0, других решений нет.
Решение 1 (делимость на 3). Предположим, что хотя бы
одно из чисел р, q, r отлично от нуля. Уравнение сохраняется при
умножении всех переменных на одно и то же число, поэтому,
сократив на наибольший общий делитель, мы получим решение, в
котором р, q и г взаимно просты в совокупности. Докажем,
однако, что они должны все делиться на 3, это противоречие будет
означать, что сделанное нами предположение неверно. Данное
уравнение является квадратным относительно р. Поскольку оно
имеет целый корень, его дискриминант
D = q2 - %2 - 15г2) = -3q2 + 60г2 = 3(20г2 - q2)
должен быть точным квадратом. Так как он делится на 3, он
должен делиться и на 9, значит, число D/3 = 20r2 — q2 делится на
3. Если оба числа дигне делятся на 3, то их квадраты дают
остаток 1 при делении на 3, и, следовательно, 20r2 — q2 дает
остаток 2. Если же одно из них делится на 3, то и другое делится
на 3, так как коэффициенты 20 и —1 на 3 не делятся. Значит, р и q
делятся на 3, поэтому левая часть исходного уравнения делится
на 9. Следовательно, г делится на 3.
Решение 2 (делимость на 5). Вместо того, чтобы проверять,
что р и q делятся на 3, докажем, что они делятся на 5 (остальное -
-38-

так же, как в первом решении). В отличие от делимости на 3, это
можно установить перебором всех возможных остатков чисел р
и q при делении на 5, но мы приведем более короткий (и менее
унизительный) способ. Перепишем уравнение в виде
(p-2g)2-3g2 + 5pg = 15r2.
Поскольку bpq и 15г2 делятся на 5, получаем, что (р — 2q)2 и Зд2
дают одинаковые остатки при делении на 5. Квадрат целого
числа может давать остатки 0, 1 или 4 при делении на 5, а утроенный
квадрат - 0, 3 или 2, так что остатки могут совпадать только если
числа делятся на 5. Значит, р — 2q и q делятся на 5, откуда и р
делится на 5.
52. Решение 1. Отбросив целую часть, будем считать, что
число ~ записано десятичной дробью 0, а^г^з^— Умножим
^ на 100, на —10 и на 1, и полученные результаты сложим:
100— =а1а2,аза405-- •
~10~ = аьа2аза4...
** = 0,ага2а3...
У1"~" == • • • , п/ К К • . «
Из условия задачи вытекает, что получится дробь, в которой все
цифры после запятой равны к. (Легко убедиться, что к ^ 9,
например, рассмотрев наибольшую цифру числа ~.) Таким
образом, число ~ • 91 представимо в виде дроби со знаменателем 9,
следовательно, число ~ представимо в виде дроби со
знаменателем 819. Значит, п - делитель числа 819. Поэтому п ^ 819.
Решение 2. Обозначая первую цифру после запятой через а
и вторую - через Ь, из условия находим, что третья цифра равна
6 + к — а, четвертая - 2к — а, пятая - 2к — 6, шестая - к + а — 6,
седьмая - а, восьмая - 6. Таким образом, цифры повторяются
через шесть, поэтому дробная часть нашего числа равна
числу, образованному ее первыми шестью цифрами, умноженному
на 0, (000001) = 999q99 » Первые шесть цифр образуют число
100000а -fl00006+1000(b+ifc-a) + 100(2A;~a)-fl0(2A;~6)+A;+a-b =
= 98901а + 109896 + 122U,
-39-

значит, дробная часть числа ~ равна
98901а + 10989b+1221fc _ 81а + 9ft + к
999999 ~ 819
(числитель и знаменатель сократились на 1221).
53. Пусть Р - середина стороны АВ.
Тогда точка N будет лежать на прямой
РМ, проходящей через середину
основания АВ трапеции ABLK и точку
пересечения ее боковых сторон. Следовательно,
на этой прямой также лежит точка
пересечения диагоналей трапеции, которая будет
тогда совпадать с N. Значит, точки А, N и L лежат на одной
прямой. Осталось заметить, что из подобия
AN/NL = AB/KL = АМ/МК = АС/2МК = AC/CL,
откуда CN - биссектриса треугольника ACL.
54. Ответ: га2. Пример: страна разбита на 2 республики по
га городов в каждой, авиалиниями соединяются только города из
разных республик.
Докажем индукцией по количеству городов следующее
утверждение: если в стране 2га городов, любые 4 из которых соединены
не более чем четырьмя авиалиниями, то всего авиалиний не
более га2, если же городов 2га + 1, то авиалиний не более га2 + п.
База для четырех городов следует из условия. Переход: если
утверждение неверно для к городов, то, удаляя город, из
которого выходит наименьшее количество авиалиний (или один из таких
городов), получим, что утверждение неверно и для А;— 1 городов.
Действительно, если при к = 2/ra-fl доказываемое утверждение не
выполнено, то можно считать, что авиалиний ровно п2+ ra-fl.
Тогда найдется город, из которого выходит не более га авиалиний,
иначе всего авиалиний будет не менее (га~Ы)(2га + 1)/2 > п2 + га + 1.
Закроем в этом городе аэропорт. Тогда в стране останется 2гга
городов и (2т)2+ 1 авиалиний между ними, причем любые четыре
города по-прежнему соединены не более чем четырьмя
авиалиниями. Это противоречит предположению индукции. Аналогичное
рассуждение верно при к = 2*/га.
♦ Обозначим
Г п'2/4, если га четно
/(«) = 1/2 1 W |
(, (тг — 1)/4, если га нечетно.
Ж
-40-

Тогда если в графе с п вершинами любой подграф с к вершинами
содержит не более f(k) ребер, то в самом графе не более /(п)
ребер.
55. Решение 1. Заметим, что max(a,b) ^ min(a,с), так как
первое из этих чисел не меньше а, а второе - не больше а. Значит,
шах(с, 1997) ^ min(6,1998). Заменяя левую часть этого
неравенства на г (от этого она не увеличивается), а правую часть - на b
(от этого она не уменьшается), получаем требуемое неравенство
с ^ Ь.
Решение 2. Складывая очевидные неравенства тах(а,6) ^ Ь
и шах(с, 1997) ^ с, получаем, что левая часть данного в условии
равенства не меньше Ь + с. Складывая неравенства min(a,c) ^ с
и miu(6,1998) ^ Ь, получаем, что правая часть не больше Ь + с.
Но левая часть равна правой, поэтому во всех складывавшихся
неравенствах достигается равенство. В частности, тах(а, 6) = Ь,
откуда Ь ^ а, и min(a,r) = с, откуда с ^ а. Значит, 6 ^ а > с.
Замечание. Условие задачи эквивалентно системе неравенств
1997 ^ с ^ а ^ b ^ 1998. Доказательство аналогично решению 2.
56. Пусть Н - основание высоты, опущен- g
ной из А на ВС. Угол BCD - прямой, так /^/^\
как BD - диаметр окружности. Четырех- / / vSA
угольник BECD составлен из треугольников I / /J^l^
BCD и ВСЕ, в которых DC и ЕН являются ч^*Т У
A v I^-~^у С
высотами, опущенными на ВС. Значит, его jfCZ^
площадь равна ^ВС(ЕН + CD). Поскольку
площадь треугольника ABC равна \ВС • АН, достаточно
доказать, что EH + CD = АН. Прямые АЕ и DC параллельны, так
как они перпендикулярны ВС, Значит, четырехугольник ADCE -
равнобочная трапеция, так как он вписан в окружность.
Величина EH + CD равна сумме проекций отрезков СЕ и CD на прямую
АЕ, т. е. проекции отрезка ED на АЕ. Так как в равнобочной
трапеции диагонали равны и образуют одинаковые углы с
основанием, проекция ED на АЕ по длине равна проекции АС на АЕ,
которая совпадает с АН.
57. Пусть закрытый мост М соединяет острова А и В.
Расстояние (наименьшее число мостов) между какими-то островами
может увеличиться при закрытии моста М только в том случае,
когда до закрытия любой кратчайший путь между этими
островами проходил через М. Кроме того, ясно, что любой участок
-41-

кратчайшего пути тоже является кратчайшим путем, и
кратчайший путь не может проходить через один остров два раза.
Предположим, что утверждение задачи не выполняется, т. е.
на каждом острове кто-то живет. Сначала докажем, что после
закрытия моста М с острова А можно добраться до острова В.
Для этого рассмотрим человека, живущего на острове А. Пусть
его друг, расстояние до которого увеличилось на один мост,
живет на острове X. Поскольку кратчайший путь от А до X должен
был проходить через мост М, он состоял из переезда через М и
некоторого кратчайшего маршрута от В до X, который при этом
не проходил через М. Значит, от А до В после закрытия моста М
можно добраться, проехав сначала от А до X, а потом повторив
кратчайший маршрут от В до X в обратном направлении.
Рассмотрим кратчайший путь между островами А и В после
закрытия моста М. Выберем остров С посередине или "почти
посередине" этого пути, т. е. так, чтобы расстояния от С до А и
В отличались не более, чем на 1. Пусть У - тот остров,
расстояние до которого от С увеличилось на один мост. Рассмотрим
кратчайший путь от С к У до начала ремонта. Пусть, например,
он шел сначала от С к А, потом через мост М на В, а потом от
Б к У. Рассмотрим вместо этого путь, который сначала идет от
С л В (по участку кратчайшего пути от А к В), а потом от В к У
так же, как и в первом пути. Этот путь CBY не длиннее
исходного пути CABY, так как участок СВ отличается от участка С А
не более чем на 1. Значит, существовал кратчайший путь от С
к У, не проходящий через мост М. Это противоречит тому, что
расстояние от С до У увеличилось.
♦ Докажите, что если раньше какой-нибудь кратчайший путь
между двумя островами проходил через ныне закрытый мост, то
теперь любой кратчайший путь между теми же двумя островами
проходит через один из необитаемых островов.
60, Занумеруем вершины 1998-угольника по кругу. Тогда
каждый отрезок соединяет четную вершину (= вершину с четным
номером) с нечетной. Действительно, так как отрезки не
пересекаются, с обеих сторон от любого из них должно лежать четное
число вершин - концов других отрезков. Нарисуем стрелки так,
чтобы полученные векторы вели из нечетных вершин в четные.
Каждый вектор равен разности двух векторов, ведущих из центра
многоугольника в соответствующую четную и нечетную
вершины. Поэтому сумма всех нарисованных векторов равда разности
-42-

суммы векторов, ведущих из центра, в четные вершины, и
аналогичной суммы для нечетных вершин. Четные и нечетные
вершины по отдельности образуют правильные 999-угольники с тем
же центром, а сумма векторов, ведущих из центра правильного
999-угольника в его вершины, равна нулю (так как она не
изменяется при повороте на угол 27г/999). Значит, сумма векторов,
нарисованных на отрезках, равна нулю как разность двух
нулевых векторов.
61. Ответ: (п + 1)1
Положим Xk = dk -f к — § для к = 1,2,..., п. Легко проверить,
что замена числа а*, на — {а\ Н 1- ап) — к соответствует замене
числа Xk на -(х\ -| Ь хп). Добавим к нашей
последовательности еще одно число х0. Значение х0 зададим так, чтобы сумма
хо + х\ -f • • • -f хп была равна нулю, т. е. х0 = — (a?i + Ь хп).
При преобразовании последовательности на место ж*,
становится старое значение жо, поэтому для того, чтобы сохранить
нулевую сумму, нужно поставить на место х0 старое значение х^..
Другими словами, данная операция сводится к перестановке
чисел xq и Xk- Такими операциями можно получить все возможные
перестановки первоначальных чисел (ж0, #i,... ,хп) и только их.
Если все числа хоУ a?i, ... , хп различны, то таких перестановок
ровно (га + 1)!, а последовательностей (а^) столько же, так как
они находятся во взаимно однозначном соответствии с
последовательностями (ж/ь).
Проверим, что при а\ = • • • = ап = 0 числа а?о,яь ...,яя
действительно различны. При 1 ^ к ^ п числа Xk = к— & принимают
различные значения от — ^тр до ~. Число Хо равно
/„ ч п2 п(п-\-1) п2 п
т. е. оно меньше всех остальных чисел ж*..
62. Задачу можно решить аналогично задаче 55. Впрочем, на
олимпиаде многие участники перебирали возможные
взаиморасположения данных величин (24 варианта) или различные
варианты "раскрытия " максимумов и минимумов (16 вариантов).
63. Обозначим t = [у/п]. Тогда t2 + 1 ^ п + 1 ^ t2 + It + 1.
По условию, п + 1 делится на t -f 1. Значит, п + 1 = t2 + t или
п + 1 = t2 + 2t +1. Тогда (п - 1)(п - 3) = (t2 +1 - 2){t2 +1 - 4) или
(n — l)(ra - 3) = (t2 + 22 — \){t2 + 2£ — 3). Оба выражения делятся
на t — 1.
-43-

65. Всякая плоскость, проходящая через центр куба, делит
объем куба пополам. Это следует из соображений центральной
симметрии. Обратно, всякая плоскость, делящая объем куба
пополам, проходит через центр куба. Действительно, если бы это
было не так, то мы могли бы выполнить такой параллельный
перенос данной плоскости, чтобы она стала проходить через цент])
куба. Но при таком движении плоскости объем одной из частей
куба будет увеличиваться, объем другой - уменьшаться, что
невозможно, так как после переноса объемы опять должны быть
равными.
Итак, обе данные плоскости проходят через центр куба.
Каждая из образовавшихся четвертей куба очевидно
представляет собой объединение нескольких пирамид, основания которых -
это части граней куба, а вершины находятся в центре куба.
Высота любой такой пирамиды равна половине длины ребра куба.
Следовательно, площадь поверхности куба в каждой четверти
равна объему этой части куба, деленному на одну шестую
длины ребра куба. Поэтому плоскости делят поверхность куба на
равные части.
66. Решение 1.
К)К)--К)-Ч+£)(»£)---('+^)<
, га + 1 п + 2 2п
= ni . . . = 2п!
п п Н-1 2п — 1
Решение 2 (индукция): Докажем это неравенство
индукцией по га. При п = 1 имеем равенство. Докажем индукционный
переход.
^^)<ПК)-т£Ч-+'+=тт)-
A.*=l к=1 п
-пС'О-^т^пК)-'-^-
По предположению индукции, последнее выражение не
превосходит 2n!(n + l) = 2(n + l)L
♦ «i,«2». • • ,а„ > 0, a-i ~Ь а-2 + ... + ап = 1. Докажите, что
ffi=i(»' + «.-)<2n!.
-44-

♦ Решение 3 (определение числа е.). Воспользуемся тем, что
при всех натуральных п (l -f ^-)n < е.
КЖ)-Ю--(>+г:)('+г:)-(^)<
< гс! • 11 + -J < en!
Получилось грубо, поэтому будем действовать тоньше
'K)K)-K)""-(^)('+r:)-(^)<
2п '
•П!
При и ^ 2 у/с- §*±f < Cv/e/5 < 1.98.
♦ Константа 2 в правой части неравенства слишком груба при
больших гс. Действительно, так как 1 + х < ех при х ^ 0, а
1 +£ + ••• + £ <1пп + 1, то
n! < JJ (к + I) = п! Д (l + 1) < п! • е*<1+*+~+±> ^ н! • е1^ .
Так как lim lu " "k1 = 0, мы получаем, что левая часть исходного
я—*+оо п
неравенства при п —» +оо асимптотически равна гс!.
67. Ответ: всегда можно определить четыре числа.
Существуют такие расстановки чисел, для которых больше четырех
чисел узнать не удастся.
Будем использовать шахматные обозначения: число,
написанное на клетке al, обозначим Л1, число на клетке е8 — ES и т.д.,
а для чисел на карточках будем использовать строчные буквы:
аЪ - число, написанное на карточке, лежащей на клетке а5, и
т.д. Проверим, что всегда можно найти числа СЗ, С6, F3, F6.
Действительно, нетрудно видеть, что сумма всех чисел на доске
равна Ы + \Л + 67 + cl + с4 -Ь с7 4- /&1 + Л4 -f Л7 (на рисунке
изображены прямоугольники, соответствующие указанным карточкам).
С другой стороны, сумма всех чисел, за исключением СЗ, равна
(см. второй рисунок) a4+a7+M+d5 + d8-f e2-f #5-f (/8-f/i2. Значит,
СЗ равно разности этих двух выражений.
-45-

Число С6 можно найти ещё проще: С6 = а8 +67 — а7 — 68. После
этого найдем F3 из равенства
F3 - С6 = с/2 - /d - el + г/1 - 61 + а2 - а4 + а5+
+ а8 - 67 + г/8 - е8 + д8 - Л7 + Л5 - ЛЗ ,
а затем F6 - из равенства
F6 + СЗ - CG - F3 = с/4 + е5 - с/5 - е4.
Надеемся, у читателя все в порядке с чувством юмора.
Теперь приведем пример двух расстановок чисел на доске,
для которых совпадают числа на всех карточках (все они равны
двум), но при этом сами расстановки имеют совпадение только
в четырех "необходимых" клетках. Это доказывает, что более
четырех клеток определить, вообще говоря, нельзя.
"о'
i 1
pi
0
1
1
0
1
1
0
1
1
0
-1
1
0
1
-1
0
1
-1
0
1
-1
0
1
-1
0
1
1
0
1
1
0
1
1
0
-1
1
0
-1
1
0
-1
1
0
-1
1
0
1
-1
0
1
1
0
1
т
0:
1
1
0]
-1|
1]
0
|Т
|о
1
! 1
0
-1
1
0
0
1
-1
0
1
1
0
1
-1
1
0
-1
1
0
-1
1
1
0
1
1
0
1
1
0
0
1
-1
0
1
-1
0
1
1
-1
0
1
-1
0
1
-1
1
0
1
1
0
-1
1
0
"б"1
1
-1:
0
1
1
0
1
69. Ответ: {0,1, 2}. Сначала заметим, что при п = 4 данное
число оканчивается не нулем, при п = 1 - одним нулем, а при
п = 3 - двумя нулями. Осталось проверить, что данное в условии
число не может делиться на 8, и поэтому не может иметь на конце
более двух нулей. Действительно, при п < 3 это проверяется
непосредственно, а при п ^3 2П и 4П делятся на 8, 1п дает при
делении на 8 остаток 1, а Зп - остаток 3 или 1. Значит, сумь:а не
делится на 8.
-46-

70. В силу свойства вписанных углов в с
Z.EFD = ZEOD = /LEAD = LBCD, по- /^7^ ~^7
этому четырехугольник BFDC - вписан- / / \у&< /
ный. Тогда ZBCF = Z.BDF = ZOEF = 1 /^ff\\/
LOAB = ZACD, откуда /ЛСЛ = ZFCD. )С X V
71. Проведем через каждый узел
внутри ломаной вертикальную и горизонтальную прямые. Пусть
в результате получилось и различных вертикальных прямых и m
горизонтальных. Поскольку каждая из этих прямых пересекает
ломаную в двух точках, то достаточно доказать, что т + п^ 20.
Действительно, по условию тп ^ 91, а если m-fn ^ 19, то в силу
неравенства о средних тп ^ (m+?v ^ ~- == 90~.
72. Обозначим через х и у числа amam-i .. . CI1999 и 01998 •. .«1
соответственно. Тогда данное условие можно переписать в
виде- К)1998* + у = я2 + у2, откуда *(101998 - я?) = </(з/ - 1).
Следовательно, если число Щ удовлетворяет условию, то и число
(1Q1998 — х)у также удовлетворяет условию. Таким образом, все
искомые числа разбиваются на пары. Осталось заметить, что
поскольку СЦ998 ф 0, то у ^ ДО1997 и 0 < х < 101998, значит.каждое
число имеет пару. Если же числа в паре совпадают, то число
у (у — 1) будет точным квадратом, что невозможно, так как оно
больше (у — I)2, но меньше у2.
73. Пусть хо > х\ > • • • > хд - третьи по величине числа в
строках. Заметим, что существует не более 20 чисел, которые
могут быть больше #о, это первые и вторые по величине числа
в строках, следовательно^ ^ 80. Аналогично, xi ^ 72.
Рассмотрим строку, содержащую х$. Сумма чисел в ней не превосходит
1()0 + 994~;г9 + (.г'9-1) + Ь-(х9-7) = 8я9 + 171. Сумма же третьих
чисел не меньше 80+72+ (#9 +7) Н |-#я = 8х*э + 180, т. е. больше,
чем сумма чисел в строке, содержащей х$.
74. Назовем данный четырехугольник
ABCD, О - точка пересечения его
диагоналей, А' и L - ее проекции на стороны ВС и
AD, М и N - середины сторон АВ и CD
соответственно. Пусть Р и Q - середины
отрезков АО и ОВ соответственно. Так как
медиана прямоугольного треугольника, проведенная из
прямого угла, равна половине гипотенузы, то MP = ВО/2 = KQ,
-47-

LP = АО/2 = MQ. Кроме того, в силу подобия треугольников
AOL и ВОК Z.APL = ZBQK, также ZAPM = Z.AOB = LBQM,
значит, Z.MPL = Z.MQK. Следовательно, AMPL = AKQM и
ML = А'М. Аналогично, А'ЛГ = iVL и точки А" и £ симметричны
относительно прямой MN.
Замечание. Внимательный читатель, вероятно, обратил
внимание на то, что расположение точек, приведенное на картинке,
на самом деле невозможно.
75. Сумма всех найденных чисел равна количеству пар
"треугольник и точка внутри него". Каждая такая пара определяет
четыре точки из множества М, и при этом каждая четверка
точек учитывается не более одного раза, так как из четырех
точек только одна может лежать внутри треугольника,
образованного тремя другими. Значит, сумма найденных чисел не пре-
п = ~^ 24 * ^°"
личество же этих чисел равно количеству треугольников, т. е.
С*з __. liiitziJiiizli} поэтому среднее арифметическое не превосхо-
дат СЦС1 = а=2. ,
♦ Докажите, что среднее арифметическое этих чисел не
превосходит даже п/Ъ (при п > 4).
76. Ответ: выигрывает первый игрок. Каждую позицию
будем задавать парой чисел (а, Ь), где а и b - количества
спичек в кучах. Позицию будем называть выигрышной, если в ней
побеждает тот игрок, которому предстоит делать ход, и
проигрышной в противном случае. Как обычно, любой ход,
совершаемый из проигрышной позиции, ведет в выигрышную, а для
выигрышной позиции обязательно найдется хотя бы один ход,
ведущий в проигрышную. Допустим, что исходная позиция -
проигрышная. Тогда каждая из позиций (2100 - 1000,3100 - 1000),
(2100 - 2000,3100 - 2000), ... , (2100 - 10000000,3100 - 10000000)
является выигрышной. Следовательно, для каждой из этих позиций
можно сделать ход в проигрышную позицию, причем для этого
нужно брать из куч НЕ поровну спичек, а значит, менее 1000
спичек из каждой кучи. Заметим тогда, что все эти 10000
проигрышных позиций будут различными, и в каждой из них разность
количеств спичек в кучах лежит в промежутке от З100 — 2100 — 1000
до З100 — 2100 + 1000. Поэтому среди этих проигрышных
позиций найдутся две, у которых разности количеств спичек в кучах
совпадают, а значит, из одной из них можно перейти в другую,
-48-

взяв из куч поровну спичок. Это противоречит свойствам
проигрышной позиции. Таким образом, исходная позиция должна
быть выигрышной.
77. Ответ: первый кондуктор может продать все 175 билетов.
Для этого ему достаточно действовать так, чтобы после его хода
не было пассажиров, к которым подходили два раза (тогда
второй кондуктор не сможет продать ни одного билета). Ясно, что
после первого хода это условие выполняется. Предположим, что
оно выполняется после очередного хода первого кондуктора,и
покажем, что он может обеспечить его выполнение и после
следующего своего хода. Если второй кондуктор подходит к какому-то
пассажиру, к которому уже подходили, то первый может подойти
к тому же пассажиру (в третий раз) и продать ему билет. Если
же второй подходит к пассажиру, к которому еще не подходили,
то первый может найти еще одного пассажира, к которому ни
разу не подходили. Действительно, если после хода второго таких
пассажиров не осталось, то к каждому подходили один или три
раза, а так как пассажиров нечетное число, то общее количество
подходов кондукторов к пассажирам нечетно. Но это количество
должно быть четным, так как перзый и второй кондукторы
сделали поровну ходов.
78* Пусть N - сумма чисел на одном листе, тогда сумма чисел
на всех листах равна 107V. Пусть п - наибольшее целое число,
для которого 2n ^ N. На листах могут быть написаны только
числа 2n, 2n~l, ... , 1. Если каждое из них встречается не более
5 раз, то их сумма не превосходит
5(2" + 2П~1 + ... + 1) = 5(2И+1 - 1) = 10 • 2П - 5 < 10iV.
79. Да, могут. Сопоставим городам числа Ci, ... , С1998 так,
чтобы все попарные суммы чисел С{ были различными (например,
можно положить С{ = 2г). Пусть цена билета между двумя
городами равна сумме чисел, сопоставленных этим городам. Тогда
все цены различны, но стоимость любого круго- £
вого маршрута равна 2(ci Н Ь Ciggs)- /\
80. Пусть ZACB = LCAB = 2а, тогда //^П\.
Z.ADC = 6а, Z.CAE = а и A^—EJ—\ С
LAEC = 180° - ZCAE - /.АСЕ = 180° - За. ^^^^1
Заметим, что а < 30°, так как 6а < 180°.
Пусть О - центр описанной окружности треугольника АЕС. По-
-49-

скольку угол ЛЕС - тупой (ZAEC = 18()°-За > 180о~-3-3()° = 90°),
точки О и Е лежат в разных полуплоскостях относительно АС\
и Z.AOC = 300° - 2ZAEC = Ga. Поскольку АОС -
равнобедренный треугольник с основанием АС и углом 6а при вершине, он
совпадает с треугольником ADC. Таким образом, D - центр
описанной окружности треугольника АЕС, в частности, DE = DC.
Значит,
/LDEC = ZZX7E = ZAC£ + Z.DCE = 2а + (90° - За) = 90° - а,
Z.EFC = 180° - ZFC£ - IFEC = 180° - 2а - (90° - а) = 90° - а.
Таким образом, в треугольнике CEF углы Е и F равны, значит,
он равнобедренный.
81. Положим с = п2 + 1, « = /*2+2, 6= п2 + п + 1. Легко видеть,
что при п > 1 эти числа действительно различны и лежат в
указанном интервале. Поскольку а дает при делении на с остаток 1,
а Ъ - остаток п, а2 + Ь2 дает тот же остаток, что и п2 + 1, то есть
делится на с.
84. Ответ: 2999 + 1.
Среди расстановок, удовлетворяющих условию, есть три
тривиальных, в которых все буквы одинаковы. Докажем, что
количество нетривиальных расстановок равно 2999 — 2.
Установим взаимно однозначное соответствие между
нетривиальными расстановками, удовлетворяющими условию, и такими
расстановками букв Д, В и К, в которых любые две соседние
буквы различны. Для удобства изложения буквы расстановок
второго вида будем располагать между отмеченными точками.
Пусть X - расстановка без повторений. Чтобы получить
соответствующую ей расстановку У, поставим между каждыми двумя
соседними буквами расстановки X букву, отличающуюся от них
обеих. Поскольку соседние буквы в X различны, это определяет
расстановку Y однозначно. Докажем, что расстановка Y
удовлетворяет условию. Буквы, отличные от Д, стоят в ней в тех
точках, рядом с которыми в расстановке Аг имеется буква Д. Значит,
все такие буквы разбиваются на пары соседних - те пары букв,
между которыми стоит буква Д расстановки X.
Следовательно, их количество на любой дуге между двумя буквами Д четно.
Аналогично, то же верно для букв В и К, значит, расстановка У
удовлетворяет условию. Заметим также, что она нетривиальна.
Действительно, если бы она состояла из одинаковых букв, на-
-50-

пример, букв Д, то расстановка Лг состояла бы из чередующихся
букв В и К, что противоречит нечетности количества точек.
Докажем теперь, что указанное соответствие действительно
является взаимно однозначным. Сначала проверим, что
расстановка У не может получаться из двух разных расстановок X и
X'. Найдем в расстановке У две разные буквы, стоящие рядом.
Между ними в расстановках Л" и X' должна стоять буква,
отличающаяся от них обеих, что определяет эту букву
однозначно. Но, как легко убедиться, если X и X' совпадают хотя бы
в одной букве, то они должны совпадать всюду. Наконец,
докажем, что любая нетривиальная расстановка У,
удовлетворяющая условию, может быть получена из некоторой
расстановки X. Поставим между каждой парой соседних различных букв
расстановки У букву, отличающуюся от них. Для каждого
интервала расстановки У, состоящего из одинаковых букв, мы тем
самым зафиксировали буквы около его концов. Чтобы получить
искомую расстановку X, достаточно расставить между буквами
каждого такого интервала две отличные от них буквы так,
чтобы они (включая уже имеющиеся буквы около концов)
чередовались. Если для какого-то интервала это невозможно, то имеет
место один из двух случаев:
1) интервал состоит из нечетного числа одинаковых букв и
заключен между двумя одинаковыми буквами или
2) интервал состоит из четного числа букв и заключен между
разными буквы.
Первый случай немедленно вступает в противоречие с
условием. Во втором случае занумеруем отмеченные точки так, чтобы
точки рассматриваемого интервала расстановки У имели номера
от 2 до 2т -f 1. Пусть, для определенности, в точке 1 стоит буква
Д, в точках от 2 до 2га + 1 - буква В, в точке 2т + 2 - буква К.
Докажем, что для любого п буквы в точках 2п и 2п -f 1
одинаковы. Индукция (база - п ^ т). Пусть п > т. Рассмотрим дугу,
последняя точка которой - 2п +1, а первая - 1, 2т +1 или 2т -f 2,
в зависимости от того, Д, В или К стоит в точке 2п + 1. Если
выполняется предположение индукции, т. е. буквы в каждой паре
точек 2 и 3, ... , 2п - 2 и 2п — 1 одинаковы, то на рассматриваемой
дуге, кроме точки 2п, имеется четное число букв, отличных от
концов. Чтобы это свойство сохранилось для всей дуги, буква
в точке 2п должна быть такой же, как в концах дуги, т. е.
совпадать с буквой в точке 2п + 1. Утверждение доказано.. Применив
-51-

его к п = 500, получим противоречие. Это заканчивает проверку
взаимной однозначности соответствия.
Осталось найти количество расстановок, в которых любые две
соседние буквы различны. Пусть xv - количество таких
расстановок в п отмеченных точках. Непосредственно проверяется, что
х2 = #з = С. Выделим три подряд стоящие точки А, В и С из п
отмеченных. Расстановки бывают двух видов: те, в которых буквы
в точках АиС различны, и те,в которых они одинаковы.
Расстановки первого вида получаются из правильных расстановок букв
вп-1 точках (всех, кроме В) добавлением (единственно
возможной) буквы в точке В. Расстановки второго вида получаются из
правильных расстановок букв в п — 2 точках (всех, кроме А и В)
добавлением в точке А такой же буквы, какая стоит в С, и
добавлением в точке В одной из двух других букв. Отсюда следует
формула хп = жп_1 + 2.г'п_29 из которой по индукции выводится,
что хп = 2" + 2 для четных п и хп = 2П — 2 для нечетных п.
♦ Каков ответ в исходной задаче для 1000 точек?
85. Ответ: выигрывает первый игрок.
Известная задача об игре со спичками (без обменов на ириски)
уже несколько веков кочует по книгам, посвященным
математическим развлечениям. Впервые она появилась, вероятно, в книге
Гаспара Клода Баше де Мезириака (1581-1638) "Игры и
задачи, основанные на математике" (Bachet C.-G. Problemes plaisans et
delectables qui se font par les nombres. Paris, 1612). Однако
предложенная на олимпиаде задача не имеет столь длинной бороды.
Когда у вас на руках много спичек, вы получаете возможность в
невыгодном положении ничего из кучи не брать. Это
обстоятельство существенным образом отличает эту игру от игры Баше.
Предъявим выигрышную стратегию для первого игрока. Если
перед очередным его ходом в куче больше 16 спичек, то первый
игрок должен взять пять спичек. За один ход первый и второй
игроки вместе берут не более 10 спичек, поэтому в какой-то
момент первому игроку (впервые) предстоит делать ход, когда в
куче будет от 7 до 16 спичек. Отметим, что в этот момент у
первого игрока будет на руках не меньше спичек, чем у второго.
Если в куче оказалось от 7 до 11 спичек, то первому следует взять
столько спичек, чтобы в куче осталось 6 спичек. Это приведет
к выигрышу первого игрока, потому что брать спички в такой
ситуации - проигрыш для второго игрока, а возможностей
обмена у него не больше, чем у первого. Если в куче остается 12-15
-52-

спичек, то первому следует взять пять спичек. Ответным ходом
второй не может оставить в куче меньше шести спичек (это
проигрыш), значит, он возьмет не 5 спичек, а тогда у первого есть
преимущество по числу возможных обменов, поскольку
количество спичек у него, в силу нашей стратегии, делится на 5, а у
второго игрока спичек меньше (хотя бы за счет последнего
хода). Осталось разобрать случай, когда в куче 16 спичек. В этот
момент из кучи взято 650 спичек, значит, у первого не меньше
325 спичек. Первому следует в этом случае взять четыре
спички. После ответного хода противника в куче останется от 7 до 11
спичек, первый возьмет одну или больше (чтобы в куче осталось
6 спичек) и будет иметь не менее 330 спичек, что опять дает ему
преимущество в обменах, так как обмены начинает второй.
86. Заметим, что ZEFC = /.ЕСА,
как опирающиеся на одну дугу окружности
ECF, а /.ЕСА = ZED В, так как
четырехугольник ADEC вписанный. Таким
образом, LEFC = Z.EDB. Значит, прямые АВ и
CF параллельны. Обозначив через G точку д
пересечения прямых CF и В А', а через G\~
точку пересечения прямых АЕ и CF, мы видим, что в
треугольнике АВК медиана DK делит прямую CG, параллельную
основанию, на два равных отрезка. Значит, CF = CG. Аналогично
прямые АЕ, DE и BE высекают на прямой CF два равных
отрезка. Значит, CF = FG\. Поэтому точки G и G\ совпадают, и
прямые ВК, АЕ и CF пересекаются в точке G.
87. Ответ: да, можно.
Решение 1. Можно считать, что центры кубиков
расположены в точках (&*,?/, z), я, у, z G Z, 0 ^ x,y,z ^ 7. Отметим все
клетки, центры которых имеют сумму координат, краткую
восьми. Нетрудно сообразить, что таких клеток будет ровно 64, по 8
в любом слое, параллельном грани. Допустим, что нам удалось
выбрать восемь отмеченных клеток, никакие две из которых не
лежат в одном слое, параллельном грани. Тогда сумма
координат этих клеток должна быть равна утроенной сумме чисел от 0
до 7. Этого не может быть, поскольку это число не делится на 8.
Решение 2. Отметим в каждом горизонтальном слое 8
кубиков таким образом, чтобы никакие два кубика этом слое не
находились "в одной строке" или "одном столбце", и чтобы ни один
из кубиков, расположенных в первых семи слоях,не был распо-
-53-

ложен ни под одним из кубиков восьмого слоя. Например, можно
считать, что кубики в первых семи слоях стоят по диагонали,
а в восьмом ~ по сдвинутой диагонали. Вид сверху показан на
рисунке. Если мы уже выбрали 7
отмеченных кубиков в первых семи горизонтальных
слоях так, что никакие два из них не
лежат в одном слое, то положение кубика в
восьмом слое, при котором он не попадает
в один слой ни с каким из уже выбранных
кубиков, определяется однозначно, причем в
силу сделанного выбора расстановки в
восьмом слое, этот кубик будет неотмеченным.
♦ В клетках доски п х п расставлено несколько шашек так, что
на каждой горизонтали и на каждой вертикали стоит т шашек
(при этом на одной клетке может стоять сразу несколько шашек).
Докажите, что шашки можно раскрасить в га цветов так, чтобы
ни на какой вертикали и горизонтали не стояло бы двух шашек
одного цвета.
♦ Рассмотрим множество всевозможных пхп матриц с
неотрицательными вещественными элементами, в которых сумма
элементов любой строки и любого столбца равна 1. Множество
таких матриц можно отождествить с некоторым выпуклым много-
гранинком^ пространстве W1 . Теорема Виркгофа - фон Неймана
утверждает, что вершины этого многогранника - это
всевозможные перестановочные матрицы, то есть матрицы, в каждой
строке и каждом столбце которых содержится ровно одна единица, а
остальные элементы нули. Эта теорема следует из
вышеприведенной задачи.
Для "трехмерных" матриц ситуация совершенно иная.
Множество "кубических" "неотрицательных" матриц с одинаковой
суммой элементов по всем слоям является многогранником, среди
вершин которого "подстановочные" матрицы составляют лишь
малую часть. Именно этим объясняется то, что конструкция
решения 2 имеет такую степень свободы.
88. Ответ: данному уравнению удовлетворяют только
константы.
Воспользуемся данным равенством, подставив его самого в
себя несколько раз:
Р(х,у) = Р(х + у,х - у) = Р((х + у) + (у - х),(у - х) - (х + у)) =
-54-

= P(2y, -2a;) = P(2(-2i), -2(2;/y)) =P(-4:c, -4y)= .. . = P(16*, 16y)<
Отсюда следует, что при всех m € N Р{х,у) = Р(16тя, 16wt/).
Проверим, что непостоянный многочлен не может
удовлетворять такому соотношению. Действительно, пусть Р(х,у) =
]Cfc=o9fc(ffiy)i гДе Чк{'х,у) ~ однородный многочлен степени А;,
qn "ф. 0. Выберем числа жо, </о так, чтобы <7п(-'Г(ь2/о) 7^ 0. Тогда
п
Р(хо,Уо) = Р(16тх0,16*пуо) = J21&1стЯх(х0,Уо) •
Правая часть последнего выражения представляет собой
многочлен (степени не меньше 1) от 16т, с ростом т она стремится к
бесконечности, чего не может быть, так как левая часть при этом
фиксирована.
89, Докажем это неравенство по индукции. При п = 1 имеем
очевидное равенство. Пусть п>1и для всех меньших значений
неравенство уже доказано. Пусть ~£* - сумма векторов из левой
части неравенства. Векторы, которые образуют с "5* угол от 0°
до 180° (против часовой стрелки), начнем поворачивать по ча-
►
совой стрелке, от этого проекция суммы всех векторов A-zi-iAn
на вектор "5* будет возрастать. Векторы, образующие с ~5* угол
от 0° до —180°, будем поворачивать против часовой стрелки, от
этого проекция суммы всех векторов A-2i-iA2i на вектор "5*
также будет возрастать. В результате этих поворотов мы сумеем
добиться того, чтобы конец какого-нибудь из векторов совпал с
началом следующего за ним по часовой стрелке вектора (в
противном случае, нам удалось бы, ни разу не совместив концы
векторов, сделать всех их параллельными вектору ~5*. Это возможно
только если у нас всего один вектор). Поскольку проекция
суммы интересующих нас векторов на вектор ~5* увеличилась, то,
следовательно, увеличилась и длина самой этой суммы. Теперь
мы можем заменить два склеившихся вектора на их сумму и
применить предположение индукции.
90. Заметим, что при всех четных п d(n2 + 1) < п.
Действительно, так как число п2 + 1 не является точным квадратом, то
все его делители можно разбить на пары вида (d, (п2 + l)/d), где
d < iiy причем d - нечетно. Количество натуральных чисел во
всех таких парах очевидно не превосходит п.
-55-

Допустим теперь, что при п ^ N последовательность d(n2 -f 1)
монотонна, обозначим S = d(N2 + 1). Так как d(n2 -f 1) всегда
четно, то при всех п d((n -f l)2 -f 1) ^ d(n2 -f 1) -f 2 или, в более
общем виде, d((n+k)2+l) ^ r/(n2-fl)-f2A:. Возьмем любое s > N—6
(такое, чтобы N -f $ было четным). Тогда
d((N + s)2 + 1) > d{N2 + l) + 28 = 6 + 2a>N + 8,
что противоречит неравенству d(n2 + 1) < п.
91. Ответ: да, может.
Мы будем использовать то, что 169 = 132. Рисунок был
задуман как пояснение того, как можно организовать дежурство
тринадцати человек. Здесь вершины-"колесики" соответствуют
дружинникам, а эллипсы, окружности и прямые - дежурствам.
Нетрудно проверить, что на каждой из упомянутых линий лежит
ровно четыре вершины и любые две вершины лежат ровно на
одной общей линии.
Эту же конструкцию можно реализовать так: пронумеруем
дружинников числами от 0 до 12, и для каждого к от 0 до 12
рассмотрим четверку, состоящую из дружинников с номерами &,
-56-

/с -f 2, fc-ЬЗ, А:4-7 (сложения по модулю 13). Нетрудно проверить,
что любые два дружинника входят вместе ровно в одну четверку.
Теперь покажем, как можно организовать дежурства 169
человек. Разобьём этих дружинников на 13 бригад по 13 человек;
по-прежнему будем нумеровать дружинников числами от 0 до 12,
так же пронумеруем и сами бригады. Для каждой бригады
реализуем предложенную выше схему разбиения на четверки. Мы
получим, что любые два дружинника из одной бригады
дежурили вместе ровно один раз. Для того чтобы обеспечить такое
же свойство для дружинников из разных бригад, для каждого
целого п от нуля до 12 построим разбиение дружинников,
скажем, на группы захвата, а именно: в одну группу захвата с к-и
дружинником из нулевой бригады поместим (к + га)-го
дружинника из первой бригады, (к -f 2га)-го дружинника из второй
бригады, и т.д., (к -f 12п)-го дружинника из двенадцатой бригады (все
сложения по модулю 13). Очевидно, что при фиксированном п
это действительно разбиение всех дружинников на 13
непересекающихся множеств, и любые два дружинника из разных бригад
при ровно одном значении п оказываются в одной группе захвата
(чтобы найти это п для р-го дружинника из r-й бригады и q-ro
дружинника из 5-й бригады, нужно решить по модулю 13
уравнение р -f ($ — r)n = д). Теперь достаточно для каждой группы
захвата опять использовать схему, изображенную на рисунке.
♦ Решите эту же задачу, если дружинников 40,
♦ Конструкция для 13 человек, приведенная выше на рисунке,
представляет собой конечную проективную плоскость третьего
порядка. А конструкция для 169 человек - это пример
уравновешенной неполной блок-схемы. См. об этом Холл М.
Комбинаторика. М., 1970, гл. 10, 12; Болл У., Коксетер Г. Математические
эссе и развлечения. М., 1986, гл. X. В этой книге есть более
наглядный чертеж обсуждавшейся конструкции (с. 305).
91. Ответ: нельзя.
Допустим, что нам удалось построить требуемую
расстановку. Будем считать, что буквы стоят в центрах клеток. Соединим
центры клеток, соседних по вертикали или горизонтали, кроме
того, соединим центры клеток, соседних в диагональном
направлении "слева сверху — вправо вниз"; отрезки, соединяющие
центры соседних клеток, будем называть звеньями. Мы получили
треугольную сетку, в которой каждый маленький треугольник
соответствует фигурке вида П-i или ЦП из условия.
-57-

Решение 1 (четность). Заметим, что если каждый
маленький треугольник не содержит трех букв, то количество звеньев
вида А—С в нем четно. Значит, суммарное количество звеньев
А—С, встречающихся во всех маленьких треугольниках, тоже
четно. При этом каждое звено, расположенное внутри квадрата,
мы учитываем ровно дважды, а звенья, лежащие на границе, -
один раз. Осталось заметить, что звенья вида А—С на границе
могут встречаться только в верхней строке, и их там ровно т.ри.
Противоречие.
Решение2 (деформацияпутей).* Каждому ориентированному
пути, соединяющему центры двух клеток и проходящему по
линиям сетки, сопоставим целое число по следующему правилу:
каждому ориентированному звену, по которому проходит наш путь,
сопоставим "вес" - число +1, если это звено ведет от буквы П к
А, от А к С, или от С к П; —1, если это звено ведет от буквы А к
П, от С к А, или от П к С; 0, если это звено соединяет
одинаковые буквы. Число, соответствующее пути, - это сумма весов его
звеньев.
Деформацией пути назовем следующее преобразование:
заменим произвольное звено нашего пути на два звена, проходящих
по сторонам треугольника сетки, примыкающего к этому ребру,
или наоборот: заменим два ребра на одно. Докажем, что при
деформации пути его вес не меняется. Действительно, в
вершинах любого треугольника сетки стоит не более двух различных
букв. Если все буквы одинаковые, то все звенья, участвующие в
обмене, имеют нулевой вес. Если есть две различные буквы, то
либо удаляемое звено имеет вес 0, а добавляемые - веса +1 и —1,
либо удаляемое звено имеет вес ±1, а добавляемые - вес ±1 и 0.
Рассмотрим путь, идущий от левого верхнего угла нашего
квадрата в правый верхний угол по верхней стороне квадрата. Его
вес равен 4. Не составляет труда продеформйровать этот путь
так, чтобы он шел по трем другим сторонам квадрата.
Поскольку на этих сторонах нет буквы С, вес продеформированного пути
равен 1. Противоречие.
РешениеЗ (компоненты связности). Все буквы С
разбиваются на компоненты связности, внутри которых можно
перемещаться по ребрам нашей треугольной сетки. Для каждой компоненты
задевающие ее треугольники образуют некоторую область,
граница которой представляет собой одну или несколько ломаных с
буквами А и П в вершинах (за исключением, возможно, вершин
-58-

с буквами С на краю квадрата). Любые две соседние вершины
на такой ломаной принадлежат треугольнику, в котором есть
буква С, поэтому в этих двух вершинах должны стоять одинаковые
буквы. Таким образом, на каждой граничной ломаной (точнее,
на каждом ее участке, остающемся после выкидывания краевых
букв С) все буквы одинаковы.
Рассмотрим компоненту, содержащую первую из букв С
первой строки. Если в ней нет других краевых букв С, то она
ограничена ломаной, соединяющей буквы А и П справа и слева от С.
Если эта компонента содержит вторую букву С, то ее граница
содержит ломаную, соединяющую буквы П и А справа от первой
и слева от второй буквы С. Если же она не содержит вторую
букву С, но содержит третью, то вторая буква С лежит в
компоненте, не содержащей других краевых букв С, и граница этой
второй компоненты содержит ломаную, соединяющую буквы А и
П слева и справа от второй буквы С. Во всех случаях мы
получили граничную ломаную с разными буквами, что противоречит
доказанному выше.
♦ Нарисуем окружность и отметим на ней три точки А, П и С
в вершинах правильного треугольника. Построим непрерывное
отображение нашей треугольной сетки в окружность, отобразив
узлы в отмеченные точки в соответствии с буквами, а ребра - в
дуги окружности между ними. Если нет треугольников с тремя
разными буквами, то это отображение продолжается до
непрерывного отображения квадрата в окружность. Легко убедиться,
что индекс (или степень, или количество оборотов вокруг
окружности) границы квадрата при этом отображении равен единице
(сравните с решением 2). Но отображение с ненулевым индексом
не может продолжаться до отображения квадрата в окружность.
Это утверждение является одной из формулировок известных
топологических теорем Брауэра и Борсука. О связанных с этим
вопросах можно прочитать в книгах Шишкин Ю.А.
Неподвижные точки. М.: Наука, 1989 (Популярные лекции по математике,
вып. GO), Прасолов В.В. Наглядная топология. М/. МЦНМО, 1995.
Приведенные решения имеют много общего с классическими
методами топологии. Первое аналогично лемме Шпернера,
второе использует идеи теории гомотопий, третье похоже на
доказательство теоремы Борсука, данное Дж. Милнором (см. Милнор
Дж,., Уоллес А, Дифференциальная топология. Начальный курс.
М.: Мир, 1972).
-59-

93. Мы воспользуемся следующим хорошо известным
равенством :
2 + 2 = 2-2. (1)
Поскольку три подряд стоящих числа на окружности - это две
единицы и двойка, либо две двойки и единица, то равенство (1)
показывает, что произведение трех подряд стоящих чисел вдвое
больше количества двоек среди них. Следовательно, искомое
произведение равно удвоенному количеству двоек во всех
тройках подряд стоящих чисел, что в шесть раз больше числа двоек
на окружности. Ответ: 180.
В* 94. Пусть S - точка пересечения перпен-
/\ дикуляров, проведенных из точек МиА',Г-
/ \ точка пересечения перпендикуляров, прове-
K&^^TjbsN денных из точек М и N. Четырехугольник
A^Mvf \ AMSK вписанный, поэтому
А М с ISAM = ZSKM = Z.BKM - 90°.
Аналогично, /ГСМ = Z.BNM - 90°. Итак, LSAM = Z.TCM.
Вспоминая теперь, что точки 5 и Т лежат на серединном
перпендикуляре к отрезку АС, мы видим, что они совпадают. Разбор
различных случаев взаимного расположения точек оставляем
читателю.
95. Пусть V - та вершина, из которой выходили два
удаленных ребра, будем считать, что она первого цвета. Рассмотрим
компоненту связности, в которую попала вершина V после
удаления ребер. Обозначим А\-\ >b, Лз, А* - множества вершин
соответственно первого, второго, третьего, четвертого цветов в этой
компоненте. Заметим, что из А2 в А\, А% и А* до выкидывания
вело поровну ребер, обозначим это количество ребер через к.
Тогда из А* и А* в. остальные множества также выходило по к
ребер. Следовательно, из А\ внутрь компоненты связности до
выкидывания вело кратное трем число ребер. Следовательно, и
за пределы этой компоненты из множества А\ вело кратное трем
число ребер. Но тогда удаление двух ребер не могло
изолировать эту компоненту, значит, она совпадает со всем графом.
96. Докажем более сильное утверждение: если
максимальная система из непересекающихся квадратов содержит не более
к квадратов, то все множество квадратов можно разбить на 2Л; — 1
-60-

подсистем, в каждой из которых все квадраты имеют общую
точку, такие подсистемы будем называть полными.
Доказательство будем проводить индукцией по к. База к = 1
очевидна. Пусть утверждение выполнено для к = £ — 1.
Докажем его для к = I. Считая, что стороны квадратов
горизонтальны и вертикальны, выберем самый нижний квадрат (или один
из нескольких самых нижних), назовем его Q. Рассмотрим все
квадраты, которые с ним не пересекаются. Для них выполнено
предположение индукции (при к = £ — 1), следовательно, их
можно разбить на 21 — 3 полных подсистем. Добавим теперь к этим
подсистемам подсистему, состоящую из квадратов, содержащих
правую верхнюю вершину квадрата <5, и подсистему, состоящую
из остальных квадратов (они все содержат левую верхнюю
вершину Q). Мы получили искомое разбиение.
97. Продолжим противоположные
стороны нашего четырехугольника до
пересечения (см. рисунок; случай
параллельных сторон проще и
оставляется читателю на доработку).
Заметим, что биссектрисы углов В и С
исходного четырехугольника - это
биссектрисы внешних углов
треугольника ВЕС. Поэтому точка К лежит на
биссектрисе угла Е. Поэтому отрезок КМ лежит на биссектрисе
угла Е. Аналогично LN лежит на биссектрисе угла F. Заметим,
что ZFPQ = LPBE + /.РЕВ = ZEDQ + Z.QED = Z.FQP.
Значит, FQ = FP, биссектриса угла F перпендикулярна отрезку PQ,
следовательно, KM _L NL. Осталось проверить, что МК и NL -
действительно диагонали выпуклого четырехугольника KLMN
(как на рисунке). Это следует из того, что отрезок МК
пересекает биссектрису угла F (так как в противном случае DM и
С К не смогли бы пересечься на этой биссектрисе) и аналогично
отрезок NL пересекает биссектрису угла Е.
98. Допустим, что мы сумели подобрать такие натуральные
числа а > с ^ d > 6, что аЪ = cd > гс4/16. Обозначим р = а + 6,
д = а — 6, r = c-f-d, « = с — d. Тогда q ^ n, р > г. Так как
р2 - q2 = 2а • 26 = 2с - 2d = г2 - s2 > n4/4, то р2 - г2 = q2 - s2
и г2 > п4/4. Заметим теперь, что q2 — s2 < q2 < га2, а с другой
стороны, р2 - г2 > (г + I)2 — г2 = 2т -f 1 > п2 + 1. Противоречие.
-61-

99. Докажем сначала утверждение задачи для центрально
симметричных многоугольников. Заметим, что каждый из них
можно разбить на п(п — 1)/2 параллелограммов, вершины
которых лежат в узлах решетки. Площадь каждого такого
параллелограмма не меньше единицы (здесь уместно припомнить
формулу Пика - см. Прасолов В.В. Задачи по планиметрии. Часть 2.
Задача 24.5. М.: "Наука", 1991; Генкин С.А., Итенберг И.В.,
Фомин Д.В. Ленинградские математические кружки. Киров, 1994.
С. 221; либо поговорить о векторном произведении двух
целочисленных векторов). Отсюда сразу следует утверждение задачи.
Теперь докажем утверждение задачи для произвольного
многоугольника. Обозначим /(п) = п(п — 1)/2. Рассмотрим
диаметр d нашего 2п-угольника, пусть он разбивает 2п-угольник на
(ft + 1)-угольник и (С + 1)-угольник, ft + £ == 2п. Выполним
центральную симметрию относительно середины диаметра d и
рассмотрим получившиеся центрально симметричные 2/г-угольник и
2<-угольник. Их площади, как доказано выше, не меньше /(ft) и
/(£), а площадь исходного 2п-угольника равна полусумме
площадей 2ft- и 2£-угольника. Так как функция / выпукла (вниз), мы
получаем требуемое.
100. Добавим к данным п векторам еще 2п векторов,
получающихся из векторов данного набора поворотом на 120° по или
против часовой стрелки. Тогда сумма всех полученных векторов
равна нулю, поэтому из них можно составить выпуклый
многоугольник, переходящий в себя при повороте на 120° относительно
некоторой точки О. Рассмотрим окружность длины 3 с центром в
точке О. Поскольку периметр нашего выпуклого многоугольника
равен трем, найдется его вершина X, лежащая вне окружности.
Пусть Y - вершина многоугольника, получающаяся из X
поворотом на 120°. Тогда XY > 3\/3/2тг. Внутри угла XOY лежит
п векторов-сторон нашего многоугольника. Разобьем их на три
множества: Sx - векторы, принадлежащие исходному набору; 5г -
векторы, полученные из исходных поворотом по часовой стрелке;
5з - векторы, полученные из исходных поворотом против
часовой стрелки. Пусть ??, Sj, Jz - суммы векторов в этих наборах.
Поскольку [St + 5? + S31 > 3\/3/2тг, то \lt\ + |*21 + |*з | > 3\/3/2тг.
Осталось заметить, что векторы исходного набора также
разбились на три подмножества: Si, векторы, которые после поворота
попадают в S2, и векторы, которые после поворота попадают в
S3. Это разбиение и будет искомым.
-62-

103. Ответ: не существуют. Допустим, что мы нашли
требуемые Р и к. Выберем натуральное з\ при котором |P(fce)| > 1.
Пусть q - любой простой делитель Р(к8). Тогда по малой
теореме Ферма P(kqa) делится на qi чего не должно быть.
105. Заметим, что шестиугольник Л4С3В4А3С4-В3 -
описанный, так как в него легко вписывается окружность с центром /
и радиусом, равным
расстоянию от / до прямой
А\А$ (используйте
равенство хорд Ах А3 у АдА2)
BiB$, Б3В2, С1С3, C3C2).
Тогда утверждение задачи
- прямое следствие
теоремы Брианшона. См. об
этом ШклярскийД. О.,
Чепцов Н.Н.у Яглом ИМ,
Избранные задачи и теоремы
планиметрии. М.: "Наука",
1967, задача 150; Коксе-
тер Г.С.М., Грейтцер С.Л.
Новые встречи с геометрией. М.: "Наука", 1978.
106. Докажем сначала утверждение задачи для центрально
симметричных многоугольников. Пусть
ах, а2,..., ап, -аА, — а2,..., -ап
— векторы сторон многоугольника. Здесь не важен порядок
сторон, нам будет удобнее считать, что \а\\ ^ jo^j ^ • • • ^ |5^|. Наш
2га-угольник легко разбить на параллелограммы со сторонами о?
ио|,1^1<;^п,и тогда его площадь S равна
Зафиксируем г, 1 ^ г < п. Пусть gi{j) = 2|о? х Sj|. Отложим
векторы Oj,i ^j < n от начала координат. Допустим, что на вектор
"at попало fc+1 узлов решетки (включая концы). Тогда длина
вектора а? равна fcg, где q - расстояние между соседними узлами, и
при всех j ф i gi(j) - натуральное число, кратное к. Проверим,
что при j > i функция д{ принимает каждое свое значение не
более 4к раз. Действительно, пусть gi(j\) = gifo) = • • • = flft(J4*+i)-
Тогда концы векторов "ajj, "aj3, ... , "aj4fc+1 находятся на двух пря-
-63-

мых, параллельных прямой, содержащей вектор а?. По крайней
мере 2к + 1 из этих концов попадут на одну прямую. А так как
расстояние между соседними узлами на этой прямой также
равно qy то найдутся два вектора, разность которых не меньше 2fcg,
чего не может быть по неравенству треугольника в силу
упорядоченности ДЛИН CLj.
Пусть п — г = iks + r (деление с остатком на 4&). Мы доказали,
что при j > г функция щ не более 4& раз принимает значения А:,
2&, ... , sk и, значит, не менее г раз принимает большие значения.
Тогда
J2 У&) > ik(k + 2* + • • • + *fc) + rk{8 + 1) =
= 2k2 8(a + 1) + rk(s + 1) = k(2ks + r)(s + 1).
Из определения чисел $ и г видно, что 2ks+r ^ 2ks+r/2 = (п-г)/2,
и s + 1 > (п - г)/4&. Поэтому
Е,.. (п - г)2
jsst+1
Теперь легко оценить площадь многоугольника:
s» E I3?x«?i-|f:sft(j)>lf;^-
1 v4-2_ п(п + 1)(2п + 1) п3 ^1
~ 16^* ~ 96 > 48 > 100'
Докажем теперь утверждение задачи для произвольного 2п-
угольника. Обозначим f(n) = n3/100. Доказательство
завершается буквальным повторением рассуждения из второго абзаца
решения задачи 99.
♦ Оценка вида Спг - точная по порядку величины.
Докажите, что для любого п ^ 2 существует выпуклый 2п-угольник с
вершинами в узлах решетки, площадь которого не больше п3/б.
107. Докажем более общее утверждение, добавив еще один
квантор:
Vn G N Vfc e N Зе > 0 Vab..., о„ > 0 3* > 0
{ta!},...,{tan} £ (е,1/к)ф
-G4-

Доказательство будем проводить индукцией по п. База п = 1
очевидна.
Рассмотрим произвольные положительные числа, а\у а%, ... ,
ап, причем пусть ап - наибольшее из них. По предположению
индукции, найдется такое t > О, что
{tax},..., {ten-i} € (е, 1/(3*)3), где е = е(п - 1, (3ft)3).
Стандартные рассуждения в духе леммы Дирихле показывают,
что среди чисел £, 2£, ... , 9k2t найдется такое число, скажем st,
для которого {stan} € (—§р-, j^)- ^Ри этом очевидно
{stai},..., {5^an-.!} 6 (е, ^).
Возьмем небольшое а > О так, чтобы для числа Г = st + а число
{Tan} оказалось в промежутке (е, .^). Рассмотрим переменную
#, пробегающую промежуток (st,T). При движении # от stf к Т
точка хап переместилась на расстояние не более ^р- + j% < ^.
Так как an - наибольшее из данных чисел, то все остальные
точки — ха\} ... , xan~i — переместились также на расстояние не
большее jfe. Значит, мы нашли число Т, для которого все
дробные части {Tai}, ... , {Тап} попали в промежуток (б, £).
Индукционный переход доказан.
108. Построим граф Г, вершины которого соответствуют
данным квадратам, а ребра соединяют вершины, соответствующие
пересекающимся квадратам. Докажем, что граф Г можно
разбить не более чем нага — 3 полных подграфов2.
По условию, любое множество вершин графа Г содержит
полный четырехвершинный подграф. Из утверждения, доказанного
в задаче 96, сразу следует, что любой подграф графа Г,
максимальный пустой подграф3 которого содержит к вершин, можно
разбить на 2к - 1 полных подграфов. Будем называть это
свойство свойством разбиваемости.
Пусть максимальный пустой подграф Гь содержащийся в Г,
имеет 1\ вершин; максимальный пустой подграф Г2,
содержащийся в Г \ Г*1, имеет £2 вершин; максимальный пустой подграф,
содержащийся в Г \ Г*1 \ Г2, имеет £3 вершин. Очевидно
4+/2 + *з<п-1. (*)
2Под разбиением графа мы понимаем разбиение множества его вершин.
Зт. е. не содержащий ни одного ребра.
-65-

Нам понадобится следующая лемма.
Лемма. Пусть Т - двудольный граф, доли которого содержат
5i и 82 вершин (s\ ^ S2), а максимальный пустой подграф
содержит 5i вершин. Тогда Т можно разбить на si полных подграфов
(каждый из которых содержит одну или две вершины).
Доказательство. Каждая вершина первой доли войдет
ровно в один подграф. Возможность разбиения следует из леммы
о девушках (т. е. теоремы Холла о паросочетаниях), не забудьте
воспользоваться условием о максимальном пустом подграфе. П
В силу леммы, граф Т\ U Г% можно разбить на 1\ полных
подграфов, а граф Г\(1\ U T'z) ~ в силу свойства разбиваемости - на
2*з - 1 полных подграфов. Значит,
*1 + 2*3 - 1 > п - 1 (**)
(иначе мы сразу найдем искомое разбиение). Сравнивая
неравенства (*) и (**) и пользуясь тем, что *2 ^ *з, находим, что
*2 = *3-
Заметим теперь, что граф Г\Г*1, опять в силу свойства
разбиваемости, можно разбить на 2*2 — 1 полных подграфов. Покажем,
что тогда граф Г можно разбить на 1\ + 2*2 — 2 полных
подграфов. Рассмотрим одну из компонент разбиения Г \ 1\ на 2*2 - 1
полных подграфов, назовем ее П. Пусть ai - любая из 1\
вершин графа IV Выделим компоненту, состоящую из ai и всех
вершин подграфа П, соединенных с ней. Затем рассмотрим
любую другую вершину а2 £ Т\ и выделим компоненту, состоящую
из с*2 и всех ещё не выделенных вершин П, соединенных с ней.
Будем выполнять подобные операции со всеми вершинами IV В
результате каждая вершина Q окажется выделенной, поскольку
существование вершины О, не соединенной ни с одной вершиной
из Гь противоречит максимальности графа Т\. Таким образом,
мы построили разбиение графа Г на не более чем *i 4-2*2 — 2
полных подграфов. Вспоминая, что *2 = *3, получаем, что искомое
разбиение содержит
*! + 2*2 - 2 = *i + *2 + *3 - 2 ^ п - 3
компонент (мы использовали ещё раз неравенство (*)).
-66-

Подписано в печать с оригинала-макета 6.04.98.
Ф-т 60 х 84/16. Печать офсетная.
Усл.печ.л.3,95. Уч.-изд.л.3,38. Тираж 1000 экз. Заказ Y5V,
РОПИ Издательства СПбГУ. 199034, Санкт-Петербург,
Университетская наб., 7/9.
Типография Издательства СПбГУ.
199034, С.-Петербург, Университетская наб., 7/9.

Оргкомитет и жюри Санкт-Петербургской олимпиады
школьников по математике приглашают всех, кто
заинтересован в процветании точных наук и хотел бы оказать
олимпиадам по математике, физике, химии и
информатике финансовую поддержку. Звоните по телефону 310-30-39
(оргкомитет олимпиады).