/
Автор: Иванов С.В. Кохась К.П. Берлов С.Л.
Теги: математика задачи по математике школьная математика математические олимпиады
Год: 1998
Текст
САНКТ-ПЕТЕРБУРГСКОЙ ГОСУДАРСТВЕННЫЙ УНйВЕРСНТЕТ
Задачи
Санкт-Петербургской
олимпиады школьников
по математике
Составители: С.Л.Берлов, С.В,Иванов, К.П.Кохась
e-mail:
крк@кк1437. spb. edu
svivanov@pdmi .ras.ru
СОДЕРЖАНИЕ
Победители олимпиады 1998 года..................... 2
Статистические данные олимпиады 1998 года.......... 5
Задачи первого тура, 6—11 классы....................б
Задачи второго тура, 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 часов.
В этом году в составлении вариантов олимпиады участво-
вали: Ю.М.Базлов, С.Л.Берлов, А.С.Голованов, М.Н.Гусаров,
С.В.Иванов, Р.А.Исмаилов, Д.В.Карпов, К.П.Кохась, О.Г.Мале-
ва, А.В.Пастор, М.Я.Пратусевич, Р.А.Семизаров, А.И.Храбров.
Много сил в организацию олимпиады вложили Л.А.Жигулев,
В.В.Крылов. Проведение олимпиады также было бы невозможно
без помощи многочисленных энтузиастов: студентов, учителей и
преподавателей вузов, вложивших свой труд в проведение всех
туров олимпиады.
Финансовую поддержку олимпиаде оказал Ю.О.Латов, на
средства гранта ФЦП “Интеграция” изготовлены призы для по-
бедителей олимпиады - футболки с символикой олимпиады (фир-
ма “Appii”, ул. Блохина д. 6, тел. 233-12-52).
- 1 -
ПОБЕДИТЕЛИ ОЛИМПИАДЫ 1998 ГОДА
|б КЛАСС! Школа Район
1 диплом Аверьянов Петр 105 Выб.
Антипов Дмитрий 261 Кир.
Дворкин Михаил 582 Прим.
Зинченко Дмитрий 30
2 диплом
Антонов Сергей 76 Выб. Иванов Александр 30
Белокопытов Артем 366 Моск. Назаров Максим 238 Адмир.
Вальтман Виталий 610 Петр. Синев Игорь 468 Выб.
Гравии Николай 366 Моск. Солодуха Иван 344 Нев.
Гутов Дмитрий 489 Моск. Чихачев Кирилл 166 Центр.
3 диплом
Артеменко Николай 30 Семенов Вадим 73 Выб.
Груздев Михаил 205 Фрунз. Сикулер Ярослав 41 Прим.
Дубашинский Мих. 527 Нев. Кузнецов Антон 144 Калин.
Железнов Дмитрий 43 Прим. Струкова Ольга 159 Калин.
Смирнов Александр 596 Прим. Преснова Алена 261 Кир.
Храбрый Александр 636 Центр. Ширяев Дмитрий 207 Центр.
|7 КЛАСС1
1 диплом Антипов Дмитрий 261 Кир.
2 диплом Захарова Виктория 642 В.О.
Панферов Василий 1
Сухов Кирилл 470 Калин.
3 диплом Власов Всеволод 642АГ В.О.
Клименко Виктор 187 Кргв.
Новицкий Михаил 52 Прим.
Филиппов Вячеслав 98 Калин.
- 2 -
Похвальный отзыв 1-й степени
Белянцев Алексей 196 Кргв. Смирнов Кирилл 38 Прим.
Иваньков Никита 366 Моск. Тирских Юлия 30
Иванова Вера 580 Прим. Хитров Виталий 30
Мухина Ольга 66 Прим. Цыбанев Максим 147 Кргв.
Руцкий Дмитрий 30
|8 КЛАСС]
1 диплом Смирнов Филипп 239
2 диплом Варягин Андрей 239
Me двинский Михаил 366 Моск.
3 диплом Бондарева Елена 239
Мясников Родион 239
Привалов Игорь 239
Похвальный отзыв 1-й степени
Васильев Антон 30 Сафарова Юлия 239
Воробьев Андрей 239 Сергеева Ольга 239
Ефремов Алексей 239 Солощева Елена 239
Назаров Антон 239 Трофимов Вадим 292 Фр.
Оршанский Сергей 239 Чашников Николай 239
Паперно Денис 642 В.О. Эфроимский Борис 239
|9 класс!
1 диплом Смирнов Филипп 239
2 диплом Ваганов Никита 239
Лифшиц Юрий 239
Me двинский Михаил 366 Моск.
Тихомиров Сергей 239
Федотов Алексей 239
3 диплом Грибов Александр 239
Ицыксон Дмитрий 239
Крысталь Борис 239
Незлобии Александр ФТШ
Привалов Игорь 239
Пчелинцева Ирина 98 Калин.
-3-
|10 КЛАСС I
1 диплом Петров Федор 239
2 диплом Назаров Александр Проскурников Антон Ушаков Егор Фарутин Александр г. Нарва 239 239 G10 Петр.
3 диплом Ананьевский Михаил АЛ
Буртный Павел 239
Кургузов Леонид 239
|11 КЛАСС |
1 диплом Беленький Алексей 239
Дуров Николай 239
Розенберг Антон 419 П/дв.
2 диплом Барыгин Илья ФТШ
(4-5 место) Етеревский Олег 239
2 диплом Бахарев Федор 239
(G--13 место) Белов Юрий 239
Егоров Арсений 30
Зильбербург Константин 239
Машевский Александр 239
Мельник Сергей 239
Сопкина Екатерина 239
Франк Владислав 239
3 диплом Железняк Александр 239
Короткевич Алексей АЛ
Левина Анна 239
Лопатин Андрей 238 Адм.
Малкин Юрий 30
Мнев Павел 610 Петр.
Мясников Андрей 239
-4 -
СТАТИСТИЧЕСКИЕ ДАННЫЕ ОЛИМПИАДЫ 1998 ГОДА
Критерий пропуска на второй тур олимпиады
класс число задач 6 7 8 9 10 11
2.5 3 3 4” 3- 3
второй тур
В левой таблице по каждой задаче приведено количество ре-
шивших ее участников; также указано общее количество пригла-
шенных на олимпиаду и количество прошедших в выводную ау-
диторию. В правой таблице указано количество участников, ре-
шивших данное число задач.
Номер задачи Всего Вывод Количество задач
1 2 3 4 5 6 7 1 2 3 4 5 6 7
6 кл. 89 79 56 20 17 12 — 107 60 15 18 31 11 10 4 —
7 кл. 70 29 14 9 3 6 10 95 39 35 20 9 4 3 1 0
8 кл. 31 39 27 17 1 3 1 97 18 31 12 12 3 2 1 0
9 кл. 56 32 17 33 6 1 1 84 26 21 13 14 6 5 1 0
10 кл. 39 24 23 20 5 2 0 74 21 12 12 13 3 4 1 0
11 кл. 68 49 47 21 18 11 3 106 36 21 24 16 7 8 2 3
отборочный тур
Номер задачи Количество задач
12345678 12 3 45678
9 кл. 21 9 15 9 7 3 2 0 25 4 4 7 4 3 0 0 0
10 кл. 12 10 4 5 5 2 1 0 17 6 3 1 3 1 0 1 0
11 кл. 10 9 6 10 4 8 2 1 14 3 2 1 3 3 1 1 0
- о -
?, чем ноликов,
ЗАДАЧИ ПЕРВОГО ТУРА, 6-11 КЛАССЫ
В квадратных скобках помещены сведения о втором вариан-
те. Все задачи давались на олимпиаде без рисунков. Рисунки
добавлены для удобства читателя.
6 КЛАСС
1. Расставьте крестики и нолики в квадрате 5x5 клеток так,
чтобы в каждой строке, кроме, быть может, первой, крестиков
было бы больше, чем ноликов, а в каждом столбце кроме, быть
может, последнего, ноликов было бы больше, чем крестиков [в
каждом столбце, кроме, быть может, первого, крестиков было
а в каждой строке, кроме, быть может,
последней, ноликов было бы больше,
чем крестиков]. (ЯЛ Базлов)
2. Винни-Пух, Сова, Кролик и Пя-
тачок съели 70 бананов [85 желудей],
причем каждому досталось хотя бы
по одному банану [желудю]. Винни-
Пух [Пятачок] съел больше, чем ка-
ждый из остальных; Сова и Кролик
вместе съели 45 бананов [55 желудей].
Сколько бананов [желудей] съел Пя-
тачок [Винни-Пух]? (К. Кохасъ)
3. На доске написано число 23 [81]. Каждую минуту число
стирают с доски и записывают на его место произведение его
цифр, увеличенное на 12 [15]. Что окажется на доске через час?
Не забудьте обосновать ответ. (4. Голованов)
4. Можно ли в квадрате 10 х 10 клеток так расставить на-
туральные числа, чтобы при любом расположении фигурки вида
сумма чисел в ее пяти клетках была равна 105 [155],
а в каждой фигуре вида Ш или £] сумма чисел была равна 40
[60]? Не забудьте обосновать ответ. (О. Малева)
( КЛАСС
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 - g / Т
середина отрезка AF, Е точка пересечения
прямой CD со стороной АВ. Оказалось, что
BD = BF = CF. Докажите, что АЕ = DE. А С
[AF медиана треугольника АВС. На про- А
должении стороны АВ за точку В отмече- /lb,
на точка D. Е - точка пересечения пр я- /
мой DF со стороной АС. Оказалось, что
АВ = BD = AF. Докажите, что СЕ = EF.]
(С. Берлов)
12. Из прямоугольника на клетчатой бумаге можно вырезать
(по клеточкам) 360 квадратов 2x2. Докажите, что из него можно
вырезать 200 [280] прямоугольников 1 х 7 [1 х 5]. (Л. Голованов)
9 КЛАСС
13. Найдите наименьшее положительное число х, удовлетво-
ряющее неравенству [.г] • {х} 3 [ [х] * {х} 4 ]. Как обычно,
[ж] обозначает целую часть х, {х} = х — [х] - дробная часть х.
(Л. Храбров)
-7-
14. Сумма четырех корней квадратных трехчленов f и д с
одинаковыми старшими коэффициентами равна нулю. Трехчлен
f 4- д имеет два корня. Докажите, что сумма этих корней так-
же равна нулю. [/ и д - квадратные трехчлены с одинаковыми
старшими коэффициентами, имеющие по два корня. Сумма двух
корней трехчлена f 4- д равна нулю. Докажите, что сумма всех
четырех корней трехчленов f и д равна нулю.] (С. Берлов)
15. Из множества натуральных чисел от 1 до 1000 [500] выбра-
но 860 [430] чисел. Докажите, что произведение каких-то двух из
них делится на 21 [35]. (С. Берлов)
16. Точки К и L на сторонах АВ и
АС остроугольного треугольника АВС та-
ковы, что KL || ВС. М - точка пересече-
ния перпендикуляров, восставленных в точ-
ках К и L к отрезкам АВ и АС. Докажите,
что А, М и центр О описанной окружности
треугольника АВС лежат на одной прямой.
[А' - точка пересечения перпендикуляров,
восставленных в вершинах А и С остро-
угольного треугольника АВС к отрезкам АВ
и ВС. На сторонах АВ и ВС взяты точки L
и М так, что LM || АС. Докажите, что точки
В, Л’ и центр О описанной окружности тре-
угольника BLM лежат на одной прямой.]
(А. Храбров)
17. В клетках таблицы 100 х 100 расставлены числа. Известно,
что в каждой строке можно выбрать не менее 10 различных чисел,
а из любых двух соседних строк нельзя выбрать больше 15 [16]
различных чисел. Докажите', что в таблице всего не более 505
[604] различных чисел. (С. Иванов)
10 КЛАСС
18. Положительное число .г удовлетворяет неравенству
[а:]2 - х[а;] 4-3^0 [ [а:]2 — афг] 4- 4 0 j .
Докажите, что х 4.75 [5.8]. Как обычно, [ж] обозначает целую
часть числа х. (А. Храбров)
19. В Клубе Любителей Вкусной Еды состоят 58 человек [62
человека], причем каждый из них - либо толстый, либо тонкий.
-8-
На очередное заседание каждый толстый член клуба принес 15
пончиков и раздал их тонким, а каждый тонкий принес 14 [16]
пончиков и раздал их толстым. Оказалось, что все толстые чле-
ны клуба получили поровну пончиков и все тонкие - тоже. Сколь-
ко среди членов клуба толстых и сколько тонких? Приведите все
возможные ответы и докажите, что других нет. (Л. Голованов)
20. Две дробно-линейные функции /(х) и д(х) таковы, что
/(.т) — </(#) > 1997 [f(x) + д(х) < 1997] для всех ж, при кото-
рых обе функции определены. Докажите, что функция /(.г) — д(х)
[/(./’) + У(х)] постоянна на своей области определения (напо-
мним, что дробно-линейной функцией называется частное двух
линейных функций). (4. Голованов)
21. В выпуклом четырёхугольнике ABCD
диагонали АС и BD равны. Кроме того,
/ВАС = /ADB, /CAD + /ADC = /ABD
[/ВАС = /CBD, /САВ+/СВА = /ADB].
Найдите /BAD. (4. Пастор)
22. В клетках таблицы 100 х 100 расста-
влены числа. Известно, что в каждой стро-
ке можно выбрать не менее 10 различных
чисел, а в любых трех подряд идущих строках имеется не больше
1G [15] различных чисел. Докажите, что в таблице всего не более
310 [260] различных чисел. (С. Иванов)
11 КЛАСС
23. Положительное число <г удовлетворяет неравенству
lg[x] + lg{.C}^3 [2]
Докажите, что х > 1001.998 [101.98]. Как обычно, [ж] обозначает
целую часть числа х, {я} = х — [х] обозначает дробную часть х.
(4. Храбров)
24. Арифметическая прогрессия состоит из натуральных чи-
сел и содержит бесконечно много чисел вида (2п)! [(2n + 1)!].
Докажите, что первый член прогрессии делится на ее разность.
Выражение zd обозначает произведение всех натуральных чисел
от 1 до п. (4. Голованов)
-9-
25. Докажите, что в любом тридцатипятизначном числе без
нулей и пятерок в десятичной записи [пятидес ятизначном числе
без нулей] можно вычеркнуть несколько цифр так, чтобы полу-
ченное в результате этого число делилось на 41 [271]. (Жюри)
26. Костя взял многочлен f(x) с вещественными коэффициен-
тами и стал решать уравнение /(.г) = 10 [16]. У этого уравнения
оказалось 10 [11] различных вещественных корней. А у уравнения
/(.т) = 15 [11] оказалось 15 [16] различных вещественных корней.
Докажите, что среди 25 [27] найденных Костей чисел хотя бы од-
но удовлетворяет уравнению f'(x) = 0. (А*. Кохась)
27. На ребрах AD, ВС, CCi, CiA, AiBi, АА[ куба
ABCDA\B\C\D\ выбраны точки Р, Q, В, S, Т, U соответственно.
Оказалось, что при этом
Z.PQB = /RQC, /RSC{ = ZTSD^ /TUAi = Z.PUA,
Z.QRC = ZSRCi, ZSTB{ = /UTA{, /UP A = /QPD.
Найдите длину замкнутой ломаной PQRSTUP, если длина ребра
куба равна 1.
[На ребрах AZ), DC, CCV, ВВ{, А^В^, A[D[ куба ABCDA^BiCiDi
выбраны точки Р, Q, R, S, Т, U соответственно. Оказалось, что
/PQD = /RQC, /RSB = /TSB\, ZTtMi = /PUDX,
Z.QRC = /SRCX, = /UTA{, /UP A = /QPD.
Найдите длину замкнутой ломаной PQRSTUP, если длина ребра
куба равна 1.] (М. Гусаров)
ЗАДАЧИ ВТОРОГО ТУРА, 6-11 КЛАССЫ
6 КЛАСС
28. Дети, построенные парами, выходят из лесу, где они со-
бирали орехи. В каждой паре идут мальчик и девочка, причем
у мальчика орехов либо вдвое больше, либо вдвое меньше, чем
у девочки. Могло ли так случиться, что у всех вместе 1000 оре-
хов? (А. Голованов)
29. Можно ли расставить в клетках шахматной доски 8x8
натуральные числа так, чтобы любые два числа, стоящие в со-
седних (по стороне) клетках, отличались на 1, а любые два числа,
- 10 -
стоящие в клетках, связанных ходом'коня, отличались на 3?
(Л. Голованов)
30. Двоечник Федя выставляет (по одной) шашки на клетки
доски 10 х 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. Найдите все такие пары натуральных чисел т и п, что
HOK(m,n) - НОД(т,п) = .
О
(Л. Голованов)
-12-
42. Точка D середина стороны АС тре- J3
угольника АВС. На сторож' ВС выбрана /\
такая точка Е, что /ВЕА = /CED. Найди- X
те отношение длин АЕ : DE. (С. Берлов) X
43. См. задачу 32. S,ц—X С
44. См. задачу 40.
45. По кругу расставлены числа от 1 до 30. Стоящие на сосед-
них местах числа можно поменять местами. После некоторого
количества таких операций оказалось, что каждое число пере-
местилось на диаметрально противоположное место. Докажите,
что в некоторый момент меняли местами числа, сумма которых
равна 31. (С. Берлов)
46. Дана бесконечная последовательность натуральных чисел
ап, в которой при всех п выполняется соотношение
^п+2 НОД(ап, Пп-f-i) 1.
Может ли эта последовательность содержать более 1998 различ-
ных чисел? (4. Голованов)
47. В оздоровительный лагерь приехало несколько школьни-
ков, каждый из которых имеет среди приехавших от 2 до 30 зна-
комых. Докажите, что опытный вожатый сможет расселить их в
60 комнат так, чтобы никакие' два знакомых не оказались в одной
комнате, и чтобы не было школьника, все знакомые которого жи-
вут в одной комнате. (Д. Карпов)
9 КЛАСС
*
48. Числа х, 1/, z, t удовлетворяют неравенству
(я + у + Z +t)2 4(;г2 + у2 + Z2 + i2).
Докажите, что существует такое вещественное число а, что
(.с — а)(у — а) 4- (г — a)(t — а) = 0. (С. Берлов)
49. Вдоль окружности расставлены числа от 1 до 100 (в про-
извольном порядке). Для каждых трех чисел, стоящих подряд,
вычислили их сумму. Докажите, что какие-то две из вычислен-
ных сумм отличаются не меньше, чем на 3. (С. Берлов)
50. В треугольнике АВС точка М - середина стороны ВС;
4А|, ВВ], СС\ - высоты. Прямые АВ и AiBi пересекаются в
-13-
точке X, а прямые МС\ и АС - в точке У.
Докажите, что ХУ || ВС. (Д. Ростовский)
51. Найдите все целочисленные решения
уравнения
р2 + q2 + pq = 15г2 . (Л. Голованов)
52. В десятичной записи несократимой дроби т/п каждая
цифра после запятой, кроме первой, меньше суммы двух соседних
с ней цифр на одно и то же натуральное число к. Докажите, что
п 819. (Ю. Базлов)
53. Точка М - середина стороны АС тре-
угольника АВС. На отрезке AM выбрали
точку X, на отрезке ВМ - точку £, на отрез-
ке В К - точку N. Оказалось, что KL || АВ,
MN || ВС, CL = 2КМ. Докажите, что CN ~
биссектриса угла ACL. (С. Берлов)
54. В стране 2п городов и несколько авиалиний. Любые че-
тыре' города соединены друг с другом не более чем четырьмя
авиалиниями. Какое наибольшее количество авиалиний может
быть в этой стране? (С. Берлов)
10 КЛАСС
55. Числа а, 5, с удовлетворяют неравенству
f Д Ю\ шах(а, Ь) + шах(с, 1997) = min(a, с) 4- min(6,1998).
I / q Дх £ Докажите, что Ь с. (Л. Храбров)
56* О - центр описанной окружности остро-
С угольного треугольника АВС. Прямая ВО
вторично пересекает описанную окружность в
точке D, а продолжение высоты, опущенной из вершины Л, пере-
секает окружность в точке Е. Докажите, что площадь четырех-
угольника BECD равна площади треугольника АВС.
(М. Брату севич)
57. Город расположен на нескольких островах, соединенных
между собой мостами. При поездках по городу жители выра-
жают длину своего пути числом мостов, которые им приходится
переезжать. После того как один из мостов1 закрыли на ремонт,
1 Болыиеохтинский.
-14-
каждый горожанин заявил: “У меня есть друг, кратчайший путь
к которому содержит теперь на один мост больше, чем раньше”.
Докажите, что хотя бы один из островов - необитаемый.
(Ф. Назаров)
58. См. задачу 51.
59. См. задачу 52.
60. 999 непересекающихся отрезков с концами в вершинах пра-
вильного 1998-угольника разбивают эти вершины на пары. Дока-
жите, что на отрезках можно так расставить стрелки, что сумма
полученных векторов будет равна нулю. (С. Берлов)
61. С последовательностью чисел (а;, а?, • • • ,ап) разрешается
делать следующее: выбрать произвольный помер A:, 1 к п, и
заменить в последовательности число на — (гц -И2Ч У-ап) — к.
Сколько различных последовательностей можно получить таки-
ми преобразованиями из последовательности (0,0,... , 0)?
(М. Всемирное)
11 КЛАСС
62. Найдите все положительные решения уравнения
шах(«, Ь) шах(с, 1998) = шш(«, с) ixxin(6,1998) . Храбров)
63. Натуральное число п таково, что п 4-1 делится на [д/п] 4-1.
Докажите, что (п — 1)(п — 3) делится на [^/п] — 1. (Л. Голованов)
64. См. задачу 57.
65. Две плоскости делят куб на четыре равновеликие части.
Докажите, что его поверхность они тоже делят на четыре равно-
великие части. (М. Гусаров)
66. Докажите, что для любого натурального п выполнено не-
равенство
(1 + 1){2+ -М...(п4- -И 2п\
V k п/ (Ю. Базлов)
67. В клетках квадрата 8x8 расставлены целые числа. Каждая
клетка закрыта карточкой, на которой написана сумма чисел в
квадрате 3 х 3 с центром в этой клетке. Какое наибольшее ко-
личество чисел в клетках квадрата можно заведомо определить,
если известны только числа на карточках? (С. Волченков)
68. См. задачу 61.
- 15*-
ЗАДАЧИ ОТБОРОЧНОГО ТУРА, 9-11 КЛАССЫ
9 КЛАСС
69. На сколько нулей может оканчиваться число ln+2n+3n+4n
(n е N)? (А. Храбров)
70. Диагонали параллелограмма ABCD пересекаются в
^~В С точке О. Окружность, описанная вокруг
/ /рХ треугольника АВОУ пересекает сторону
\ / / АВ в точке' Е. Окружность, описан-
\ ная ВОКРУГ треугольника DOE, пересека-
ет отрезок BE в точке F. Докажите, что
Е Z.BCA = Z.FCD. (С. Берлов)
71. На листе клетчатой бумаги нарисована несамопересека-
ющаяся замкнутая ломаная, не проходящая через узлы сетки. В
области, ограниченной ломаной, лежит не менее 91 узла. Дока-
жите, что ломаная пересекает линии сетки по крайней мере в 40
точках. (С. Иванов)
72. Докажите, что количество таких натуральных чисел
d}„(iin_i .. .б£| (т > 1998), что
arn«m-i • • • «1 = amarn-i • • ai9992 + <Й99«<*1997 - - < «12, — четно.
(А. Храбров)
73. В квадрате 10 х 10 расставлены все натуральные числа от
1 до 100. В каждой строке отметили третье по величине число
(считая от наибольшего). Докажите, что сумма всех отмеченных
чисел не меньше суммы чисел в некоторой строке. (С. Берлов)
74. Докажите, что проекции точки пересечения диагоналей
вписанного четырехугольника на две его противоположные сто-
роны симметричны относительно прямой, соединяющей середи-
ны двух других противоположных сторон этого четырехугольни-
ка. (С. Берлов)
75. Множество М состоит из п точек плоскости, никакие три
из которых не лежат на одной прямой. Для каждого треуголь-
ника с вершинами из М подсчитали количество точек М внутри
него. Докажите, что среднее арифметическое всех найденных чи-
сел не превосходит n/4. (С. Иванов)
76. На очень большом столе лежат две кучи спичек. В первой
куче 2100 спичек, во второй - З100. Два игрока по очереди берут
спички из куч. Одним ходом разрешается брать из одной кучи к
-16-
спичек, из другой - т так, чтобы \k2 — m2| 1000. Выигрывает
взявший последнюю спичку. Кто выиграет при правильной игре?
(С. Берлов)
10 КЛАСС
77. В троллейбусе едут 175 пассажиров и два кондуктора.
Каждый пассажир покупает билет только после того, как его три
раза об этом попросят. Сначала первый кондуктор просит при-
обрести билет одного из еще безбилетных пассажиров, потом то
же самое делает второй, и так далее до тех пор, пока все не ку-
пят билеты. Продажу какого наибольшего количества билетов
может обеспечить себе первый кондуктор? (Ф. Назаров)
78. На каждом из 10 листов бумаги написано несколько степе-
ней двойки. Суммы чисел на всех листах одинаковы. Докажите,
что какая-то из степеней двойки встречается на этих листах не
менее 6 раз. (С. Иванов)
79. В стране 1998 городов, любые два города соединены авиа-
линией. Цены билетов на всех авиалиниях различны. Могут
ли все круговые маршруты (проходящие через каждый город по
одному разу и возвращающиеся в исходный пункт) иметь одина-
ковую стоимость? (К. Кохась)
80. На отрезке АС как на основании в р
разных полуплоскостях построены равно бе-
дренные треугольники АВС и ADC, причем / 2^*
Z.ADC = 3ZACB. АЕ - биссектриса тре- д \ с
угольника АВС, отрезки DE и АС пересека-
юте я в точке F. Докажите, что треугольник D
CEF - равнобедренный. (С. Иванов)
81. Докажите, что для всякого натурального п > 1 между
числами п2 и (п-hI)2 можно выбрать три различных натуральных
числа «, b и (. так, что а2 Н- Ъ2 делится на с. (С. Берлов)
82. См. задачу 74.
83. См. задачу 75.
84. Начокружности отмечены 999 точек. Сколькими способами
можно расставить в этих точках буквы Д, В и К так, чтобы на
любой дуге между любыми двумя одинаковыми буквами стояло
четное число отличных от них? (Д’. Карпов)
- 17-
11 КЛАСС
85. В куче G66 спичек. Два игрока ходят по очереди. Каждый
своим ходом может либо взять из кучи от 1 до 5 спичек, либо
обменять у судьи ранее взятые 5 спичек на ириску. Выигрывает
взявший последнюю спичку. Кто выиграет при правильной игре?
(К. Кохась)
/К 86. Окружность, проходящая через вер-
Р Г I \ шины А и С треугольника АВСЬ пересека-
ет сторону АВ. в ее середине D, а сторону
I/~ в точке Окружность, проходящая
через точку Е и касающаяся в точке С пря-
С К мой АС, пересекает прямую DE в точке F.
К - точка пересечения прямых АС и DE. Докажите, что прямые
CF, АЕ и В К пересекаются в одной точке. (С. Берлов)
87. Можно ли в “клетчатом” кубе 8x8x8 отметить 64 клетки
так, чтобы в каждом слое кубиков, параллельном грани, было
отмечено ровно 8 клеток, а среди любых 8 отмеченных клеток
какие-то две обязательно находились в одном таком слое?
(А. Вершик)
88. Найдите все многочлены Р(ж, у) от двух переменных такие,
что при любых х и у Р(х + у,у — х) = Р(х,у). (А. Голованов)
89. 2п-угольник А\ Аг ... Агп вписан в окружность с центром О
и радиусом 1. Докажите, что
IA1A2-I-A3A4-I---ЬАгп-1А2п| 2 sin (-(Ai О Аг 4-.. • +Агп-10 Агп)) •
z
(Ю. Базлов)
90. Пусть d(n) обозначает количество натуральных делителей
числа п. Докажите, что последовательность с?(п2 4-1) ни с какого
места не становится строго монотонной. (А. Голованов)
91. В дружине 169 человек. Каждый день четверо из них выхо-
дят на дежурство. Может ли через некоторое время случиться,
что любые двое отдежурили вместе ровно один раз? (К. Кохасъ)
92. Можно ли в клетках таблицы 11 х И так расставить
буквы П, А, С, чтобы в верхней строчке таблицы было написано:
“ПАПАСПАСПСА”, ни одна из остальных клеток, прилегающих
к границе, не содержала бы букву С и чтобы ни в одной фигурке
вида Д-j или Щ не было трех различных букв? (Я. Филонов)
-18-
ЗАДАЧИ ОЛИМПИАДЫ ФМЛ № 239
Осенью 1997 года состоялась очередная открытая олимпиада
ФМЛ №239. Она проходила в 1 тур, в котором приняло участие
около 80 школьников, в том числе почти все сильнейшие “олим-
пиадники” города. Олимпиада продолжалась 5 часов. При этом
все равно (как и во все предыдущие годы) нашлись задачи, кото-
рые никто не решил.
8-9 КЛАСС
93. По окружности расставлены 20 единиц и 30 двоек так, что
никакие три одинаковые цифры не стоят подряд. Найти сумму
произведений всех троек подряд идущих цифр. (С. Берлов)
94. В треугольнике АВС К 6 АВ, В
N Е ВС, М - середина АС, Известно, что
Z.BKM = Z.BNM, Докажите, что перпенди- / YJV
куляры к сторонам исходного треугольника /х+/ \
в точках К, N, М пересекаются в одной точ- С
ке. (С. Берлов)
95. Вершины связного графа раскрашены в 4 цвета так, что
ребра соединяют вершины разных цветов, причем каждая вер-
шина соединена с одинаковым количеством вершин трех других
цветов. Докажите, что при выкидывании любых двух ребер, вы-
ходящих из одной вершины, граф останется связным.
(С. Берлов)
96. На плоскости дано несколько равных параллельно распо-
ложенных квадратов, причем среди любых п из них два имеют
общую точку. Доказать, что эти квадраты можно разбить на не
более чем 2п — 1 подсистем, в каждой из которых все квадраты
имеют общую точку. (В. Дольников)
97. Биссектрисы вписанного четырехугольника образуют в
пересечении выпуклый четырехугольник. Докажите, что диаго-
нали полученного четырехугольника перпендикулярны.
(С. Берлов)
98. Докажите, что любое число, большее ?z4/16 (п 6 ^раскла-
дывается в произведение двух сомножителей, разность которых
не превосходит п, не более, чем одним способом. (С. Берлов)
99. На единичной решетке дан выпуклый 2п-угольник. Дока-
зать, что его площадь не меньше, чем п(п — 1)/2. (,С; Иванов)
-19-
100. На плоскости дано несколько векторов, сумма длин ко-
торых равна 1. Доказать, что их можно разбить на три группы
(возможно, пустые) так, что сумма длин сумм векторов в этих
группах будет больше ЗУЗ/2тг. (С. Берлов)
10-11 КЛАСС
В
Q
В2
101. См. задачу 94.
102. См. задачу 95.
103. Существуют ли
многочлен Р с целыми ко-
эффициентами, отличный
от константы, и натураль-
ное число к такие, что все
числа вида F(jkn) попарно
взаимно просты?
(А. Пастор)
104. См. задачу 98.
105.
АВС. Некоторая окруж-
Точка I - центр
В3 1 С
вписанной окружности треугольника
ность с центром в I пересекает сторону ВС в точках Ах и Ль
сторону С А в точках Вх и В2, сторону АВ в точках Сх и С2. По-
лученные точки расположены на окружности в порядке Ах, А2,
Вх, В2, Сх, С2. Точки А3, В3, С3 - середины дуг АГА2, ВхВ2, СхС2
соответственно. Прямые Л2Л3 и ВхВз пересекаются в точке С4,
прямые В2Вз и СхСз - в точке А4, а прямые С2Сз и Ах A3 - в точ-
ке В4. Докажите, что отрезки А3А4, В3В4, С3С4 пересекаются в
одной точке. (С. Берлов)
106. На единичной решетке дан выпуклый 2п-угольник. Дока-
жите, что его площадь не меньше, чем n3/100. (С. Иванов)
107. Дано натуральное число п. Докажите, что существует
такое е > 0, что для любых п положительных чисел (ц, а2, ... ,
ап найдется положительное вещественное число t, для которого
б< {tai}, {ta2}, • • ♦ > {tan} < (С. Иванов, К. Кохась)
108. На плоскости дано несколько равных параллельно рас-
положенных квадратов, причем среди любых п из них можно вы-
брать четыре имеющих общую точку. Докажите, что эти ква-
драты можно разбить на не более чем п — 3 подсистем, в каждой
из которых все квадраты имеют общую точку. (В. Дольников)
-20-
ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ
1. Можно расставить крестики и нолики так:
1 вариант:
0 0 0 0 0
X 0 X 0 А
0 X 0 X X
X 0 X 0 X
0 X 0 X X
2 вариант:
0 X X 0 0
0 X X 0 0
0 0 0 X X
0 0 0 X X
0 X X 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. Ответ: нельзя. Рассмотрим внутри квадрата фигуру вида
FH I'] I I - С одной стороны, сумма чисел в этой фигуре долж-
на быть равна 210, так как эта фигура есть объединение двух
пятиклеточных фигур из условия; с другой стороны, эту фигу-
ру легко представить в виде объединения пяти прямоугольников
1x2, значит, сумма чисел в ней должна быть равна 5 • 40 = 200;
Итак, требования нашей расстановки противоре- rFP
чивы, и расставить числа нельзя. Во втором вари- .-[ j I I
анте, аналогично, можно рассмотреть фигуру вида LJ
♦ В квадрате 10 х 10 клеток расставлены натуральные числа
так, что при любом расположении фигурки вида сУмма чи‘
сел в ней равна 105. Верно ли, что сумма чисел во всей таблице
делится на 105?
- 21 -
5. См. рисунок.
2 см 2 см
0.5 см
3.5 см
4 см
Существуют и другие способы.
6. Ответ: нельзя.
1.5 см 1.5 см
I 0.5 см
2.5 см
Предположим, что такая расстановка чисел существует. По
условию, любые два числа, стоящие через одно, имеют неотри-
цательное произведение, то есть либо это числа одного знака,
либо одно из них - нуль. Занумеруем места, на которых стоят
числа, номерами от 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. Решение! (уравнение). Пусть на складе лежит х банок
по 0.7 л, а банок по 0.5 л нет. Тогда банок по 1 л всего 2500 — х
[2600 — и]. Общая ёмкость банок равна 1998 л, значит,
0.7я + 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. Решение! (четность). Из четырех данных чисел найдутся
2 числа одинаковой четности. Ясно, что их сумма будет четна и
поэтому не может быть равна степени нечетного числа.
Решение 2 (неравенство). Допустим, что мы нашли требуе-
мые числа а, 6, с, d, а < Ь < с < d, Пусть c + d = 5*, тогда d > 5fc/2
и 5А:/2 < b + d < 5к. Значит, число Ъ 4- d никак не может быть
степенью числа 5.
11. Требуется доказать, что
ник EAD равнобедренный. Для
статочно проверить, что /EAD
А так как /EDA = /FDC, то
что /LEAD — /FDC. Заметим,
угольник DBF равнобедренный.
/BDF = /BFD. Тогда /ADB = /DFC.
Теперь мы видим, что треугольники ADB и DFC равны по двум
сторонам и углу. Значит, /LEAD = /FDC, что и требовалось.
Во втором варианте, как видно из картинки к условию, речь
идет о той же самой задаче.
m-а а
12. Пусть т и п - длины сторон исходно-
го прямоугольника, а и Ь ~ их остатки при
делении на 7. Тогда исходный прямоуголь-
ник можно разрезать на 3 прямоугольника
размерами (ш — а) х п, а х (п — Ь) и а х Ь.
Поскольку у первых двух прямоугольников разрезания длина од-
ной из сторон делится на 7, то их можно разрезать на прямо-
угольники 1x7. Так как площадь оставшегося прямоугольника
треуголь-
этого до-
= /EDA,
докажем,
что тре-
Значит,
А
С
-23-
a x b не превосходит 36, а площадь исходного была не меньше
4 • 360 = 1440, то суммарная площадь разрезанной части - не
менее 1404, откуда следует, что вырезано более двухсот прямо-
угольников 1x7.
13. Ответ: 4.75 [во втором варианте - 5.8]. Из неравенств
[ж]{.г} > Зи {i} < 1 следует, что [.г] > 3. При [х] = 4 получаем
{х} 3/[я] = 0.75, т. е. х 4.75. Если же [я] 5, то О И
5 > 4.75. Значит, наименьшее возможное значение х равно 4.75.
Второй вариант решается аналогично.
14. Пусть f(x) = ах2 4~ b\x 4- ci, д(х) = ах2 4- Ь^х 4- Оз, тогда
f(x) + g(x) = 2а.'Г24"(&1 + Ьч)х + (с[ 4-q) и по теореме Виета (или из
формулы для корней квадратного уравнения) сумма корней f(x)
равна (—61 /а), сумма корней д(х) равна (—62/а), следовательно,
—Ь{/а — Ь>)/а = 0, откуда — (6| 4- Ь>>)1'2а — 0, а это - сумма корней
/(я) 4-(/(*).
15. Заметим, что существует ровно 142 делящихся на 7 на-
туральных числа, не превосходящих 1000, и 858 не делящихся,
следовательно, хотя бы одно из выбранных чисел делится на 7.
Аналогично, существуют ровно 333 натуральных числа, которые
не превосходят 1000 и делятся на 3, значит, какое-то из выбран-
ных чисел делится на 3. Тогда произведение этих чисел будет
делиться на 21, если же они совпадают, то в качестве второго
сомножителя можно взять любое другое выбранное число.
В Решение второго варианта аналогично.
\ 16. Пусть D и Е - середины сторон
АВ и АС соответственно. Заметим, что
Z \лОТ \ II II ~ серединный перпенди-
/ \1 \к \ куляр к АВ, значит, 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 и у 15, что противоречит равенству х + у = 58.
2 случай: d = 2. Тогда х = 2хо, у = 2//о, где хо и уо - взаимно
простые натуральные числа. Условия на х и у выражаются через
хо и уо следующим образом: х*о + уо == 29, 15#о делится на уо, 14^/0
делится на xq. Так же, как в первом случае, отсюда следует, что
xq 14 и уо 15. Значит, хо = 14 и уо = 15, иначе xq + уо < 29.
Значит, х = 28 и у = 30. Этот ответ подходит: 15 • 28 делится на
30, 14 • 30 делится на 28.
3 случай: d == 29. Поскольку числа х и у делятся на 29, они оба
не меньше 29. Значит, х = у — 29, иначе х + у > 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) = где с / 0- Знаменатель обращается в нуль
в точке х = —d/c. Если числитель тоже обращается в нуль в этой
точке, то числитель и знаменатель пропорциональны, а значит,
функция является константой (этот случай мы рассмотрим в кон-
це). Если же числитель не обращается в нуль при х = —d/c, то
функция принимает сколь угодно большие значения вблизи этой
точки (ее график имеет там вертикальную асимптоту). Посколь-
ку функция f — <7 ограничена снизу числом 1997, функция д тоже
должна принимать сколь угодно большие значения вблизи точки
х = -d/c. Значит, знаменатель функции д в этой точке обраща-
ется в нуль, следовательно, он пропорционален ex 4- d. Посколь-
ку функции f и д имеют пропорциональные (можно считать, что
одинаковые) знаменатели, их разность - тоже дробно-линейная
функция со знаменателем сх 4- d. Значит, она либо постоянна,
либо имеет вертикальную асимптоту при х = —djc (это объяс-
нено выше применительно к функции /). Наличие вертикальной
асимптоты противоречит тому, что /(х) — д(х) > 1997 для всех х,
значит, / — д может быть только постоянной функцией.
Таким образом, мы разобрали случай, когда одна из функций
(неважно, f или д) имеет вертикальную асимптоту. Если они
обе не имеют вертикальных асимптот (т. е. если у каждой из
них знаменатель постоянен или пропорционален числителю), то
это две линейные функции. Тогда их разность - тоже линейная
функция, а поскольку она ограничена снизу, она постоянна.
♦ Как легко убедиться, разность двух дробно-л инейных функ-
ций является дробно-квадратичной функцией, т. е. отношением
двух многочленов степени не выше второй. Придумайте дробно-
квадратичную функцию, все значения которой больше 1997, но
которая не постоянна на своей области определения. Может ли
такая функция иметь знаменатель, представимый в виде произ-
ведения двух линейных функций? А знаменатель, имеющий два
корня?
21. Решение! (дополнительное построение - равные тре-
угольники). Пусть F - точка на луче PC, расположенная за точ-
кой С так, что CF = ВЛ. Так как
A.ABD = Z.CAD 4- Z.ADC = 180° - Z.ACD = Z.ACF,
-26-
то треугольник DBA равен треугольнику ACF по двум сторонам
и углу между ними. Тогда AD = AF и
AFAC = A AD В = ABAC. f
~ R \
Следовательно, точка F лежит на пря- л?—\ С
мой АВ и ZBAD == ZAFC, что равно-
сильно равенству отрезков AD и DF. /
Итак, AD = AF = DF, треугольник AFD г\
равносторонний, значит, Z.BAD = 60°. [)
Решение 2 (дополнительное постро-
ение - окружность). Как и в решении С
1, заметим, что ZABD = 180° ~ ZACD.
Пусть С\ - точка, симметричная точ- /I
ке С относительно прямой AD. Тогда / I I ]
ZABD + ZACiD = 180° и BD = АСЪ /
Значит, четырехугольник ABDC± впи- || у
санный. Заметим, что А Q
ZBAD = ZABCi, ZDACi = ZDBCi
как углы, опирающиеся на равные хор-
ды, ZBDCi = ZADB из симметрии. Сумма углов треугольника
ABD равна 180°, следовательно,
180° = ZBAD + ZADB 4- ZDBCt + ZABCi =
= ZBAD 4- ZBAC 4- ZCAD 4- ZBAD = 3ZBAD.
Отсюда ZBAD = 60°.
Решение 3 (теорема синусов). По теореме синусов для тре-
угольников ABD и ACD имеем
sin ZB AD _ sin ZABD sin ZADC _ sin ZACD
BD ~ AD ’ AC “ AD
Как и в первых двух решениях, заметим, что ZABD 4- ZACD ==
180°. Следовательно, sin ZABD = sin ZACD, и правые части двух
выписанных равенств совпадают. Поскольку АС = BD, получа-
ем, что sin ZB AD = sin ZADC. Следовательно, ZADC = ZB AD
или ZADC = 180° — ZB AD. Второе равенство невозможно, так
как из него следует, что АВ || CD, а это противоречит тому, что
ZABD 4- ZACD = 180°. Значит, ZADC = ZB AD. Пользуясь
этим равенством и данными в условии соотношениями, напишем
-27-
сумму углов треугольника ABD:
180° = ZDAD 4- Z.ADB + Z.ABD =
= Z.BAD + Z.ADB 4- Z.CAD 4- Z ADC =
= Z.BAD 4- Z.BAC + ZCAD 4- /-BAD = 3ZBAD.
Отсюда Z.BAD = 60°.
Замечание. Из первого решения легко увидеть, что условия за-
дачи эквивалентны следующему набору свойств четырехуголь-
ника ABCD: /A = /D = GO0 и АВ + CD = AD.
22. Рассмотрим какие-нибудь три строки подряд. В них, по
условию, имеется не более 16 различных чисел, из которых по
крайней мере 10 встречаются в самой верхней из трех строк.
Значит, в двух нижних строках имеется самое большее 6 чисел,
которые не встречаются выше. Разобьем все строки на пары со-
седних и будем рассматривать их сверху вниз. В первой паре
строк имеется не более 16 различных чисел, так как даже в пер-
вых трех строках их не более 16. С каждой следующей парой
строк (а этих пар, кроме первой, всего 49) добавляется не бо-
лее 6 новых чисел, поэтому всего мы насчитаем самое большее
16 4- 6 • 49 = 310 различных чисел.
♦ Оценка 310 - точная: в таблице может быть ровно 310 раз-
личных чисел. Придумайте пример такой таблицы.
23. Для положительных х данное неравенство равносильно
неравенству
[х] • {х} 1000 [ [х] • {х} > 100 ] .
Дальше решение аналогично решению задачи 13.
24. Пусть - первый член прогрессии, d - её разность. Из
условия следует, что прогрессия содержит хотя бы одно число
вида ш!, где т > d. Это значит, что при каком-то к a^-\~kd — т\.
Заметим, что в этом равенстве выражения т! и kd делятся на d.
Значит, di тоже делится на d.
25. 41 • 271 = 11111. Дальше - см. решение задачи 8.
26. Если ни одно из найденных чисел не является корнем
производной, то среди найденных значений х не встречаются ни
локальные минимумы, ни локальные максимумы исходного мно-
гочлена. Тогда многочлен /(.г) - 10 [f(x) — 11] меняет знак в
четном числе точек, поэтому значения многочлена при х —> — оо
- 28 -
и при х —> 4-оо имеют один и тот же знак, следовательно, этот
многочлен имеет четную степень. Но, с другой стороны, много-
член f(x) — 15 [/(ж) — 16] меняет знак в нечетном числе точек и,
следовательно, имеет нечетную степень. Этого не может быть,
поскольку упомянутые многочлены имеют одинаковые степени.
Таким образом, хотя бы одно из найденных чисел должно быть
корнем производной многочлена.
27. Ответ: Как нетрудно проверить, каждое из ра-
венств, данных в условии, означает, что угол между каждым зве-
ном ломаной и соответствующим ребром куба равен углу между
следующим звеном ломаной и этим же ребром куба. Отсюда
следует, что, построив подходящую развертку Куба, мы сможем
добиться того, что ломаная будет изображена на ней отрезком
прямой линии. Указанные развертки для обоих вариантов да-
ны на рисунке. Из рисунков ясно, что в обоих случаях длина
ломаной равна д/20.
Di D
А В В
28. Заметим, что в каждой паре суммарное число орехов
должно делиться на 3, значит, и общее число орехов должно де-
литься на 3 и не может быть равно 1000.
29. (См. рисунок.) Пусть в клетке А стоит ——- ———
число п, а в клетке В - число п + 3. Тогда в-----—--------
клетках С и D должны стоять числа п 4-1 и п 4- 2, — —-----
так же как и в клетках Е и F. Но тогда числа в ———LJ______
клетках С и F, связанных ходом коня, будут отличаться на 1,
что противоречит условию задачи. Следовательно, требуемым
образом числа расставить нельзя.
30. Рассмотрим момент, когда осталась ровно одна незанятая
клетка. Тогда одна из шашек может побить шашку, стоящую
рядом со свободной клеткой.
-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 = 2Н, то для того, чтобы получить число,
превосходящее 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. HOK(m,n) является делителем числа тп, при-
-33-
чем из уравнения следует, что HOK(m,n) > тп/3. Значит,
HOK(m,n) = тп или HOK(m,n) = mn/2. В первом случае т
и п взаимно просты, т. е. НОД(/п, п) = 1. Подставляя в уравне-
ние, получаем, что mn-1 = пш/3, откуда тп = 3/2. Значит, этот
случай невозможен. Во втором случае НОД(т, п) = 2, и уравне-
ние переписывается в виде тп/2 — 2 = тп/3, откуда тп = 12. Но
число 12 единственным образом представляется в виде произве-
дения двух чисел с наибольшим общим делителем, равным 2, а
именно 12 = 2-6.
Решение 2. Пусть d = НОД(т,п), тогда т = xd и п = yd,
где х и. у - взаимно простые натуральные числа. При этом
HOK(m, п) = xyd, поэтому xyd — d = xyd2/3. Преобразуя, по-
лучаем, что ху(3 — d) = 3. Значит, 3 делится на 3 — d, откуда
3 — d = 1, т. е. d = 2. Остается уравнение ху = 3, из которого
х = 1 и у = 3 (или наоборот). Значит, т = xd = 2, п = yd = б (или
наоборот).
Решение 3. Пусть НОД(т,п) = ж, НОК(т,п) = у. Тогда
тп = .гу, и исходное уравнение имеет вид у — х = ху/3. Преобра-
зуя, получаем, что (3—х)(у+З) = 9. Так как у4-3 — положительное
число, то 3 — х - положительный делитель девяти, меньший трех.
Отсюда х = 2, у = 6. Теперь нетрудно сообразить, что т = 2,
п = 6 (или наоборот).
J3 42» Ответ. 2:1.
/ \ Решение 1. Проведем через точку D
/ ЛЕ прямую, параллельную ВС, и пусть F -
/ точка пересечения этой прямой с АЕ. По
д и \ С теореме Фалеса точка F делит отрезок АЕ
& пополам, т. е. АЕ : FE = 2:1. С другой
стороны, FE = DE, так как в треугольнике DEF углы D и F
равны. Действительно, Z.FDE = Z.CED и /LDFE = Z.BEF из
равенства накрест лежащих углов, а углы CED и BEF равны по
условию. Значит, АЕ : DE = АЕ : FE = 2:1.
Решение 2. Опустим из точек А и D
перпендикуляры АХ и DY на прямую ВС.
/ \ х Прямоугольные треугольники АХЕ и DYE
/ подобны, так как их углы в вершине Е рав-
ны по условию. Значит, AE:DE = АХ: DY.
д || \ с Прямоугольные треугольники АХС и DYC
& подобны, так как угол С у них общий,
поэтому АХ : DY = АС : DC = 2:1. Значит, АЕ : DE = 2:1.
-34-
Решение 3. Построим треугольник А'ВС, симметричный
треугольнику АВС относительно прямой ВС. Пусть D* ~ середи-
на отрезка А'С, проведем отрезок
ED*. Так как /.АЕВ = Z.DEC = ________—А'
Z.DfEC, точки А, Е, Df лежат на од-
ной прямой. По построению, пря- /
м&яЕС- ось симметрии и, в част- / /
ности, медиана треугольника АА!С. . ц \/
Тогда АЕ : DE = АЕ : D'E = 2 : 1, D С
поскольку медианы в точке пересечения делятся в отношении 2:1.
45. Будем считать, что при перемещении в соседнюю позицию
против часовой стрелки число сдвигается на -hl, а при переме-
щении по часовой стрелке - на —1. Сумма всех сдвигов всех
чисел равна нулю, так как она равна нулю при каждом обмене.
Если занумеровать все позиции числами от 0 до 29 против часо-
вой стрелки, то позиция каждого числа в любой момент времени
равна остатку по модулю 30 суммы его начальной позиции и на-
копленных к этому моменту сдвигов. Значит, суммарный сдвиг
каждого числа имеет остаток 15 по модулю 30, так как его конеч-
ная позиция отличается от начальной ровно на 15.
Докажем теперь, что если числа х и 31— х не менялись местами,
то их суммарные сдвиги равны. Для этого проследим за рассто-
янием между х и 31—х вдоль дуги, проходящей от х к 31 -х против
часовой стрелки (считая расстояние между соседними числами
равным 1). Это расстояние может принимать значения от 1 до
29. При обмене, в котором участвует число я, из расстояния
вычитается его сдвиг. При обмене, в котором участвует число
31 — ж, к расстоянию прибавляется его сдвиг. Если обменивают-
ся два числа, отличных от х и 31 — х, то расстояние не изменяет-
ся. Значит, если х и 31 — х не менялись местами друг с другом,
то расстояние между ними изменилось на разность суммарного
сдвига числа 31 — х и суммарного сдвига числа х. Но расстояния
в начале и в конце равны, значит, и суммарные сдвиги равны.
Таким образом, если х и 31 — х не менялись местами, то сумма
их сдвигов равна удвоенному сдвигу числа ж, то есть числу вида
60& 4-30. Числа от 1 до 30 разбиваются на 15 пар вида (ж, 31 — х).
Если ни в какой паре числа не менялись местами, то общая сумма
всех сдвигов равна сумме пятнадцати чисел вида 60fc + 30. Но
такая сумма имеет остаток 30 по модулю 60, а сумма всех сдвигов
должна быть равна нулю.
-35-
46. Да, может. Приведем пример такой последовательности.
Положим «2000 = 3, «1999 = 4. Числа «п, начиная с п = 2001, опре-
делим по индукции с помощью данной в условии формулы. Числа
ап, где 1 п 1998, построим “обратным ходом” (т. е. сначала
«1998, ПОТОМ «1997, И Т. Д. ДО «1) ПО формуле «п = («п+1 - 1)(«п+2 ~ 1).
По индукции легко доказывается, что числа «2000, «1999, • • •, «1 все
не меньше трех и возрастают. В частности, они все различны.
Убедимся, что построенная последовательность удовлетворяет
соотношению ап+2 = НОД(«п,«п+1) + 1- При п 1999 это вы-
полняется автоматически. При п = 1998 имеем ап =3-2 = 6,
НОД(ап,ап+1) 4- 1 = НОД(6,4) 4-1=3 = «п+2- Пусть п 1997.
Тогда
НОД(«п,«п+1) “ НОД((ап+1 l)(«n+2 l),«n+i) =
= НОД(«п+2 1,«п+1) НОД(«п4-2 1, («п+2 1)(«п+3 1)) —
= «п+2 ~ 1,
что и требовалось. (Второе равенство в цепочке следует из того,
что an+i - 1 взаимно просто с «п+1«)
47. Обобщим немного условие задачи, а именно будем счи-
тать, что количество знакомых одного школьника может быть
от 0 до 30, но требование, чтобы все знакомые не жили в одной
комнате, будем применять только к тем, у кого не меньше двух
знакомых.
Докажем обобщенное утверждение задачи индукцией по числу
школьников. База (нуль школьников) очевидна. Предположим,
что приехало п школьников, и что для любого их количества,
меньшего п, утверждение уже доказано. Если среди приехавших
никто ни с кем не знаком, расселим их как угодно. В противном
случае выберем двоих знакомых (пусть это Вася и Петя) и рас-
селим всех остальных в соответствии с обобщенным условием.
Будем называть комнату неподходящей для Васи, если выполня-
ется хотя бы одно из следующих условий:
1) в ней живет кто-то из знакомых Васи;
2) у Васи есть знакомый (не Петя), который имеет кроме Ва-
си ровно одного знакомого, и этот знакомый знакомого живет в
данной комнате;
3) у Пети есть еще знакомые, кроме Васи, и все они живут в
данной комнате.
-36-
Аналогично определим комнаты, неподходящие для Пети.
Легко проверить, что если поселить Васю и Петю в разные под-
ходящие для них комнаты, то условие будет выполнено. Посмо-
трим, сколько комнат могут быть неподходящими для Васи. Пер-
вое и второе условие (по отдельности) делают неподходящими
самое большее столько комнат, сколько есть знакомых у Васи,
кроме Пети, то есть не более 29 комнат. Третьему условию мо-
жет удовлетворять только одна комната. Всего получается не
больше 59 комнат. Заметим, однако, что если их ровно 59, то все
знакомые Пети живут в одной комнате, а тогда при аналогичном
подсчете для Пети мы получим не более 1 4- 29 4- 1 = 31 комнат.
Таким образом, для каждого из них неподходящими являются не
более 59 комнат, причем если у одного их ровно 59, то у другого
меньше. Значит, для любого из них есть хотя бы одна подхо-
дящая комната, и при этом для кого-то из них подходящих ком-
нат хотя бы две. Пусть есть хотя бы две комнаты, подходящие
для Пети. Тогда сначала поселим Васю в подходящую для него
комнату, а потом поселим Петю в подходящую для него комна-
ту, отличную от той, куда поселили Васю. Таким образом, все
школьники окажутся расселенными в соответствии с (обобщен-
ным) условием.
48. Решение 1: заметим, что левая часть данного в условии
равенс тва представляет собой квадратный трехчлен относитель-
но а. Если равенство не выполняется ни при каких значениях а,
то дискриминант данного трехчлена будет отрицателен, т. е.
(х 4- у 4- z 4-t)2 - 8(ху 4- zt) < 0,
откуда
(а: 4- у 4- z 4-t)2 < 8(.п/ 4- zt) 4(х2 + у2 4- z2 + t2),
что противоречит данному в условии неравенству.
Р ешение 2: после несложных преобразований данное в усло-
вии неравенство приводится к виду/
(•*’ - У? + (х - z)2 + (х- t)2 + (у - с)2 4- (г/ — t)2 + (z - t)2 0,
которое выполняется только при х = у = z = t. Теперь можно
взять а = х.
49. Разобьем все числа, кроме 100, на 33 непересекающиеся
тройки подряд стоящих чисел. Поскольку сумма всех чисел в
тройках равна 14-24-----F 99 = 4950, то найдется тройка, сумма
-37-
чисел в которой не более 150. Теперь разобьем на, 33 непересе-
кающиеся тройки все числа, за исключением 1. Сумма чисел в
этих тройках равна 5049, следовательно, одна из сумм в них не
менее 153. Таким образом, мы нашли две тройки, суммы чисел в
которых различаются не менее чем на 3.
50. Поскольку AAly BBi,
CCi - высоты, то четырех-
угольники ABAiBi и BCBiCi
~ вписанные, значит,
ZC1BM = ZGBi А =
Так как СуМ - медиана пря-
моугольного треугольника
BCiC, выходящая из прямо-
го угла, то АВС]М = а, от-
куда ZYCiX = ZYBiX = а и четырехугольник XYCiBy - впи-
санный, поэтому ZYXCi = ZYBiCi = ZCiBM, значит, XY || ВС.
51. Ответ. p = g = r = 0, других решений нет.
Решение 1 (делимость на 3). Предположим, что хотя бы од-
но из чисел р, д, г отлично от нуля. Уравнение сохраняется при
умножении всех переменных на одно и то же число, поэтому, со-
кратив на наибольший общий делитель, мы получим решение, в
котором р, q и г взаимно просты в совокупности. Докажем, од-
нако, что они должны все делиться на 3, это противоречие будет
означать, что сделанное нами предположение неверно. Данное
уравнение является квадратным относительно р. Поскольку оно
имеет целый корень, его дискриминант
D — q2 ~ 4(g2 — 15r2) = -3g2 4- 60r2 = 3(20r2 - g2)
должен быть точным квадратом. Так как он делится на 3, он дол-
жен делиться и на 9, значит, число D/3 = 20г2 — д2 делится на
3. Если оба числа g и г не делятся на 3, то их квадраты дают
остаток 1 при делении на 3, и, следовательно, 20г2 — д2 дает оста-
ток 2. Если же одно из них делится на 3, то и другое делится
на 3, так как коэффициенты 20 и —1 на 3 не делятся. Значит, р и g
делятся на 3, поэтому левая часть исходного уравнения делится
на 9. Следовательно, г делится на 3.
Решение 2 (делимость на 5). Вместо того, чтобы проверять,
что р и g делятся на 3, докажем, что они делятся на 5 (остальное -
-38-
так же, как в первом решении). В отличие от делимости на 3, это
можно установить перебором всех возможных остатков чисел р
и q при делении на 5, но мы приведем более короткий (и менее
унизительный) способ. Перепишем уравнение в виде
(р - 2g)2 - 3g2 + 5pg = 15r2.
Поскольку 5pg и 15r2 делятся на 5, получаем, что (р — 2g)2 и 3g2
дают одинаковые остатки при делении на 5. Квадрат целого чис-
ла может давать остатки 0, 1 или 4 при делении на 5, а утроенный
квадрат - 0, 3 или 2, так что остатки могут совпадать только если
числа делятся на 5. Значит, р — 2g и g делятся на 5, откуда и р
делится на 5.
52» Решение 1. Отбросив целую часть, будем считать, что
число ~ записано десятичной дробью 0,а}Л2«з<Ч «• • * Умножим
~ на 100, на —10 и на 1, и полученные результаты сложим:
100— =aia2l аза4а5 ...
-10^ = а19а2а3а4 ...
~ = 0,aia2a3...
91—= ..., к к к.,.
Из условия задачи вытекает, что получится дробь, в которой все
цифры после запятой равны к. (Легко убедиться, что к 9, на-
пример, рассмотрев наибольшую цифру числа ~.) Таким обра-
зом, число • 91 представимо в виде дроби со знаменателем 9,
следовательно, число ~ представимо в виде дроби со знаменате-
лем 819. Значит, п - делитель числа 819. Поэтому п < 819.
Решение 2. Обозначая первую цифру после запятой через а
и вторую - через 6, из условия находим, что третья цифра равна
b 4- к — а, четвертая - 2к — а, пятая - 2к — 6, шестая - к 4- а — 6,
седьмая - а, восьмая - 6. Таким образом, цифры повторяются
через шесть, поэтому дробная часть нашего числа равна чис-
лу, образованному ее первыми шестью цифрами, умноженному
на 0, (000001) = ддддэд * Первые шесть цифр образуют число
100000а 4-1000064-1000(64-/с-а)4-Ю0(2/с-а)4-Ю(2А;-6)4-А: 4-«-6 =
= 98901а 4- 109896.4- 1221Л;,
-39-
значит, дробная часть числа ~ равна
98901а + 109896 + 1221 Л: _ 81а + 96 + к
999999 ~ 819
(числитель и знаменатель сократились на 1221).
В 53. Пусть Р - середина стороны АВ.
уА Тогда точка N будет лежать на прямой
р/\ \ РМ, проходящей через середину основа-
\ ния АВ трапеции ABLK и точку пересе-
чения ее боковых сторон. Следовательно,
на эт°й прямой также лежит точка пересе-
чения диагоналей трапеции, которая будет
тогда совпадать с N. Значит, точки A, N и L лежат на одной
прямой. Осталось заметить, что из подобия
AN/NL = AB/KL = АМ/МК = АС/2МК = AC/CL,
откуда CN ~ биссектриса треугольника ACL.
54. Ответ: п2. Пример: страна разбита на 2 республики по
п городов в каждой, авиалиниями соединяются только города из
разных республик.
Докажем индукцией по количеству городов следующее утвер-
ждение: если в стране 2п городов, любые 4 из которых соединены
не более чем четырьмя авиалиниями, то всего авиалиний не бо-
лее п2, если же городов 2п + 1, то авиалиний не более п2 + п.
База для четырех городов следует из условия. Переход: если
утверждение неверно для к городов, то, удаляя город, из которо-
го выходит наименьшее количество авиалиний (или один из таких
городов), получим, что утверждение неверно и для к—1 городов.
Действительно, если при к = 2т+1 доказываемое утверждение не
выполнено, то можно считать, что авиалиний ровно п24-п+1. То-
гда найдется город, из которого выходит не более п авиалиний,
иначе всего авиалиний будет не менее (п4-1)(2п + 1)/2 > п24-а4~1«
Закроем в этом городе аэропорт. Тогда в стране останется 2т
городов и (2m)24-1 авиалиний между ними, причем любые четыре
города по-прежнему соединены не более чем четырьмя авиалини-
ями. Это противоречит предположению индукции. Аналогичное
рассуждение верно при к = 2т.
♦ Обозначим
, ч f а2/4, если п четно ,
/(«) = S/2 1 \ / 1
I (гг — 1)/4, если п нечетно.
-40-
Тогда если в графе с п вершинами любой подграф с к вершинами
содержит не более f(k) ребер, то в самом графе не более f(n)
ребер.
55. Решение 1. Заметим, что max(a,6) min(a,с), так как
первое из этих чисел не меньше а, а второе - не больше а. Значит,
шах(с, 1997) шш(Ь, 1998). Заменяя левую часть этого неравен-
ства на г (от этого она не увеличивается), а правую часть - на b
(от этого она не уменьшается), получаем требуемое неравенство
с Ъ.
Решение 2. Складывая очевидные неравенства max(a,6) > b
и шах(с, 1997) с, получаем, что левая часть данного в условии
равенства не меньше Ъ + с. Складывая неравенства min(a,c) с
и шш(Ь, 1998) 6, получаем, что правая часть не больше Ь + с.
Но левая часть равна правой, поэтому во всех складывавшихся
неравенствах достигается равенство. В частности, тах(а, Ъ) = 6,
откуда b а. и шш(в,с) = с, откуда с а. Значит, 6 > а > с.
Замечание. Условие задачи эквивалентно системе неравенств
1997 < с < а < Ъ 1998. Доказательство аналогично решению 2.
56. Пусть Н - основание высоты, опущен- д
ной из А на ВС. Угол BCD - прямой, так
как BD - диаметр окружности. Четырех- / / уЛ
угольник BECD составлен из треугольников I / &
BCD и ВСЕ, в которых DC и ЕН являются с
высотами, опущенными на ВС. Значит, его °
площадь равна ^ВС(ЕН +CD). Поскольку
площадь треугольника АВС равна ^ВС • АН, достаточно дока-
зать, что ЕН + CD = АН. Прямые АЕ и DC параллельны, так
как они перпендикулярны ВС. Значит, четырехугольник ADCE -
равнобочная трапеция, так как он вписан в окружность. Величи-
на EH + CD равна сумме проекций отрезков СЕ и CD на прямую
АЕ, т. е. проекции отрезка ED на АЕ. Так как в равнобочной
трапеции диагонали равны и образуют одинаковые углы с осно-
ванием, проекция ED на АЕ по длине равна проекции АС на АЕ,
которая совпадает с АН.
57. Пусть закрытый мост М соединяет острова А и В. Рас-
стояние (наименьшее число мостов) между какими-то островами
может увеличиться при закрытии моста М только в том случае,
когда до закрытия любой кратчайший путь между этими остро-
вами проходил через М. Кроме того, ясно, что любой участок
-41 -
кратчайшего пути тоже является кратчайшим путем, и кратчай-
ший путь не может проходить через один остров два раза.
Предположим, что утверждение задачи не выполняется, т. е.
на каждом острове кто-то живет. Сначала докажем, что после
закрытия моста М с острова А можно добраться до острова В.
Для этого рассмотрим человека, живущего на острове А. Пусть
его друг, расстояние до которого увеличилось на один мост, жи-
вет на острове X. Поскольку кратчайший путь от А до X должен
был проходить через мост АГ, он состоял из переезда через М и
некоторого кратчайшего маршрута от В до X, который при этом
не проходил через М. Значит, от А до В после закрытия моста М
можно добраться, проехав сначала от А до X, а потом повторив
кратчайший маршрут от В до X в обратном направлении.
Рассмотрим кратчайший путь между островами А и В после
закрытия моста М. Выберем остров С посередине или “почти
посередине” этого пути, т. е. так, чтобы расстояния от С до А и
В отличались не более, чем на 1. Пусть Y - тот остров, рассто-
яние до которого от С увеличилось на один мост. Рассмотрим
кратчайший путь от С к У до начала ремонта. Пусть, например,
он шел сначала от С к А, потом через мост М на В, а потом от
В к У. Рассмотрим вместо этого путь, который сначала идет от
С к В (по участку кратчайшего пути от А к В), а потом от В к У
так же, как и в первом пути. Этот путь CBY не длиннее исход-
ного пути CABY, так как участок СВ отличается от участка С А
не более чем на 1. Значит, существовал кратчайший путь от С
к У, не проходящий через мост М. Это противоречит тому, что
расстояние от С до У увеличилось.
♦ Докажите, что если раньше какой-нибудь кратчайший путь
между двумя островами проходил через ныне закрытый мост, то
теперь любой кратчайший путь между теми же двумя островами
проходит через один из необитаемых островов.
60. Занумеруем вершины 1998-угольника по кругу. Тогда ка-
ждый отрезок соединяет четную вершину (= вершину с четным
номером) с нечетной. Действительно, так как отрезки не пересе-
каются, с обеих сторон от любого из них должно лежать четное
число вершин - концов других отрезков. Нарисуем стрелки так,
чтобы полученные векторы вели из нечетных вершин в четные.
Каждый вектор равен разности двух векторов, ведущих из центра
многоугольника в соответствующую четную и нечетную верши-
ны. Поэтому сумма всех нарисованных векторов равна разности
-42-
суммы векторов, ведущих из центра, в четные вершины, и ана-
логичной суммы для нечетных вершин. Четные и нечетные вер-
шины по отдельности образуют правильные 999-угольники с тем
же центром, а сумма векторов, ведущих из центра правильного
999-угольника в его вершины, равна нулю (так как она не изме-
няется при повороте на угол 2тг/999). Значит, сумма векторов,
нарисованных на отрезках, равна нулю как разность двух нуле-
вых векторов.
61. Ответ: (п 4-1)!.
Положим Xk = аь + & — f Для к = 1,2,..., п. Легко проверить,
что замена числа ад. на —(ai 4-F an) - к соответствует замене
числа Xk на — 4----F хп), Добавим к нашей последовательно-
сти еще одно число xQ. Значение xq зададим так, чтобы сумма
xq 4- 4- • * • 4- хп была равна нулю, т. е. xq = —(#i 4--Ь хп).
При преобразовании последовательности на место жд. становит-
ся старое значение а?о, поэтому для того, чтобы сохранить ну-
левую сумму, нужно поставить на место xQ старое значение жд..
Другими словами, данная операция сводится к перестановке чи-
сел xq и Xk- Такими операциями можно получить все возможные
перестановки первоначальных чисел (ж0,Ж1,... ,хп) и только их.
Если все числа xq, .ti, ... , хп различны, то таких перестановок
ровно (п 4- 1)!, а последовательностей (a&) столько же, так как
они находятся во взаимно однозначном соответствии с последо-
вательностями (х^.
Проверим, что при а\ = * • • = ап = 0 числа жо,Ж1,... }хп дей-
ствительно различны. При 1 к п числа жд. = к— | принимают
различные значения от — *4^ до Число xq равно
ч п2 п(п4-1) п2 п
-<1+2+-'+")+т = —+
т. е. оно меньше всех остальных чисел Xk-
62. Задачу можно решить аналогично задаче 55. Впрочем, на
олимпиаде многие участники перебирали возможные взаиморас-
положения данных величин (24 варианта) или различные вари-
анты “раскрытия ” максимумов и минимумов (16 вариантов).
63. Обозначим t = [Уп]. Тогда t2 4- 1 п 4- 1 t2 4- 2t 4-1.
По условию, п 4- 1 делится на t 4- 1. Значит, п 4- 1 = t2 4-1 или
п 4-1 = t2 4- 2t 4-1. Тогда (п - 1)(п - 3) = (t2 4-1 - 2)(t2 4-^-4) или
(n — l)(n — 3) = (t2 4- 2t — l)(t2 4- 2t — 3). Оба выражения делятся
на t — 1.
-43-
65. Всякая плоскость, проходящая через центр куба, делит
объем куба пополам. Это следует из соображений центральной
симметрии. Обратно, всякая плоскость, делящая объем куба по-
полам, проходит через центр куба. Действительно, если бы это
было не так, то мы могли бы выполнить такой параллельный пе-
ренос данной плоскости, чтобы она стала проходить через цент])
куба. Но при таком движении плоскости объем одной из частей
куба будет увеличиваться, объем другой - уменьшаться, что не-
возможно, так как после переноса объемы опять должны быть
равными.
Итак, обе данные плоскости проходят через центр куба. Ка-
ждая из образовавшихся четвертей куба очевидно представля-
ет собой объединение нескольких пирамид, основания которых -
это части граней куба, а вершины находятся в центре куба. Вы-
сота любой такой пирамиды равна половине длины ребра куба.
Следовательно, площадь поверхности куба в каждой четверти
равна объему этой части куба, деленному на одну шестую дли-
ны ребра куба. Поэтому плоскости делят поверхность куба на
равные части.
66. Решение 1.
\ п / \ nJ \ nJ \ 1 • п / \ 2 • п / \ п • п /
< п.\ —) fi 4—тгг) • • • (1 + ~
\ п / \ г/+ 1 / \ 2п — 1 /
п + 1 п + 2 2п
= /л! ---•-------------- = 2п\
п п + 1 2п — 1
Решение 2 (индукция)^ Докажем это неравенство индукци-
ей по п. При п = 1 имеем равенство. Докажем индукционный
переход.
»+1 1 п 1 1 I 1 1
jjLl п' nJ
По предположению индукции, последнее выражение не превосхо-
дит 2n!(n + 1) = 2(п 4-1)!.
♦ «1, , о>п > 0, «1 4- (i2 4- ... -h ап = 1. Докажите, что
П"=1 (« + «<) <2п'-
-44-
♦ Р ешение 3 (определение числа е). Воспользуемся тем, что
при всех натуральных п (1 4- ^)п < е.
(14-1) (2+1) ... (n+l) = ,t!.(l+_L) (1+-1-) ... (14-—) <
\ п/ х п / X nJ X 1 ♦ п/ х 2 ♦ п/ х п • п/
/ 1 X п
< п! • (1 4— ) < еп!
х п/
Получилось грубо, поэтому будем действовать тоньше
(1+1) (2+1) ... (п+1) = „!-(1+_1_) (1+JL) ... (14-—) <
х nJ \ п / х п/ х 1-п/х 2 • п/ X п • п /
1 + 1 Л . 1 V‘ J 7- 2п + 2
При п 2 v/e • G>/е/5 < 1.98.
ф Константа 2 в правой части неравенства слишком груба при
больших п. Действительно, так как 1 4- х < ех при х 0, а
1 4- | 4--F ~ Inn 4-1, то
Так как lim = 0, мы получаем, что левая часть исходного
п—*+оо ”
неравенства при п -+ 4-оо асимптотически равна п!.
67» Ответ: всегда можно определить четыре числа. Суще-
ствуют такие расстановки чисел, для которых больше четырех
чисел узнать не удастся.
Будем использовать шахматные обозначения: число, написан-
ное на клетке al, обозначим 41, число на клетке е8 — Е8 и т.д.,
а для чисел на карточках будем использовать строчные буквы:
«5 - число, написанное на карточке, лежащей на клетке а5, и
т.д. Проверим, что всегда можно найти числа (73, С6, F3, F6.
Действительно, нетрудно видеть, что сумма всех чисел на доске
равна Ъ1 4- Ь4 4- Ь7 4- cl 4- с4 4- с7 4- hl 4- М 4- h7 (на рисунке изобра-
жены прямоугольники, соответствующие указанным карточкам).
С другой стороны, сумма всех чисел, за исключением СЗ, равна
(см. второй рисунок) a44-a74-614-d54-d84-e24-<754-#84-/&2. Значит,
(73 равно разности этих двух выражений.
-45-
—
Число С6 можно найти ещё проще: С6 = а8 + Ь7 — а7 — 68. После
этого найдем F3 из равенства
F3 — С6 = с/2 — hl - el 4- dl - 61 + а2 — а4 4- «54-
4- а8 ~ 67 4- d8 - е8 4- д8 — h7 4- 65 — 63 ,
а затем F6 - из равенства
F6 4- СЗ - CG - F3 = (Z4 4- е5 - d5 - е4.
Надеемся, у читателя все в порядке с чувством юмора.
Теперь приведем пример двух расстановок чисел на доске,
для которых совпадают числа на всех карточках (все они равны
двум), но при этом сами расстановки имеют совпадение только
в четырех “необходимых” клетках. Это доказывает, что более
четырех клеток определить, вообще говоря, нельзя.
0 1 1 0 1 -1 0 1 1 0 -1 1 0 1 1 0
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 -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 0 1 1 0 1 -1 0 1
1 -1 0 1 -1 0 1 -1 -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 0 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. В силу свойства вписанных углов _____в с
AEFD = AEOD = ABAD = ABCD, по-
этому четырехугольник BFDC - вписан- ( / /
нъМ. Тогда ABCF = ABDF = AOEF = I
АО АВ = AACD, откуда АВС А = AFCD. \^F\/ V
-- ГТ о
71. Проведем через каждый узел
внутри ломаной вертикальную и горизонтальную прямые. Пусть
в результате получилось п различных вертикальных прямых и т
горизонтальных. Поскольку каждая из этих прямых пересекает
ломаную в двух точках, то достаточно доказать, что m + n > 20.
Действительно, по условию тп 91, а если т + п 19, то в силу
неравенства о средних тп tm.±ILL = 9()1,
72. Обозначим через х и у числа amam_j...«1999 и «1998 .. .<4
соответственно. Тогда данное условие можно переписать в ви-
де* 10199Н.г 4- у = х2 4- у2, откуда я (101998 - х) = у(у - 1). Сле-
довательно, если число ху удовлетворяет условию, то и число
(101998 — х)у также удовлетворяет условию. Таким образом, все
искомые числа разбиваются на пары. Осталось заметить, что
поскольку ai998 /= 0, то у 1019®7 и 0 < х < 101998, значит,каждое
число имеет пару. Если же числа в паре совпадают, то число
у (у — 1) будет точным квадратом, что невозможно, так как оно
больше (i/ — I)2, но меньше у2.
73. Пусть л’о > Xi > • • • > х’9 - третьи по величине числа в
строках. Заметим, что существует не более 20 чисел, которые
могут быть больше хд, это первые и вторые по величине числа
в строках, следовательно,хо 80. Аналогично, 72. Рассмо-
трим строку, содержащую хд, Сумма чисел в ней не превосходит
1004-994-^9 4- (.T9 — 1)4-1- - 7) = 8x9 4-171. Сумма же третьих
чисел не меньше 804-724-(#<) 4-7) 4-----hхд = 8х9 4-180, т. е. больше,
чем сумма чисел в строке, содержащей хд.
74. Назовем данный четырехугольник
ABCD, О - точка пересечения его диагона-
лей, К и L - ее проекции на стороны ВС и
AD, М и N - середины сторон АВ и CD со-
ответственно. Пусть Р и Q - середины от-
резков АО и ОВ соответственно. Так как
медиана прямоугольного треугольника, проведенная из прямо-
го угла, равна половине гипотенузы, то МР = ВО/2 = KQ,
-47-
LP = АО/2 = MQ. Кроме того, в силу подобия треугольников
AOL и ВОК Z.APL = £BQK, также /.АРМ = /АОВ = /BQM,
значит, /MPL = Z.MQK. Следовательно, ДМРЬ = &KQM и
ML = КМ. Аналогично, KN = NL и точки К и L симметричны
относительно прямой MN.
Замечание. Внимательный читатель, вероятно, обратил вни-
мание на то, что расположение точек, приведенное на картинке,
на самом деле невозможно.
75. Сумма всех найденных чисел равна количеству пар “тре-
угольник и точка внутри него”. Каждая такая пара определяет
четыре точки из множества М, и при этом каждая четверка то-
чек учитывается не более одного раза, так как из четырех то-
чек только одна может лежать внутри треугольника, образован-
ного тремя другими. Значит, сумма найденных чисел не пре-
восходит количества четверок, т. е. С\ = 'Х^Х^^ХУт3)., Ко-
личество же этих чисел равно количеству треугольников, т. е.
, поэтому среднее арифметическое не превосхо-
дат C^/Cl = ,
ф Докажите, что среднее арифметическое этих чисел не пре-
восходит даже п/5 (при п > 4).
76. Ответ: выигрывает первый игрок. Каждую позицию
будем задавать парой чисел (а, 6), где а и 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 - сумма чисел на одном листе, тогда сумма чисел
на всех листах равна ION. Пусть п - наибольшее целое число,
для которого 2n N. На листах могут быть написаны только
числа 2П, 2П~1, ... , 1. Если каждое из них встречается не более
5 раз, то их сумма не превосходит
5(2” + 2П"1 + 4-1) = 5(2”+1 - 1) = 10 • 2” - 5 < 107V.
79. Да, могут. Сопоставим городам числа Ci, ... , c199g так,
чтобы все попарные суммы чисел с4 были различными (например,
можно положить Ci = 2*). Пусть цена билета между двумя горо-
дами равна сумме чисел, сопоставленных этим городам. Тогда
все цены различны, но стоимость любого круго- р
вого маршрута равна 2(сх 4-h Ciggs).
80. Пусть ЛАСВ = ЛСАВ = 2а, тогда
ZADC = 6а, ЛСАЕ = а и F с
ЛАЕС = 180° - ЛСАЕ - ЛАСЕ = 180° - За. ''^1
Заметим, что а < 30°, так как 6а < 180°.
Пусть О - центр описанной окружности треугольника АЕС. По-
-49-
скольку угол АЕС - тупой (ЛАЕС = 180°-За > 180°-3-30° = 90°),
точки О и Е лежат в разных полуплоскостях относительно АС,
и ЛАОС = 3G0° — 2ЛАЕС = Ga. Поскольку АОС - равнобедрен-
ный треугольник с основанием АС и углом 6а при вершине, он
совпадает с треугольником ADC. Таким образом, D - центр опи-
санной окружности треугольника АЕС, в частности, DE = DC.
Значит,
ЛЕЕС = ЛОСЕ = ЛАСЕ 4- ЛОСЕ = 2а 4- (90° -За) = 90° - а,
ЛЕЕС = 180° - ЛЕСЕ - ЛЕЕС = 180° - 2а - (90° - а) = 90° - а.
Таким образом, в треугольнике CEF углы Е и F равны, значит,
он равнобедренный.
81. Положим с = п2 -|-1, а = п2 4-2, Ъ = п2 4-п4-1. Легко видеть,
что при п > 1 эти числа действительно различны и лежат в ука-
занном интервале. Поскольку а дает при делении на с остаток 1,
а b - остаток п, а2 4- Ь2 дает тот же остаток, что и п2 4-1, то есть
делится на с.
84. Ответ: 2999 4- 1.
Среди расстановок, удовлетворяющих условию, есть три три-
виальных, в которых все буквы одинаковы. Докажем, что коли-
чество нетривиальных расстановок равно 2999 — 2.
Установим взаимно однозначное соответствие между нетриви-
альными расстановками, удовлетворяющими условию, и такими
расстановками букв Д, В и К, в которых любые две соседние
буквы различны. Для удобства изложения буквы расстановок
второго вида будем располагать между отмеченными точками.
Пусть X - расстановка без повторений. Чтобы получить соот-
ветствующую ей расстановку У, поставим между каждыми двумя
соседними буквами расстановки X букву, отличающуюся от них
обеих. Поскольку соседние буквы в X различны, это определяет
расстановку У однозначно. Докажем, что расстановка У удовле-
творяет условию. Буквы, отличные от Д, стоят в ней в тех точ-
ках, рядом с которыми в расстановке X имеется буква Д. Значит,
все такие буквы разбиваются на пары соседних - те пары букв,
между которыми стоит буква Д расстановки X. Следователь-
но, их количество на любой дуге между двумя буквами Д четно.
Аналогично, то же верно для букв В и К, значит, расстановка У
удовлетворяет условию. Заметим также, что она нетривиальна.
Действительно, если бы она состояла из одинаковых букв, на-
-50-
пример, букв Д, то расстановка Лг состояла бы из чередующихся
букв В и К, что противоречит нечетности количества точек.
Докажем теперь, что указанное соответствие действительно
является взаимно однозначным. Сначала проверим, что расста-
новка Y не может получаться из двух разных расстановок X и
X'. Найдем в расстановке У две разные буквы, стоящие рядом.
Между ними в расстановках X и X' должна стоять буква, от-
личающаяся от них обеих, что определяет эту букву однознач-
но. Но, как легко убедиться, если X и X* совпадают хотя бы
в одной букве, то они должны совпадать всюду. Наконец, до-
кажем, что любая нетривиальная расстановка У, удовлетворя-
ющая условию, может быть получена из некоторой расстанов-
ки X. Поставим между каждой парой соседних различных букв
расстановки У букву, отличающуюся от них. Для каждого ин-
тервала расстановки У, состоящего из одинаковых букв, мы тем
самым зафиксировали буквы около его концов. Чтобы получить
искомую расстановку X, достаточно расставить между буквами
каждого такого интервала две отличные от них буквы так, что-
бы они (включая уже имеющиеся буквы около концов) чередова-
лись. Если для какого-то интервала это невозможно, то имеет
место один из двух случаев:
1) интервал состоит из нечетного числа одинаковых букв и
заключен между двумя одинаковыми буквами или
2) интервал состоит из четного числа букв и заключен между
разными буквы.
Первый случай немедленно вступает в противоречие с услови-
ем. Во втором случае занумеруем отмеченные точки так, чтобы
точки рассматриваемого интервала расстановки У имели номера
от 2 до 2т -h 1. Пусть, для определенности, в точке 1 стоит буква
Д, в точках от 2 до 2т 4-1 - буква В, в точке 2т 4- 2 - буква К.
Докажем, что для любого п буквы в точках 2п и 2п 4-1 одинако-
вы. Индукция (база - п т). Пусть п > т. Рассмотрим дугу,
последняя точка которой - 2п 4-1, а первая - 1, 2m 4-1 или 2m 4- 2,
в зависимости от того, Д, В или К стоит в точке 2п 4- 1. Если
выполняется предположение индукции, т. е. буквы в каждой паре
точек 2 и 3, ... , 2п — 2 и 2п — 1 одинаковы, то на рассматриваемой
дуге, кроме точки 2п, имеется четное число букв, отличных от
концов. Чтобы это свойство сохранилось для всей дуги, буква
в точке 2п должна быть такой же, как в концах дуги, т. е. совпа-
дать с буквой в точке 2п 4- 1. Утверждение доказано.. Применив
- 51 -
его к п = 500, получим противоречие. Это заканчивает проверку
взаимной однозначности соответствия.
Осталось найти количество расстановок, в которых любые две
соседние буквы различны. Пусть .г„ - количество таких расста-
новок в п отмеченных точках. Непосредственно проверяется, что
х2 = #з = G. Выделим три подряд стоящие точки А, В и С из п от-
меченных. Расстановки бывают двух видов: те, в которых буквы
в точках А и С различны, и те,в которых они одинаковы. Расста-
новки первого вида получаются из правильных расстановок букв
в п-1 точках (всех, кроме В) добавлением (единственно возмож-
ной) буквы в точке В. Расстановки второго вида получаются из
правильных расстановок букв в п — 2 точках (всех, кроме А и В)
добавлением в точке А такой же буквы, какая стоит в С, и доба-
влением в точке В одной из двух других букв. Отсюда следует
формула хп = 4- 2хп^29 из которой по индукции выводится,
что хп = 2" 4- 2 для четных п и хп = 2П — 2 для нечетных п,
ф Каков ответ в исходной задаче для 1000 точек?
85. Ответ: выигрывает первый игрок.
Известная задача об игре со спичками (без обменов на ириски)
уже несколько веков кочует по книгам, посвященным математи-
ческим развлечениям. Впервые она появилась, вероятно, в книге
Гаспара Клода Баше де Мезириака (1581-1638) “Игры и зада-
чи, основанные на математике” (Backet C.-G. Problemes plaisans et
clelectables qui se font par les nombres. Paris, 1612). Однако пред-
ложенная на олимпиаде задача не имеет столь длинной бороды.
Когда у вас на руках много спичек, вы получаете возможность в
невыгодном положении ничего из кучи не брать. Это обстоятель-
ство существенным образом отличает эту игру от игры Баше.
Предъявим выигрышную стратегию для первого игрока. Если
перед очередным его ходом в куче больше 16 спичек, то первый
игрок должен взять пять спичек. За один ход первый и второй
игроки вместе берут не более 10 спичек, поэтому в какой-то мо-
мент первому игроку (впервые) предстоит делать ход, когда в
куче будет от 7 до 16 спичек. Отметим, что в этот момент у
первого игрока будет на руках не меньше спичек, чем у второго.
Если в куче оказалось от 7 до 11 спичек, то первому следует взять
столько спичек, чтобы в куче осталось 6 спичек. Это приведет
к выигрышу первого игрока, потому что брать спички в такой
ситуации - проигрыш для второго игрока, а возможностей обме-
на у него не больше, чем у первого. Если в куче остается 12-15
-52-
спичек, то первому следует взять пять спичек. Ответным ходом
второй не может оставить в куче меньше шести спичек (это про-
игрыш), значит, он возьмет не 5 спичек, а тогда у первого есть
преимущество по числу возможных обменов, поскольку количе-
ство спичек у него, в силу нашей стратегии, делится на 5, а у
второго игрока спичек меньше (хотя бы за счет последнего хо-
да). Осталось разобрать случай, когда в куче 16 спичек. В этот
момент из кучи взято 650 спичек, значит, у первого не меньше
325 спичек. Первому следует в этом случае взять четыре спич-
ки. После ответного хода противника в куче останется от 7 до И
спичек, первый возьмет одну или больше (чтобы в куче осталось
6 спичек) и будет иметь не менее 330 спичек, что опять дает ему
преимущество в обменах, так как обмены начинает второй.
86. Заметим, что £EFC = Z.ECA, &
как опирающиеся на одну дугу окружности /
ECF, а ЛЕСА = ЛЕВВ> так как четырех- nf \ \ G
угольник ADEC вписанный. Таким обра-
зом, £EFC = Z.EDB. Значит, прямые АВ и
CF параллельны. Обозначив через G точку
пересечения прямых CF и ВК, а через G\~
точку пересечения прямых АЕ и CF, мы видим, что в треуголь-
нике АВК медиана DK делит прямую CG, параллельную осно-
ванию, на два равных отрезка. Значит, CF = CG. Аналогично
прямые АЕ, DE и BE высекают на прямой CF два, равных от-
резка. Значит, CF = FG\. Поэтому точки Gh(?i совпадают, и
прямые ВЛ’, АЕ и CF пересекаются в точке G.
87. Ответ: да, можно.
Решение 1. Можно считать, что центры кубиков располо-
жены в точках (х,?/, z), х, у, z € Z, 0 х,у, z 7. Отметим все
клетки, центры которых имеют сумму координат, кратную вось-
ми. Нетрудно сообразить, что таких клеток будет ровно 64, по 8
в любом слое, параллельном грани. Допустим, что нам удалось
выбрать восемь отмеченных клеток, никакие две из которых не
лежат в одном слое, параллельном грани. Тогда сумма коорди-
нат этих клеток должна быть равна утроенной сумме чисел от 0
до 7. Этого не может быть, поскольку это число не делится на 8.
Решение 2. Отметим в каждом горизонтальном слое 8 куби-
ков таким образом, чтобы никакие два кубика этом слое не нахо-
дились “в одной строке” или “одном столбце”, и чтобы ни один
из кубиков, расположенных в первых семи слоях,не был распо-
-53-
ложен ни под одним из кубиков восьмого слоя. Например, можно
считать, что кубики в первых семи слоях стоят по диагонали,
а в восьмом - по сдвинутой диагонали. Вид сверху показан на
рисунке. Если мы уже выбрали 7 отмечен-
ных кубиков в первых семи горизонтальных
слоях так, что никакие два из них не ле-
жат в одном слое, то положение кубика в
восьмом слое, при котором он не попадает
в один слой ни с каким из уже выбранных
кубиков, определяется однозначно, причем в
силу сделанного выбора расстановки в вось-
мом слое, этот кубик будет неотмеченным.
♦ В клетках доски n х п расставлено несколько шашек так, что
на каждой горизонтали и на каждой вертикали стоит т шашек
(при этом на одной клетке может стоять сразу несколько шашек).
Докажите, что шашки можно раскрасить в т цветов так, чтобы
ни на какой вертикали и горизонтали не стояло бы двух шашек
одного цвета.
♦ Рассмотрим множество всевозможных пхп матриц с неотри-
цательными вещественными элементами, в которых сумма эле-
ментов любой строки и любого столбца равна 1. Множество та-
ких матриц можно отождествить с некоторым выпуклым много-
2
гранником Я пространстве R” . Теорема Биркгофа - фон Неймана
утверждает, что вершины этого многогранника - это всевозмож-
ные перестановочные матрицы, то есть матрицы, в каждой стро-
ке и каждом столбце которых содержится ровно одна единица, а
остальные элементы нули. Эта теорема следует из вышеприве-
денной задачи.
Для “трехмерных” матриц ситуация совершенно иная. Множе-
ство “кубических” “неотрицательных” матриц с одинаковой сум-
мой элементов по всем слоям является многогранником, среди
вершин которого “подстановочные” матрицы составляют лишь
малую часть. Именно этим объясняется то, что конструкция ре-
шения 2 имеет такую степень свободы.
88. Ответ: данному уравнению удовлетворяют только кон-
станты.
Воспользуемся данным равенством, подставив его самого в се-
бя несколько раз:
Р(х, у) = Р(х + у, х - у) = Р((х + у) + (у-х),(у-х>)- (х- + у)) =
-54-
~Р(2у, —2а:) = Р(2(-2;г), -2(2;//)) = Р(-4а:, -4^> .. . = Р(16х, 16//),
Отсюда следует, что при всех т € N Р(х,у) = Р(16тх,16ту).
Проверим, что непостоянный многочлен не может удовлетво-
рять такому соотношению. Действительно, пусть Р(х, у) =
52fc=o гДе Qk(x,y) ~ однородный многочлен степени к,
qn 0. Выберем числа жо, уо так, чтобы <7п(-Го,3/о) / 0- Тогда
п
Р(*о,1/о) = Р(16”1.со, 16туо) = 52 ™ктдк(х0,у0).
А,=0
Правая часть последнего выражения представляет собой много-
член (степени не меньше 1) от 16w, с ростом т она стремится к
бесконечности, чего не может быть, так как левая часть при этом
фиксирована.
89, Докажем это неравенство по индукции. При п = 1 имеем
очевидное равенство. Пусть п > 1 и для всех меньших значений
неравенство уже доказано. Пусть - сумма векторов из левой
части неравенства. Векторы, которые образуют с угол от 0°
до 180° (против часовой стрелки), начнем поворачивать по ча-
совой стрелке, от этого проекция суммы всех векторов A2i-iA2i
на вектор V будет возрастать. Векторы, образующие с V угол
от 0° до —180°, будем поворачивать против часовой стрелки, от
этого проекция суммы всех векторов Агг-Мй» на вектор V так-
же будет возрастать. В результате этих поворотов мы сумеем
добиться того, чтобы конец какого-нибудь из векторов совпал с
началом следующего за ним по часовой стрелке вектора (в про-
тивном случае, нам удалось бы, ни разу не совместив концы век-
торов, сделать всех их параллельными вектору V. Это возможно
только если у нас всего один вектор). Поскольку проекция сум-
мы интересующих нас векторов на вектор V увеличилась, то,
следовательно, увеличилась и длина самой этой суммы. Теперь
мы можем заменить два склеившихся вектора на их сумму и при-
менить предположение индукции.
90. Заметим, что при всех четных п d(n2 4-1) < п. Действи-
тельно, так как число п2 4- 1 не является точным квадратом, то
все его делители можно разбить на пары вида (d, (п2 4- l)/d), где
d < п, причем d - нечетно. Количество натуральных чисел во
всех таких парах очевидно не превосходит п.
- 00 -
Допустим теперь, что при п N последовательность d(n2 4-1)
монотонна, обозначим б = d(N2 4- 1)* Так как d(n2 4- 1) всегда
четно, то при всех п d((n 4- I)2 4- 1) > d(n2 4- 1) 4- 2 или, в более
общем виде, </((п4-&)24-1) cZ(n24-l)4-2fc. Возьмем любое s > N—б
(такое, чтобы N 4- $ было четным). Тогда
d((W 4- s)2 4-1) > d(N2 4-1)4-2s = 64-2s>7V + $,
что противоречит неравенству d(n2 4-1) < п.
91. Ответ: да, может.
Мы будем использовать то, что 169 = 132. Рисунок был за-
думан как пояснение того, как можно организовать дежурство
тринадцати человек. Здесь вершины-“колесики” соответствуют
дружинникам, а эллипсы, окружности и прямые - дежурствам.
Нетрудно проверить, что на каждой из упомянутых линий лежит
ровно четыре вершины и любые две вершины лежат ровно на
одной общей линии.
Эту же конструкцию можно реализовать так: пронумеруем
дружинников числами от 0 до 12, и для каждого к от 0 до 12
рассмотрим четверку, состоящую из дружинников с номерами к,
-56-
к + 2, /г 4- 3, к 4-7 (сложения по модулю 13). Нетрудно проверить,
что любые два дружинника входят вместе ровно в одну четверку.
Теперь покажем, как можно организовать дежурства 169 че-
ловек. Разобьём этих дружинников на 13 бригад по 13 человек;
по-прежнему будем нумеровать дружинников числами от 0 до 12,
так же пронумеруем и сами бригады. Для каждой бригады ре-
ализуем предложенную выше схему разбиения на четверки. Мы
получим, что любые два дружинника из одной бригады дежу-
рили вместе ровно один раз. Для того чтобы обеспечить такое
же свойство для дружинников из разных бригад, для каждого
целого п от нуля до 12 построим разбиение дружинников, ска-
жем, на группы захвата, а именно: в одну группу захвата с &-м
дружинником из нулевой бригады поместим (к 4- п)-го дружинни-
ка из первой бригады, (к 4- 2п)-го дружинника из второй брига-
ды, и т.д., (к 4- 12п)-го дружинника из двенадцатой бригады (все
сложения по модулю 13). Очевидно, что при фиксированном п
это действительно разбиение всех дружинников на 13 непересе-
кающихся множеств, и любые два дружинника из разных бригад
при ровно одном значении п оказываются в одной группе захвата
(чтобы найти это п для р-го дружинника из r-й бригады и д-го
дружинника из s-й бригады, нужно решить по модулю 13 урав-
нение р 4- ($ — 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). Но отображение с ненулевым индексом
не может продолжаться до отображения квадрата в окружность.
Это утверждение является одной из формулировок известных то-
пологических теорем Брауэра и Борсука. О связанных с этим
вопросах можно прочитать в книгах Шашкин Ю.А. Неподвиж-
ные точки. M.I Наука, 1989 (Популярные лекции по математике,
вып. GO), Прасолов В.В. Наглядная топология. M.Z МЦНМО, 1995.
Приведенные решения имеют много общего с классическими
методами топологии. Первое аналогично лемме Шпернера, вто-
рое использует идеи теории гомотопий, третье похоже на дока-
зательство теоремы Борсука, данное Дж. Милнором (см. Милнор
Дж., Уоллес А. Дифференциальная топология. Начальный курс.
М.: Мир, 1972).
-59-
93. Мы воспользуемся следующим хорошо известным равен-
ством :
2 + 2 = 2-2. (1)
Поскольку три подряд стоящих числа на окружности - это две
единицы и двойка, либо двс^ двойки и единица, то равенство (1)
показывает, что произведение трех подряд стоящих чисел вдвое
больше количества двоек среди них. Следовательно, искомое
произведение равно удвоенному количеству двоек во всех трой-
ках подряд стоящих чисел, что в шесть раз больше числа двоек
на окружности. Ответ: 180.
Як 94. Пусть S - точка пересечения перпен-
/ \ дикуляров, проведенных из точек М и К, Т -
/ \ точка пересечения перпендикуляров, прове-
N денных из точек М и Аг. Четырехугольник
\ AMSK вписанный, поэтому
4 м с AS AM = ASKM = АВКМ - 90° .
Аналогично, АТСМ = ABNM - 90°. Итак, ASAM = АТСМ.
Вспоминая теперь, что точки S и Т лежат на серединном перпен-
дикуляре к отрезку АС, мы видим, что они совпадают. Разбор
различных случаев взаимного расположения точек оставляем чи-
тателю.
95. Пусть V - та вершина, из которой выходили два удален-
ных ребра, будем считать, что она первого цвета. Рассмотрим
компоненту связности, в которую попала вершина V после уда-
ления ребер. Обозначим Ау; А2, A3, А4 - множества вершин соот-
ветственно первого, второго, третьего, четвертого цветов в этой
компоненте. Заметим, что из А2 в А1? Аз и А4 до выкидывания
вело поровну ребер, обозначим это количество ребер через к.
Тогда из Аз и А4 в. остальные множества также выходило по к
ребер. Следовательно, из Ai внутрь компоненты связности до
выкидывания вело кратное трем число ребер. Следовательно, и
за пределы этой компоненты из множества Ai вело кратное трем
число ребер. Но тогда удаление двух ребер не могло изолиро-
вать эту компоненту, значит, она совпадает со всем графом.
96. Докажем более сильное утверждение: если максималь-
ная система из непересекающихся квадратов содержит не более
к квадратов, то все множество квадратов можно разбить на 2к — 1
-60-
подсистем, в каждой из которых все квадраты имеют общую точ-
ку, такие подсистемы будем называть полными.
Доказательство будем проводить индукцией по к. База к = 1
очевидна. Пусть утверждение выполнено для к = I - 1. Дока-
жем его для к = I. Считая, что стороны квадратов горизонталь-
ны и вертикальны, выберем самый нижний квадрат (или один
из нескольких самых нижних), назовем его Q. Рассмотрим все
квадраты, которые с ним не пересекаются. Для них выполнено
предположение индукции (при к = I — 1), следовательно, их мож-
но разбить на 2£ — 3 полных подсистем. Добавим теперь к этим
подсистемам подсистему, состоящую из квадратов, содержащих
правую верхнюю вершину квадрата <2, и подсистему, состоящую
из остальных квадратов (они все содержат левую верхнюю вер-
шину Q). Мы получили искомое разбиение.
97. Продолжим противоположные
стороны нашего четырехугольника до
пересечения (см. рисунок; случай па-
раллельных сторон проще и оставля-
ется читателю на доработку). Заме-
тим, что биссектрисы углов В и С ис-
ходного четырехугольника - это бис-
сектрисы внешних углов треугольни-
ка ВЕС. Поэтому точка К лежит на
биссектрисе угла Е. Поэтому отрезок КМ лежит на биссектрисе
угла Е. Аналогично LN лежит на биссектрисе угла F. Заметим,
что Z.FPQ = ЛРВЕ 4- Z.PEB = Z.EDQ + £QED = Z.FQP. Зна-
чит, FQ = FP, биссектриса угла F перпендикулярна отрезку PQ,
следовательно, КМ ± NL. Осталось проверить, что МК и NL -
действительно диагонали выпуклого четырехугольника KLMN
(как на рисунке). Это следует из того, что отрезок МК пере-
секает биссектрису угла F (так как в противном случае DM и
СК не смогли бы пересечься на этой биссектрисе) и аналогично
отрезок NL пересекает биссектрису угла Е.
98. Допустим, что мы сумели подобрать такие натуральные
числа а > с d > &, что ab = cd > п4/16. Обозначим р = а + Ь,
q = а — Ь, г = с 4- d, з = с — d. Тогда q п, р > г. Так как
р2 - q2 = 2а • 2Ъ = 2с • 2d = г2 - з2 > п4/4, то р2 — г2 = q2 - з2
и г2 > п4/4. Заметим теперь, что q2 — s2 q2 п2, а с другой
стороны, р2 - г2 (г 4-1)2 — г2 = 2г 4-1 > п2 4-1. Противоречие.
-61-
99. Докажем сначала утверждение задачи для центрально
симметричных многоугольников. Заметим, что каждый из них
можно разбить на п(п — 1)/2 параллелограммов, вершины кото-
рых лежат в узлах решетки. Площадь каждого такого паралле-
лограмма не меньше единицы (здесь уместно припомнить форму-
лу Пика - см. Прасолов В.В. Задачи по планиметрии. Часть 2.
Задача 24.5. М.: “Наука”, 1991; Генкин С.А., Итенберг И.В,, Фо-
мин Д.В. Ленинградские математические кружки. Киров, 1994.
С. 221; либо поговорить о векторном произведении двух целочи-
сленных векторов). Отсюда сразу следует утверждение задачи.
Теперь докажем утверждение задачи для произвольного мно-
гоугольника. Обозначим /(n) = п(п — 1)/2. Рассмотрим диа-
метр d нашего 2п-утольника, пусть он разбивает 2п-угольник на
(fc + 1)-угольник и (£ + 1)-угольник, k + i == 2п. Выполним цен-
тральную симметрию относительно середины диаметра d и рас-
смотрим получившиеся центрально симметричные 2&-утольник и
2Лугольник. Их площади, как доказано выше, не меньше f(k) и
/(£), а площадь исходного 2п-угольника равна полусумме площа-
дей 2к- и 2£-угольника. Так как функция f выпукла (вниз), мы
получаем требуемое.
100. Добавим к данным п векторам еще 2п векторов, получа-
ющихся из векторов данного набора поворотом на 120° по или
против часовой стрелки. Тогда сумма всех полученных векторов
равна нулю, поэтому из них можно составить выпуклый много-
угольник, переходящий в себя при повороте на 120° относительно
некоторой точки О. Рассмотрим окружность длины 3 с центром в
точке О. Поскольку периметр нашего выпуклого многоугольника
равен трем, найдется его вершина X, лежащая вне окружности.
Пусть Y - вершина многоугольника, получающаяся из X пово-
ротом на 120°. Тогда XY > Зу/3/2я. Внутри угла XOY лежит
п векторов-сторон нашего многоугольника. Разобьем их на три
множества: Si - векторы, принадлежащие исходному набору; S% -
векторы, полученные из исходных поворотом по часовой стрелке;
S3 - векторы, полученные из исходных поворотом против часо-
вой стрелки. Пусть $2, $з ~ суммы векторов в этих наборах.
Поскольку |s? 4- $2 + $з | > 3л/3/2тг, то |st| + |$21 4- |$з| > 3у/3/2я.
Осталось заметить, что векторы исходного набора также разби-
лись на три подмножества: Si, векторы, которые после поворота
попадают в S2, и векторы, которые после поворота попадают в
S3. Это разбиение и будет искомым.
-62-
103. Ответ: не существуют. Допустим, что мы нашли тре-
буемые Р и к. Выберем натуральное s\ при котором |P(fcs)| > 1.
Пусть q - любой простой делитель Р(ка). Тогда по малой теоре-
ме Ферма P(kqa) делится на д, чего не должно быть.
105. Заметим, что шестиугольник А4С3В4А3С4В3 ~ описан-
ный, так как в него легко вписывается окружность с центром I
и радиусом, равным рас-
стоянию от I до прямой
АМз (используйте равен-
ство хорд ЛМз, А3А2,
BiB3, В3в2, С\С3, С3С2).
Тогда утверждение задачи
- прямое следствие теоре-
мы Брианшона. См. об
этом ШклярскийД. О., Чен-
цов Н.Н,, Яглом И.М. Из-
бранные задачи и теоремы
планиметрии. М.: “Наука”,
1967, задача 150; Коксе-
тер Г.С.М., Грейтцер С.Л,
В
Новые встречи с геометрией. М.: “Наука”, 1978.
106. Докажем сначала утверждение задачи для центрально
симметричных многоугольников. Пусть
> • • •» , О2 > • • • »
— векторы сторон многоугольника. Здесь не важен порядок сто-
рон, нам будет удобнее считать, что joj | ||а£|. Наш
2п-угольник легко разбить на параллелограммы со сторонами а?
и Oj у 1 i < j nt и тогда его площадь S равна
S — | X Oj I .
Зафиксируем t, 1 i n. Пусть gi(j) = 2|a? x Oj |. Отложим век-
торы Oj, i j < n от начала координат. Допустим, что на вектор
а? попало к+1 узлов решетки (включая концы). Тогда длина век-
тора а/ равна fcg, где q - расстояние между соседними узлами, и
при всех j / г gi(j) - натуральное число, кратное к. Проверим,
что при j > i функция д{ принимает каждое свое значение не бо-
лее 4к раз. Действительно, пусть ^(ji) = = • • = Sj(j4fe+i)-
Тогда концы векторов , ~aj2,... , "а}4Ь+1 находятся на двух пря-
-63-
мых, параллельных прямой, содержащей вектор По крайней
мере 2к 4- 1 из этих концов попадут на одну прямую. А так как
расстояние между соседними узлами на этой прямой также рав-
но q, то найдутся два вектора, разность которых не меньше 2fcg,
чего не может быть по неравенству треугольника в силу упоря-
доченности ДЛИН Oj .
Пусть п — i = 4ks + r (деление с остатком на 4к). Мы доказали,
что при j > i функция gi не более 4к раз принимает значения к,
2к, ... , sk и, значит, не менее г раз принимает большие значения.
Тогда
> 4Л;(Л; 4- 2к 4-F sk) 4- rk(s 4-1) =
j=i-H
= 2k2s(s 4-1) 4- rk(s 4-1) = k(2ks 4- r)(s 4-1).
Из определения чисел $ и г видно, что 2A;s4-r 2ks+r/2 = (n—i)/2,
и $ 4-1 > (п — i)/4k. Поэтому
Теперь легко оценить площадь многоугольника:
- п п 1 п , г .^2
i=l J=t‘+1 i=l
1 ,2 n(n 4- l)(2zz 4-1) n3 n3
“ 16 Z-'4 “ 96 > 48 > 100 ’
t=l
Докажем теперь утверждение задачи для произвольного 2п-
угольника. Обозначим f(n) = 'п3/100. Доказательство завер-
шается буквальным повторением рассуждения из второго абзаца
решения задачи 99.
♦ Оценка вида Сп3 ~ точная по порядку величины. Докажи-
те, что для любого п 2 существует выпуклый 2п-угольник с
вершинами в узлах решетки, площадь которого не больше п3/6.
107. Докажем более общее утверждение, добавив еще один
квантор:
Vn G N Vfc Е N Зе > О Vai,..., ап > 0 3t > 0
{iai{ton} G (e, 1/k).
- G4 -
Доказательство будем проводить индукцией по п. База п = 1
очевидна.
Рассмотрим произвольные положительные числа, «1, «2, • •• ,
ап, причем пусть ап - наибольшее из них. По предположению
индукции, найдется такое t > 0, что
€ (е, 1/(3/г)3), где е = е(п - 1,(ЗА:)3).
Стандартные рассуждения в духе леммы Дирихле показывают,
что среди чисел 2£, ... , 9k2 Зt найдется такое число, скажем
для которого {stan} € (-gjr, д|з)- При этом очевидно
{stoi},..., {stan_i} 6 (е, .
О Av
Возьмем небольшое а > 0 так, чтобы для числа Т = + а число
{Тап} оказалось в промежутке (е, ^). Рассмотрим переменную
ж, пробегающую промежуток (si,T). При движении я от st к Т
точка хап переместилась на расстояние не более 4-
Так как ап - наибольшее из данных чисел, то все остальные точ-
ки — жа1, ... , хап-1 — переместились также на расстояние не
большее gp Значит, мы нашли число Т, для которого все дроб-
ные части {Tai}, • • • , {Tan} попали в промежуток (б, |). Индук-
ционный переход доказан.
108. Построим граф Г, вершины которого соответствуют дан-
ным квадратам, а ребра соединяют вершины, соответствующие
пересекающимся квадратам. Докажем, что граф Г можно раз-
бить не более чем нап — 3 полных подграфов2.
По условию, любое множество вершин графа Г содержит пол-
ный четырехвершинный подграф. Из утверждения, доказанного
в задаче 96, сразу следует, что любой подграф графа Г, макси-
мальный пустой подграф3 которого содержит к вершин, можно
разбить на 2к — 1 полных подграфов. Будем называть это свой-
ство свойством разбиваемости.
Пусть максимальный пустой подграф Г1, содержащийся в Г,
имеет вершин; максимальный пустой подграф Г2, содержащий-
ся в Г \ Г1, имеет €2 вершин; максимальный пустой подграф, со-
держащийся в Г \ Г1 \ Г2, имеет вершин. Очевидно
(-1 + ^2 + ^3 П — 1. (*)
2Под разбиением графа мы понимаем разбиение множества его вершин.
Зт. е. не содержащий ни одного ребра.
-65-
Нам понадобится следующая лемма.
Лемма. Пусть Т - двудольный граф, доли которого содержат
и 82 вершин (51 > 52), а максимальный пустой подграф содер-
жит 51 вершин. Тогда Т можно разбить на 51 полных подграфов
(каждый из которых содержит одну или две вершины).
Доказательство. Каждая вершина первой доли войдет
ровно в один подграф. Возможность разбиения следует из леммы
о девушках (т. е. теоремы Холла о паросочетаниях), не забудьте
воспользоваться условием о максимальном пустом подграфе. □
В силу леммы, граф U Г2 можно разбить на £\ полных под-
графов, а граф Г\ (Г1 U Г2) - в силу свойства разбиваемости - на
2^з - 1 полных подграфов. Значит,
fi 4- 2^з — 1 > п — 1 (**)
(иначе мы сразу найдем искомое разбиение). Сравнивая нера-
венства (*) и (**) и пользуясь тем, что Лг Ль находим, что
Лг = ^з-
Заметим теперь, что граф Г\Г1, опять в силу свойства разби-
ваемости, можно разбить на 2£2 -1 полных подграфов. Покажем,
что тогда граф Г можно разбить на + 2^2 — 2 полных подгра-
фов. Рассмотрим одну из компонент разбиения Г \ 1\ на 2£2 - 1
полных подграфов, назовем ее Q. Пусть ai - любая из £i вер-
шин графа Гр Выделим компоненту, состоящую из ср и всех
вершин подграфа £2, соединенных с ней. Затем рассмотрим лю-
бую другую вершину а2 € Г1 и выделим компоненту, состоящую
из а2 и всех ещё не выделенных вершин Q, соединенных с ней.
Будем выполнять подобные операции со всеми вершинами Гр В
результате каждая вершина Q окажется выделенной, поскольку
существование вершины Q, не соединенной ни с одной вершиной
из Гь противоречит максимальности графа Г]. Таким образом,
мы построили разбиение графа Г на не более чем 4-2^2 — 2 пол-
ных подграфов. Вспоминая, что £2 = Ль получаем, что искомое
разбиение содержит
^1 4- 2€2 — 2 = ^14-Лг+^3“2^п — 3
компонент (мы использовали ещё раз неравенство (*)).
-66-
Подписано в печать с оригинала-макета 6.04.98.
Ф-т 60 х 84/16. Печать офсетная.
Усл.печ.л.3,95. Уч.-изд.л.3,38. Тираж 1000 экз. Заказ /57.
РОПИ Издательства СПбГУ. 199034, Санкт-Петербург,
Университетская наб., 7/9.
Типография Издательства СПбГУ.
199034, С.-Петербург, Университетская наб., 7/9.
Оргкомитет и жюри Санкт-Петербургской олимпиады
школьников по математике приглашают всех, кто заинте-
ресован в процветании точных наук и хотел бы оказать
олимпиадам по математике, физике, химии и информати-
ке финансовую подцержку. Звоните по телефону 310-30-39
(оргкомитет олимпиады).