ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.04.2024
Просмотров: 49
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
731. Через точки касания вневписанных окружностей и проведем перпендикуляры к соответствующим сторонам треугольника. Они пройдут через центры вневписанных окружностей (и I
3
) и пересекутся в некоторой точке O см. рис. 317). Так как и находятся на внешней биссектрисе угла B, то ∠ABI
3
=
∠CBI
1
. Из рассмотрения прямоугольных треугольников и следует, что значит, OI
1
I
3
— равнобедренный.
Обозначим середину отрезка через P . Поскольку OI
1
= OI
3
,
OP
⊥ I
1
I
3
. Рассмотрим окружностьс диаметром OB. На ней лежат точ-
741. Заметим, что b
k
=
a
k
c
k
, где c
k
— наименьший простой делитель Так как b
9
> b
10
, то b
9
> и b
9
c
9
. Отсюда a
10
> a
9
c
2 9
. Но из неравенств a
i
< a
i+1
, b
i
> следует, что c
i
< c
i+1
, те. Значит, c
9
23, так как 23 — девятое по счету простое число.
Поэтому a
10
> c
2 9
529 > 500.
742. Сначала заметим, что поскольку ∠ARP < ∠ARP + ∠QRC =
=
∠ABC, то точка X лежит на луче RP иначе ∠ARP = π − ∠ARX >
>
∠RAX = ∠ABC) (см. рис. 321). Тогда ∠ACB = ∠XAB и ∠AP X =
=
∠RP B = ∠RQC, и треугольники AP X и CQR равны по стороне и двум углам. Следовательно, P X = QR. Аналогично, P R = QY , откуда и следует утверждение задачи. Ответ. Выигрывает игрок, делающий второй ход.
Приведем выигрышную стратегию для второго. Первыми несколькими ходами он склеивает каждую клетку, примыкающую к границе квадрата со всеми ее соседями. На это потребуется не более 8 · 99 ходов, т. е.
после этого будет склеено всего 16 · 99 пар сторон и, как следствие, не более 2 · 16 · 99 <
10 000 2
доминошек окажутся склеенными с чем-нибудь еще. Следовательно, после этого еще останутся отдельные доминошки, и фигура не будет связной. Далее второй будет действоватьпроизвольным образом, следя только затем, чтобы не проиграть прямо нынешним ходом.
Пустьв некоторый момент ему не удастся сделатьэтого. Тогда все доминошки распадаются на две связных фигуры, причем все несклеен- ные отрезки — это граница между этими фигурами, так как любой другой
757. Очевидно, начиная со второго члена, наши последовательности возрастают x
n+2
> x
2
n+1
> x
n+1
, y
n+2
> y
n+1
. Так как x
3
> 1 + 1 2
= 2
,
y
3
> 1 2
+ 1 = 2
, все члены каждой из последовательностей, начиная с третьего, больше 2. Аналогично при n > 3 получим x
n
> 3
, y
n
> Заметим теперь, что x
n+2
> x
2
n+1
> при n > 1. С другой стороны y
2
n
+ y
n+1
= y
2
n
+ y
n
+ y
2
n−1
< 3y
2
n
< при n > Итак, при n > 3 имеем x
n+2
lg y
n+2
>
4 lg x
n
3 lg y
n
, а lg x
2k
lg y
2k
>
4 3
k−1
·
lg x
2
lg При достаточно большом k правая частьпоследнего неравенства больше, а значит, x
2k
> y
2k
, что и требовалось доказать. Из теоремы о трех перпендикулярах следует, что SD — высота в грани SAB. Так как SS
— диаметр окружности, проходящей через S, и A, то ∠SAS
= см. рис. 328). Обозначив через R и r соответственно радиусы описанной сферы пирамиды и вписанной окружности треугольника, имеем S
A
2
= S
A
2
+ AA
2
= (SS
2
− SA
2
) + AD
2
= SS
2
−
− (SA
2
− AD
2
) = SS
2
− SD
2
= SS
2
− (SI
2
+ ID
2
) = (2R)
2
− SI
2
− Аналогично вычисляя и S
C
, получаем, что S
A
= S
B
= S
C
=
=
(2R)
2
− SI
2
− r
2
759. Перепишем условие задачи в виде равенства (x + 1)
n
− 1 =
= P (x)Q(x)
, где P (x) — многочлен с нечетными коэффициентами
К. Кноп 73, 75, 103, 400, А. Ковальджи
(2)
: 499, П. Кожевников 7, 146, 151, 186, 223,
247, 312, 395, 615, 679, С. Кожухов П. Козлов 408, С. Конягин
(1)
: К. Кохась
(2)
: 79, А. Кочерова
(1)
: Д. Кузнецов 17, 55, 138, 177, 633, Б. Кукушкин Е. Куликов 361, 392, 722, М. Куликов Л. Купцов 434, 486, А. Левин
(1)
: Ю. Лифшиц
(9)
: 244, 251, 252, 266, 268, 620,
621, 643, Д. Любшин
(1)
: О. Ляшко
(2)
: 436, Е. Малинникова
(7)
: 9, 24, 108, 465, 519,
521, П. Мартынов Л. Медников 87, 94, С. Мисник
(1)
: Д. Митькин
(2)
: 433, М. Мурашкин
(4)
: 406, 409, 419, О. Мусин
(7)
: 70, 452, 484, 508, 542, 559, Н. Нецветаев
(1)
: В. Ню М. Островский
(1)
: А. Пастор 356, 652, 660, И. Певзнер
(1)
: А. Перлин
(6)
: 11, 12, 27, 427, 456, Ф. Петров 610, О. Подлипский
(27)
: 150, 164, 239, 258, 265,
279, 287, 296, 299, 332, 341, 362, 393, 395,
410, 424, 549, 585, 604, 609, 637, 669, 694,
710, 714, 717, Е. Порошенко
(1)
: В. Произволов
(2)
: 107, А. Протопопов А. Разборов И. Рубанов
(19)
: 44, 76, 100, 121, 147, 148,
149, 208, 226, 267, 277, 293, 304, 316, 325,
330, 432, 512, С. Рукшин
(2)
: 40, А. Савин
(1)
: Р. Садыков
(3)
: 189, 216, Н. Седракян
(1)
: 259 302, 305, 321, 333, 345, 359, 367, 375, В. Сендеров
(28)
: 197, 210, 217, 256, 301,
383, 415, 418, 481, 499, 507, 659, 681, 709,
721, 727, 732, 746, И. Сергеев А. Скопенков
(3)
: 59, 133, Д. Скробот
(1)
: А. Смирнов
(3)
: 696, 699, Л. Смирнова
(2)
: 122, М. Смуров
(6)
: 19, 455, 505, 511, 540, И. Соловьёв
(1)
: М. Сонкин
(34)
: 15, 35, 43, 51, 54, 62, 71, 82,
87, 91, 94, 119, 127, 128, 143, 154, 162, 184,
207, 212, 215, 230, 502, 518, 527, 529, 534,
550, 562, 571, 579, 587, 595, Е. Сопкина
(1)
: Д. Тамаркин
(3)
: 32, 440, Д. Тарасенко
(1)
: О. Тен
(1)
: Д. Терёшин
(19)
: 25, 47, 66, 212, 430, 438,
446, 448, 459, 463, 471, 478, 490, 495, 498,
515, 531, 591, С. Токарев
(27)
: 20, 52, 58, 80, 88, 111, 134,
183, 206, 214, 231, 271, 272, 335, 344, 350,
443, 447, 464, 473, 475, 476, 520, 535, 580,
636, С. Тухвебер
(1)
: В. Уфнаровский
(1)
: К. Фельдман
(1)
: В. Филимонов
(2)
: 364, Фольклор 262, А. Фомин 117, Д. Фон-дер-Флаас
(8)
: 8, 48, 439, 444, 503,
523, 536, Б. Френкин
(1)
: А. Храбров
(19)
: 222, 229, 246, 253, 284, 291,
336, 369, 378, 403, 413, 522, 574, 606, 613,
614, 668, 678, Д. Храмцов
(16)
: 83, 152, 159, 168, 175, 204,
236, 264, 288, 308, 311, 317, 319, 355, Ю. Хромин
(2)
: 320, Д. Цветов Г. Челноков 264, 292, 368, 376, 380, 392,
395, Е. Черепанов
(4)
: 189, 216, 605, Е. Чернышов
(1)
: А. Шаповалов
(25)
: 50, 56, 74, 77, 98, 106,
110, 113, 114, 115, 142, 157, 161, 169, 171,
176, 205, 483, 509, 514, 526, 532, 544, И. Шарыгин
(1)
: И. Ященко
(2)
: 112, Л. Ященко
(1)
: 481
68, 75, 99, 211, 276, 348, 466, 559, 563, 590, 608, 611, 626, 656, 667,
710, Разные задачи на взаимное расположение фигур, 140, 158, 226, 245, 312, 416, 438, 448, 511, 532, 542, 635, 658,
676, 703, Разные оценочные задачи комбинаторной геометрии, 113, 155, 187, 263, 316, 484, 491, 522, 546, 554, 567.
Конструктивы
Разрезания, придумывание интересных геометрических конструкций, 203, 240, 300.
3
) и пересекутся в некоторой точке O см. рис. 317). Так как и находятся на внешней биссектрисе угла B, то ∠ABI
3
=
∠CBI
1
. Из рассмотрения прямоугольных треугольников и следует, что значит, OI
1
I
3
— равнобедренный.
Обозначим середину отрезка через P . Поскольку OI
1
= OI
3
,
OP
⊥ I
1
I
3
. Рассмотрим окружностьс диаметром OB. На ней лежат точ-
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
A
B
C
I
3
I
1
A
B
C
O
P
A
B
C
I
3
I
1
P
Рис. Риски, и P , те. это окружность, описанная около BA
C
. Теперь достаточно доказать, что P лежит на описанной окружности ABC. Из этого будет следовать, что P = B
1
, и A
1
B
1
C
1
— серединный треугольник для I
1
I
2
I
3
, значит, его стороны параллельны внешним биссектрисам ABC. Но внешние биссектрисы параллельны сторонам треугольника, образованного точками касания вписанной окружности со сторонами ABC стороны этих треугольников перпендикулярны внутренним бис- сектрисам).
Проведем из вершин A и C биссектрисы внутренних и внешних углов ABC см. рис. 318). Как известно, две биссектрисы одного угла перпендикулярны. Следовательно, точки I
1
, C, A, лежат на окружности с диаметром и с центром в точке P . Рассмотрим центральный угол этой окружности — ∠AP I
3
. Он опирается на дугу I
3
A
, не нее же опирается вписанный угол ∠I
3
CA =
1 2
∠C. Значит, ∠I
3
P A = 2
∠I
3
CA Из этого следует, что ∠BP A = ∠BCA, те. точки A, B, P , C лежат на одной окружности.
Замечание. Окружность, проходящая через A, B, C, P , является окружностью девяти точек для треугольника I
1
I
2
I
3
732. Имеем (z − 1)(z + 1) = x
y
, НОД(z − 1, z + 1) = 1 при нечетном, НОД(z − 1, z + 1) = 2 при четном x. В первом случае z − 1 = u
y
,
z + 1 = v
y
, где u, v ∈ N; отсюда v
y
− u
y
= 2
. Но, поскольку v > u, y > имеем v
y
− u
y
= (v
− u)(v
y−1
+ . . . + u
y−1
)
(v − u)(2
y−1
+ 1)
Противоречие 2 3. Значит, число x четно. В этом случае одно из чисел 1 и z + 1 делится на 2 и не делится на 4, а второе делится на и не делится на 2
y
. Таким образом, A = 2u
y
, B = 2
y−1
v
y
(u, v — нечетные натуральные числа, где A и B равны, в некотором порядке, числами при этом AB = x
y
). Получили |2u
y
−2
y−1
v
y
| = 2, |u
y
−2
y−2
v
y
| = Отсюда, при некотором выборе знака, u
y
± 1 = Заметим, что u > 1. В самом деле, если u = 1, то A = 2, A = z − 1,
z = 3
, x = 2 — противоречит условию. Кроме того, число y нечетно, в противном случае, если y = 2n, z
2
− (x
n
)
2
= 1
, что невозможно
A
B
C
I
3
I
1
A
B
C
O
P
A
B
C
I
3
I
1
P
Рис. Риски, и P , те. это окружность, описанная около BA
C
. Теперь достаточно доказать, что P лежит на описанной окружности ABC. Из этого будет следовать, что P = B
1
, и A
1
B
1
C
1
— серединный треугольник для I
1
I
2
I
3
, значит, его стороны параллельны внешним биссектрисам ABC. Но внешние биссектрисы параллельны сторонам треугольника, образованного точками касания вписанной окружности со сторонами ABC стороны этих треугольников перпендикулярны внутренним бис- сектрисам).
Проведем из вершин A и C биссектрисы внутренних и внешних углов ABC см. рис. 318). Как известно, две биссектрисы одного угла перпендикулярны. Следовательно, точки I
1
, C, A, лежат на окружности с диаметром и с центром в точке P . Рассмотрим центральный угол этой окружности — ∠AP I
3
. Он опирается на дугу I
3
A
, не нее же опирается вписанный угол ∠I
3
CA =
1 2
∠C. Значит, ∠I
3
P A = 2
∠I
3
CA Из этого следует, что ∠BP A = ∠BCA, те. точки A, B, P , C лежат на одной окружности.
Замечание. Окружность, проходящая через A, B, C, P , является окружностью девяти точек для треугольника I
1
I
2
I
3
732. Имеем (z − 1)(z + 1) = x
y
, НОД(z − 1, z + 1) = 1 при нечетном, НОД(z − 1, z + 1) = 2 при четном x. В первом случае z − 1 = u
y
,
z + 1 = v
y
, где u, v ∈ N; отсюда v
y
− u
y
= 2
. Но, поскольку v > u, y > имеем v
y
− u
y
= (v
− u)(v
y−1
+ . . . + u
y−1
)
(v − u)(2
y−1
+ 1)
Противоречие 2 3. Значит, число x четно. В этом случае одно из чисел 1 и z + 1 делится на 2 и не делится на 4, а второе делится на и не делится на 2
y
. Таким образом, A = 2u
y
, B = 2
y−1
v
y
(u, v — нечетные натуральные числа, где A и B равны, в некотором порядке, числами при этом AB = x
y
). Получили |2u
y
−2
y−1
v
y
| = 2, |u
y
−2
y−2
v
y
| = Отсюда, при некотором выборе знака, u
y
± 1 = Заметим, что u > 1. В самом деле, если u = 1, то A = 2, A = z − 1,
z = 3
, x = 2 — противоречит условию. Кроме того, число y нечетно, в противном случае, если y = 2n, z
2
− (x
n
)
2
= 1
, что невозможно
УЧЕБНЫЙ ГОД, 11
КЛАСС
433
Лемма 1. Пусть a 2, p — нечетное простое число. Тогда число 1 имеет хотя бы один простой делитель, не являющийся делителем числа a − Доказательство. Рассмотрим разложение 1 = (a − 1)(a
p−1
+ a
p−2
+ . . . + a
2
+ a + 1) = (a
− Докажем вначале, что числа a − 1 и b не могут иметьобщего делителя отличного от 1 и от p. Действительно, если a − 1 делится на q, то и a
m
−
− 1 делится на q при любом натуральном m. Значит, b = ql + p, где l некоторое целое число. Поэтому b делится на q лишьпри q = 1 или Таким образом, для завершения доказательства леммы осталось рас- смотретьслучай, когда b = и a − 1 делится на p. Докажем, что этот случай невозможен. Поскольку b > p, достаточно доказать, что b не делится на p
2
. Докажем это. Если a = p
α
k + 1
, где k не делится на p, то (p
α
k + 1)
p
= 1 + p
α+1
k + p
·
p
− 1 2
· p
2α
k
2
+ . . . =
= 1 + p
α+1
k + где d целое. Отсюда a
p
− 1 = p
α+1
(k + pd)
. Поскольку не делится на то очевидно, что b делится на p и не делится на p
2
. Лемма доказана.
Лемма 2. Пусть a 2, p — нечетное простое число и выполнено
хотя бы одно из неравенств a = 2 и p = 3. Тогда a
p
+ имеет простой делитель, не являющийся делителем числа a + Доказательство. Рассмотрим разложение+ 1 = (a + 1)(a
p−1
− a
p−2
+ . . . + a
2
− a + 1) = (a + Докажем вначале, что числа a + 1 и b не могут иметьобщего делителя отличного от 1 и от p. Действительно, если a + 1 делится на r, то и a
k
+ делится на r при любом нечетном k; если же k = 2m, то a
k
− 1 делится на 1, которое, в свою очередь, делится на r. Значит, b = rl + p, где l некоторое целое число. Поэтому b делится на r лишьпри r = 1 или Таким образом, для завершения доказательства леммы осталось рас- смотретьслучай b = p
n
, a + 1 делится на p. Докажем, что этот случай невозможен. Докажем вначале, что, как ив доказательстве леммы 1, b >
> p
. Имеем b a
2
− a + 1 a + 1 p. Из условий леммы следует,
что среди неравенств этой цепочки естьстрогие. С другой стороны, как ив доказательстве леммы 1, можно получить, что число b не делится на что и завершает доказательство леммы.
Из доказанных лемм следует, что правая частьравенства u
y
± 1 =
= имеет не менее q + 1 различных простых делителей. Поскольку
НОД(u, 2v) = 1, u > 1, получаем отсюда неравенство задачи
КЛАСС
433
Лемма 1. Пусть a 2, p — нечетное простое число. Тогда число 1 имеет хотя бы один простой делитель, не являющийся делителем числа a − Доказательство. Рассмотрим разложение 1 = (a − 1)(a
p−1
+ a
p−2
+ . . . + a
2
+ a + 1) = (a
− Докажем вначале, что числа a − 1 и b не могут иметьобщего делителя отличного от 1 и от p. Действительно, если a − 1 делится на q, то и a
m
−
− 1 делится на q при любом натуральном m. Значит, b = ql + p, где l некоторое целое число. Поэтому b делится на q лишьпри q = 1 или Таким образом, для завершения доказательства леммы осталось рас- смотретьслучай, когда b = и a − 1 делится на p. Докажем, что этот случай невозможен. Поскольку b > p, достаточно доказать, что b не делится на p
2
. Докажем это. Если a = p
α
k + 1
, где k не делится на p, то (p
α
k + 1)
p
= 1 + p
α+1
k + p
·
p
− 1 2
· p
2α
k
2
+ . . . =
= 1 + p
α+1
k + где d целое. Отсюда a
p
− 1 = p
α+1
(k + pd)
. Поскольку не делится на то очевидно, что b делится на p и не делится на p
2
. Лемма доказана.
Лемма 2. Пусть a 2, p — нечетное простое число и выполнено
хотя бы одно из неравенств a = 2 и p = 3. Тогда a
p
+ имеет простой делитель, не являющийся делителем числа a + Доказательство. Рассмотрим разложение+ 1 = (a + 1)(a
p−1
− a
p−2
+ . . . + a
2
− a + 1) = (a + Докажем вначале, что числа a + 1 и b не могут иметьобщего делителя отличного от 1 и от p. Действительно, если a + 1 делится на r, то и a
k
+ делится на r при любом нечетном k; если же k = 2m, то a
k
− 1 делится на 1, которое, в свою очередь, делится на r. Значит, b = rl + p, где l некоторое целое число. Поэтому b делится на r лишьпри r = 1 или Таким образом, для завершения доказательства леммы осталось рас- смотретьслучай b = p
n
, a + 1 делится на p. Докажем, что этот случай невозможен. Докажем вначале, что, как ив доказательстве леммы 1, b >
> p
. Имеем b a
2
− a + 1 a + 1 p. Из условий леммы следует,
что среди неравенств этой цепочки естьстрогие. С другой стороны, как ив доказательстве леммы 1, можно получить, что число b не делится на что и завершает доказательство леммы.
Из доказанных лемм следует, что правая частьравенства u
y
± 1 =
= имеет не менее q + 1 различных простых делителей. Поскольку
НОД(u, 2v) = 1, u > 1, получаем отсюда неравенство задачи
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Замечание. Фактически мы доказали следующее, более сильное, чем утверждение задачи,
Предложение. Пустьчисло y разлагается в произведение n отличных от 1 натуральных чисел. Тогда x имеет не менее n + 2 различных простых делителей. Ответ. Не существует.
Возьмем произвольно x
1
= 0 и положим y
1
=
1
x
1
. Тогда f
2
(x
1
+
+ y
1
)
f
2
(x
1
) + 2f (1) + f
2
(y
1
)
f
2
(x
1
) + a
, где a = 2f(1) > Будем далее выбирать x
n
= x
n−1
+ y
n−1
, y
n
=
1
x
n
, n 2. Тогда f
2
(x
n
+
+y
n
)
f
2
(x
n
)+a = f
2
(x
n−1
+y
n−1
)+a
f
2
(x
n−1
)+2a
. . . f
2
(x
1
)+
+ na
. Ясно, что последовательность f(x
1
)
, f(x
2
)
, . . . , f(x
n
)
, . . . неогра- ничена.
734. Ответ. Нельзя.
Предположим, что это возможно. Заметим, что два из рассматриваемых параллелепипедов пересекаются тогда и только тогда, когда их проекции на все три оси координат пересекаются.
Рассмотрим 4 пары параллелепипедов и P
2
, и P
5
, и P
8
, и P
11
. Если взятьпараллелепипеды из разных пар, то они пересекаются,
значит их проекции на любую осьпересекаются. Паре параллелепипедов из одной пары поставим в соответствие оськоординат (одну из осей, если таковых несколько, на которую проекции этих параллелепипедов не пересекаются. Поскольку пара осей — 3, найдутся две пары (скажем, и P
2
, и P
5
), которым сопоставлена одна и та же ось Ox.
Пустьотрезки S
1
, S
2
, S
4
, S
5
— проекции P
1
, P
2
, P
4
, соответственно на ось Ox пусть A
i
— левые концы отрезков S
i
, а B
i
— правые. Известно, что отрезки в парах и S
2
, и не пересекаются, а в любых других парах — пересекаются. Не ограничивая общности, можем считать, что B
1
< A
2
< и A
4
< B
4
< A
5
< B
5
. Так как пересекается сто. Но тогда B
4
< A
2
, и отрезки и не пересекаются.
Противоречие.
Замечание. Ответ в соответствующей задаче для 10 параллелепипедов также отрицательный, а для 9 параллелепипедов — положительный. Пусть X и Y — середины AB и CD соответственно, AB и CD пересекаются в точке P (пустьдля определенности P — точка пересечения лучей AB и DC) (см. рис. Предположим, что O — точка пересечения средних линий четырехугольника. Тогда O — середина отрезка XY , так как середины сторон четырехугольника — вершины параллелограмма. Далее, P O биссектриса и медиана в треугольнике XP Y , поэтому он равнобедрен-
Замечание. Фактически мы доказали следующее, более сильное, чем утверждение задачи,
Предложение. Пустьчисло y разлагается в произведение n отличных от 1 натуральных чисел. Тогда x имеет не менее n + 2 различных простых делителей. Ответ. Не существует.
Возьмем произвольно x
1
= 0 и положим y
1
=
1
x
1
. Тогда f
2
(x
1
+
+ y
1
)
f
2
(x
1
) + 2f (1) + f
2
(y
1
)
f
2
(x
1
) + a
, где a = 2f(1) > Будем далее выбирать x
n
= x
n−1
+ y
n−1
, y
n
=
1
x
n
, n 2. Тогда f
2
(x
n
+
+y
n
)
f
2
(x
n
)+a = f
2
(x
n−1
+y
n−1
)+a
f
2
(x
n−1
)+2a
. . . f
2
(x
1
)+
+ na
. Ясно, что последовательность f(x
1
)
, f(x
2
)
, . . . , f(x
n
)
, . . . неогра- ничена.
734. Ответ. Нельзя.
Предположим, что это возможно. Заметим, что два из рассматриваемых параллелепипедов пересекаются тогда и только тогда, когда их проекции на все три оси координат пересекаются.
Рассмотрим 4 пары параллелепипедов и P
2
, и P
5
, и P
8
, и P
11
. Если взятьпараллелепипеды из разных пар, то они пересекаются,
значит их проекции на любую осьпересекаются. Паре параллелепипедов из одной пары поставим в соответствие оськоординат (одну из осей, если таковых несколько, на которую проекции этих параллелепипедов не пересекаются. Поскольку пара осей — 3, найдутся две пары (скажем, и P
2
, и P
5
), которым сопоставлена одна и та же ось Ox.
Пустьотрезки S
1
, S
2
, S
4
, S
5
— проекции P
1
, P
2
, P
4
, соответственно на ось Ox пусть A
i
— левые концы отрезков S
i
, а B
i
— правые. Известно, что отрезки в парах и S
2
, и не пересекаются, а в любых других парах — пересекаются. Не ограничивая общности, можем считать, что B
1
< A
2
< и A
4
< B
4
< A
5
< B
5
. Так как пересекается сто. Но тогда B
4
< A
2
, и отрезки и не пересекаются.
Противоречие.
Замечание. Ответ в соответствующей задаче для 10 параллелепипедов также отрицательный, а для 9 параллелепипедов — положительный. Пусть X и Y — середины AB и CD соответственно, AB и CD пересекаются в точке P (пустьдля определенности P — точка пересечения лучей AB и DC) (см. рис. Предположим, что O — точка пересечения средних линий четырехугольника. Тогда O — середина отрезка XY , так как середины сторон четырехугольника — вершины параллелограмма. Далее, P O биссектриса и медиана в треугольнике XP Y , поэтому он равнобедрен-
УЧЕБНЫЙ ГОД, 11
КЛАСС
435
D
C
B
A
Y
X
O
P
L
K
Рис. 319
ный и ∠BXO = ∠CY O. Кроме того, ∠XBO + ∠Y CO =
1 2
(
∠ABC +
+
∠BCD) =
1 2
(180
◦
− ∠BP C) = ∠P XY = ∠XBO + ∠XOB, поэтому CO = ∠XOB, и треугольники OXB и CY O подобны. Следовательно O
. Аналогично O
=
XB
Y O
, откуда следует OA · OC =
= OB
· OD.
ПустьтеперьOA · OC = OB · OD. Заметим, что ∠AOB + ∠COD =
= (180
◦
− ∠OAB − ∠OBA) + (180
◦
− ∠OCD − ∠ODC) = 360
◦
−
−
1 2
(
∠DAB + ∠ABC + ∠BCD + ∠CDA) = 180
◦
. Поэтому, если достро- итьтреугольники OAB и OCD до параллелограммов OAKB и то эти параллелограммы будут подобны (поскольку
OA
AK
=
OA
OB
=
DO
OC
).
Тогда треугольники OXB и CY O также подобны, поскольку они соответствуют друг другу при подобии параллелограммов. Отсюда ∠XOB =
=
∠OCY = ∠OCB и ∠COY = ∠XBO = ∠OBC. Следовательно + ∠BOC + ∠COY = ∠OCB + ∠BOC + ∠OBC = 180
◦
, т. е.
точка O лежит на прямой XY . Аналогично, O лежит на прямой, соединяющей середины двух других сторон четырехугольника, что и требовалось. Лемма. Пусть есть n непересекающихся пар знакомых представителей n стран по двое от страны. Тогда можно разбить
их на 2 группы, в каждой из которых по одному представителю от
страны и нет знакомых.
Д ока за тел ьс т во. Выберем любого представителя страны 1, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, й страны
КЛАСС
435
D
C
B
A
Y
X
O
P
L
K
Рис. 319
ный и ∠BXO = ∠CY O. Кроме того, ∠XBO + ∠Y CO =
1 2
(
∠ABC +
+
∠BCD) =
1 2
(180
◦
− ∠BP C) = ∠P XY = ∠XBO + ∠XOB, поэтому CO = ∠XOB, и треугольники OXB и CY O подобны. Следовательно O
. Аналогично O
=
XB
Y O
, откуда следует OA · OC =
= OB
· OD.
ПустьтеперьOA · OC = OB · OD. Заметим, что ∠AOB + ∠COD =
= (180
◦
− ∠OAB − ∠OBA) + (180
◦
− ∠OCD − ∠ODC) = 360
◦
−
−
1 2
(
∠DAB + ∠ABC + ∠BCD + ∠CDA) = 180
◦
. Поэтому, если достро- итьтреугольники OAB и OCD до параллелограммов OAKB и то эти параллелограммы будут подобны (поскольку
OA
AK
=
OA
OB
=
DO
OC
).
Тогда треугольники OXB и CY O также подобны, поскольку они соответствуют друг другу при подобии параллелограммов. Отсюда ∠XOB =
=
∠OCY = ∠OCB и ∠COY = ∠XBO = ∠OBC. Следовательно + ∠BOC + ∠COY = ∠OCB + ∠BOC + ∠OBC = 180
◦
, т. е.
точка O лежит на прямой XY . Аналогично, O лежит на прямой, соединяющей середины двух других сторон четырехугольника, что и требовалось. Лемма. Пусть есть n непересекающихся пар знакомых представителей n стран по двое от страны. Тогда можно разбить
их на 2 группы, в каждой из которых по одному представителю от
страны и нет знакомых.
Д ока за тел ьс т во. Выберем любого представителя страны 1, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, й страны
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ снова в первую, второго представителя й страны — во вторую и т. д.
Этот процесс завершится, когда очередной знакомый уже распределен;
это возможно только если этот знакомый — изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требова- лось.
Если еще осталисьнераспределенные люди, осталосьповторитьпро- цесс, начиная с любого нераспределенного человека. Лемма доказана.
Теперьразобьем четырех представителей страны X на двух представителей страны и двух — страны X
, итак поступим со всеми странами. Разобьем всех сидящих на 50 пар сидящих рядом и объявим людей из одной пары знакомыми. Тогда, в силу леммы, можно разбитьэтих людей на две группы по 50 человек, среди которых нет знакомых и естьпо одному представителю
новых
стран (или по 2 представителя
старых
). Но тогда в каждой группе вместе с любым человеком присутствует не более одного его соседа. Тогда мы можем в каждой группе разбитьлюдей на пары знакомых так, чтобы соседи оказалисьзнакомыми, и снова применить лемму, разбив нашу группу на 2 подгруппы, без знакомых, те. без соседей г класс. Ясно, что ломаная пересекает диагональ. Пусть A — одна из вершин ломаной, лежащая на диагонали. Будем двигаться по ломаной, пока не попадем в первый раз снова в вершину B, лежащую на диагонали. Из симметрии, если двигаться по ломаной изв другую сторону, то B также окажется первой вершиной на диагонали, в которую мы попадем. При этом ломаная уже замкнется, поэтому через остальные 13 центров клеток на диагонали ломаная не проходит.
Раскрасим доску в шахматном порядке так, чтобы диагональбыла черной. Заметим, что на нашей ломаной белые и черные клетки чередуются, поэтому их количества равны. В исходном же квадрате черных клеток на одну больше. Поскольку клетки диагонали черные, и ломаная не проходит через 13 из них, то она не проходит и через 12 белых клеток. Итого,
длина ломаной не более 15 2
− 13 − 12 = 200.
738. Рассмотрим какое-нибудьнатуральное число n > 1000000. Покажем, что условию будет удовлетворятьчетверка чисел −n, n + 1, n(n +
+ 1) + 1
, n(n + 1)(n(n + 1) + 1) + 1. Действительно, применив трижды соотношение + 1
=
1
a(a + 1)
, получаем
Этот процесс завершится, когда очередной знакомый уже распределен;
это возможно только если этот знакомый — изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требова- лось.
Если еще осталисьнераспределенные люди, осталосьповторитьпро- цесс, начиная с любого нераспределенного человека. Лемма доказана.
Теперьразобьем четырех представителей страны X на двух представителей страны и двух — страны X
, итак поступим со всеми странами. Разобьем всех сидящих на 50 пар сидящих рядом и объявим людей из одной пары знакомыми. Тогда, в силу леммы, можно разбитьэтих людей на две группы по 50 человек, среди которых нет знакомых и естьпо одному представителю
новых
стран (или по 2 представителя
старых
). Но тогда в каждой группе вместе с любым человеком присутствует не более одного его соседа. Тогда мы можем в каждой группе разбитьлюдей на пары знакомых так, чтобы соседи оказалисьзнакомыми, и снова применить лемму, разбив нашу группу на 2 подгруппы, без знакомых, те. без соседей г класс. Ясно, что ломаная пересекает диагональ. Пусть A — одна из вершин ломаной, лежащая на диагонали. Будем двигаться по ломаной, пока не попадем в первый раз снова в вершину B, лежащую на диагонали. Из симметрии, если двигаться по ломаной изв другую сторону, то B также окажется первой вершиной на диагонали, в которую мы попадем. При этом ломаная уже замкнется, поэтому через остальные 13 центров клеток на диагонали ломаная не проходит.
Раскрасим доску в шахматном порядке так, чтобы диагональбыла черной. Заметим, что на нашей ломаной белые и черные клетки чередуются, поэтому их количества равны. В исходном же квадрате черных клеток на одну больше. Поскольку клетки диагонали черные, и ломаная не проходит через 13 из них, то она не проходит и через 12 белых клеток. Итого,
длина ломаной не более 15 2
− 13 − 12 = 200.
738. Рассмотрим какое-нибудьнатуральное число n > 1000000. Покажем, что условию будет удовлетворятьчетверка чисел −n, n + 1, n(n +
+ 1) + 1
, n(n + 1)(n(n + 1) + 1) + 1. Действительно, применив трижды соотношение + 1
=
1
a(a + 1)
, получаем
УЧЕБНЫЙ ГОД, КЛАСС 1
−n
+
1
n + 1
+
1
n(n + 1) + 1
+
1
n(n + 1)(n(n + 1) + 1) + 1
=
=
−
1
n(n + 1)
+
1
n(n + 1) + 1
+
1
n(n + 1)(n(n + 1) + 1) + 1
=
=
−
1
n(n + 1)(n(n + 1) + 1)
+
1
n(n + 1)(n(n + 1) + 1) + 1
=
=
−
1
n(n + 1)(n(n + 1) + 1)(n(n + 1)(n(n + 1) + 1) + что и требовалось. Ответ. Заметим, что 2006 = 17 · 118; поэтому найдутся 2 цвета, в которые покрашены в сумме не менее 2 · 118 = 236 точек.
Докажем индукцией по k, что через 2k − 1 точку двух цветов всегда можно провести k −1 непересекающуюся хорду с одноцветными концами.
База очевидна. Пусть k > 2. Тогда среди точек возьмем две одноцветных,
стоящих подряд. Соединим их хордой, выбросим и применим предположение индукции к оставшимся точкам.
Выбрав 235 точек двух цветов и применив данное утверждение, получаем, что 117 хорд Коля сможет провести всегда. Осталосьпривести пример, когда больше хорд провести нельзя.
Пустьна окружности стоит 17k точек. ПустьПетя покрасит каждую точку в цвет, соответствующий остатку отделения на 17 ее номера. Докажем индукцией по k, что через эти точки можно провести не более k − хорды с выполнением условия. База очевидна, докажем переход. Пусть проведено некоторое количество хорд. Рассмотрев две соединенные точки и B на минимальном расстоянии друг от друга, получим такую хорду, что на одной из дуг, на которые она делит окружность, нет концов других проведенных хорд. Теперьсотрем хорду AB и уберем с окружности все точки этой дуги, включая один из концов хорды. Мы получили исходную раскраску 17l точек при l < k. Они соединены не более, чем 1 хордой, поэтому изначально хорд было не больше l − 1 + 1 k − что и требовалось. Пусть M — вторая точка пересечения ω со стороной AC. Докажем, что четырехугольник AT LC — вписанный. Действительно, заметим, что при гомотетии с центром A, переводящей окружность ω вопи- санную окружностьтреугольника ABC, прямая MK переходит впрямую, а следовательно, они параллельны (см. рис. 320). Тогда получаем,
что ∠AMK = ∠ACB = ∠ACT , но из вписанности четырехугольника имеем ∠AMK = ∠ALK = ∠ALT . Отсюда ∠ACT = ∠ALT , те вписанный. Следовательно, ∠CT A = ∠CLA, но по свойству
−n
+
1
n + 1
+
1
n(n + 1) + 1
+
1
n(n + 1)(n(n + 1) + 1) + 1
=
=
−
1
n(n + 1)
+
1
n(n + 1) + 1
+
1
n(n + 1)(n(n + 1) + 1) + 1
=
=
−
1
n(n + 1)(n(n + 1) + 1)
+
1
n(n + 1)(n(n + 1) + 1) + 1
=
=
−
1
n(n + 1)(n(n + 1) + 1)(n(n + 1)(n(n + 1) + 1) + что и требовалось. Ответ. Заметим, что 2006 = 17 · 118; поэтому найдутся 2 цвета, в которые покрашены в сумме не менее 2 · 118 = 236 точек.
Докажем индукцией по k, что через 2k − 1 точку двух цветов всегда можно провести k −1 непересекающуюся хорду с одноцветными концами.
База очевидна. Пусть k > 2. Тогда среди точек возьмем две одноцветных,
стоящих подряд. Соединим их хордой, выбросим и применим предположение индукции к оставшимся точкам.
Выбрав 235 точек двух цветов и применив данное утверждение, получаем, что 117 хорд Коля сможет провести всегда. Осталосьпривести пример, когда больше хорд провести нельзя.
Пустьна окружности стоит 17k точек. ПустьПетя покрасит каждую точку в цвет, соответствующий остатку отделения на 17 ее номера. Докажем индукцией по k, что через эти точки можно провести не более k − хорды с выполнением условия. База очевидна, докажем переход. Пусть проведено некоторое количество хорд. Рассмотрев две соединенные точки и B на минимальном расстоянии друг от друга, получим такую хорду, что на одной из дуг, на которые она делит окружность, нет концов других проведенных хорд. Теперьсотрем хорду AB и уберем с окружности все точки этой дуги, включая один из концов хорды. Мы получили исходную раскраску 17l точек при l < k. Они соединены не более, чем 1 хордой, поэтому изначально хорд было не больше l − 1 + 1 k − что и требовалось. Пусть M — вторая точка пересечения ω со стороной AC. Докажем, что четырехугольник AT LC — вписанный. Действительно, заметим, что при гомотетии с центром A, переводящей окружность ω вопи- санную окружностьтреугольника ABC, прямая MK переходит впрямую, а следовательно, они параллельны (см. рис. 320). Тогда получаем,
что ∠AMK = ∠ACB = ∠ACT , но из вписанности четырехугольника имеем ∠AMK = ∠ALK = ∠ALT . Отсюда ∠ACT = ∠ALT , те вписанный. Следовательно, ∠CT A = ∠CLA, но по свойству
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
касательной ∠CLA = ∠LKA, те, и значит, ∠BT A =
=
∠BKT . Тогда треугольники BT A и BKT подобны по двум углам, откуда другой стороны, произведение BK · BA равно квадрату касательной к ω из точки Рис. Рис. 321
касательной ∠CLA = ∠LKA, те, и значит, ∠BT A =
=
∠BKT . Тогда треугольники BT A и BKT подобны по двум углам, откуда другой стороны, произведение BK · BA равно квадрату касательной к ω из точки Рис. Рис. 321
1 ... 56 57 58 59 60 61 62 63 64
741. Заметим, что b
k
=
a
k
c
k
, где c
k
— наименьший простой делитель Так как b
9
> b
10
, то b
9
> и b
9
c
9
. Отсюда a
10
> a
9
c
2 9
. Но из неравенств a
i
< a
i+1
, b
i
> следует, что c
i
< c
i+1
, те. Значит, c
9
23, так как 23 — девятое по счету простое число.
Поэтому a
10
> c
2 9
529 > 500.
742. Сначала заметим, что поскольку ∠ARP < ∠ARP + ∠QRC =
=
∠ABC, то точка X лежит на луче RP иначе ∠ARP = π − ∠ARX >
>
∠RAX = ∠ABC) (см. рис. 321). Тогда ∠ACB = ∠XAB и ∠AP X =
=
∠RP B = ∠RQC, и треугольники AP X и CQR равны по стороне и двум углам. Следовательно, P X = QR. Аналогично, P R = QY , откуда и следует утверждение задачи. Ответ. Выигрывает игрок, делающий второй ход.
Приведем выигрышную стратегию для второго. Первыми несколькими ходами он склеивает каждую клетку, примыкающую к границе квадрата со всеми ее соседями. На это потребуется не более 8 · 99 ходов, т. е.
после этого будет склеено всего 16 · 99 пар сторон и, как следствие, не более 2 · 16 · 99 <
10 000 2
доминошек окажутся склеенными с чем-нибудь еще. Следовательно, после этого еще останутся отдельные доминошки, и фигура не будет связной. Далее второй будет действоватьпроизвольным образом, следя только затем, чтобы не проиграть прямо нынешним ходом.
Пустьв некоторый момент ему не удастся сделатьэтого. Тогда все доминошки распадаются на две связных фигуры, причем все несклеен- ные отрезки — это граница между этими фигурами, так как любой другой
УЧЕБНЫЙ ГОД, 10
КЛАСС
439
отрезок можно склеить. При этом одна из этих фигур содержит все граничные клетки квадрата.
В границе внутренней фигуры четное число отрезков (если мы обойдем эту ломаную, то отрезков, по которым мы шли вверх и вниз, будет поровну тоже с отрезками вправо и влево. Подсчитаем изначальное число разрезанных сторон отрезков. Оно равно суммарному периметру всех до- миношек, уменьшенному на периметр квадрата и деленному на 2 (так как каждый из остальных отрезков считался по два раза, те четному числу. Значит, к данному моменту склеено также четное число сторон, и ходитьдолжен первый. Противоречие. Обозначим через и корни уравнения f(x) = 0, а через и корни уравнения f(f(x)) = 0, сумма которых равна −1. Множество корней последнего уравнения совпадает с объединением множеств корней уравнений f(x) = и f(x) = c
2
. Если и являются корнями одного из последних двух уравнений, то их сумма, равная −1, будет по теореме
Виета равна и −a, откуда a = 1. Можно считать, что c
1
c
2
. Но поскольку по теореме Виета c
1
+ c
2
=
−1, то c
2
−
1 2
. Из условия следует,
что дискриминант уравнения f(x) = неотрицателен, поэтому 1 − 4b +
+ 4c
2
0, откуда b −
1 В противном случае, не умаляя общности, можно записать, что x
2 1
+
+ ax
1
+ b = и x
2 2
+ ax
2
+ b = c
2
. Складывая последние два равенства,
получим: x
2 1
+ x
2 2
+ a(x
1
+ x
2
) + 2b = c
1
+ c
2
. Поскольку c
1
+ c
2
=
−a по теореме Виета, а x
1
+ x
2
=
−1 по условию, то последнее равенство после сокращения перепишется так x
2 1
+ x
2 2
+ 2b = 0
. Но тогда b = −
1 2
(x
2 1
+
+ x
2 2
)
−
1 4
(x
1
+ x
2
)
2
=
−
1 4
10 класс. См. решение задачи 737.
746. В решении латинскими буквами везде обозначены натуральные числа.
По условию, (x − 1)
3
+ x
3
+ (x + 1)
3
= y
3
, или 3x(x
2
+ 2) = y
3
. Тогда
y
делится на 3, y = 3z и x(x
2
+ 2) = 9z
3
. Очевидно, НОД(x, x
2
+ 2)
Докажем, что случай НОД(x, x
2
+2) = невозможен. Действительно,
в этом случае либо x = и x
2
+ 2 = v
3
, либо x = u
3
, x
2
+ 2 = при некоторых натуральных u, v. В первом случае получаем 81u
6
+ 2 = что невозможно, так как куб целого числа при делении надает остаток или ±1. Аналогично, второе равенство влечет, что u
6
+ 2 = 9v
3
, что невозможно по тем же причинам
КЛАСС
439
отрезок можно склеить. При этом одна из этих фигур содержит все граничные клетки квадрата.
В границе внутренней фигуры четное число отрезков (если мы обойдем эту ломаную, то отрезков, по которым мы шли вверх и вниз, будет поровну тоже с отрезками вправо и влево. Подсчитаем изначальное число разрезанных сторон отрезков. Оно равно суммарному периметру всех до- миношек, уменьшенному на периметр квадрата и деленному на 2 (так как каждый из остальных отрезков считался по два раза, те четному числу. Значит, к данному моменту склеено также четное число сторон, и ходитьдолжен первый. Противоречие. Обозначим через и корни уравнения f(x) = 0, а через и корни уравнения f(f(x)) = 0, сумма которых равна −1. Множество корней последнего уравнения совпадает с объединением множеств корней уравнений f(x) = и f(x) = c
2
. Если и являются корнями одного из последних двух уравнений, то их сумма, равная −1, будет по теореме
Виета равна и −a, откуда a = 1. Можно считать, что c
1
c
2
. Но поскольку по теореме Виета c
1
+ c
2
=
−1, то c
2
−
1 2
. Из условия следует,
что дискриминант уравнения f(x) = неотрицателен, поэтому 1 − 4b +
+ 4c
2
0, откуда b −
1 В противном случае, не умаляя общности, можно записать, что x
2 1
+
+ ax
1
+ b = и x
2 2
+ ax
2
+ b = c
2
. Складывая последние два равенства,
получим: x
2 1
+ x
2 2
+ a(x
1
+ x
2
) + 2b = c
1
+ c
2
. Поскольку c
1
+ c
2
=
−a по теореме Виета, а x
1
+ x
2
=
−1 по условию, то последнее равенство после сокращения перепишется так x
2 1
+ x
2 2
+ 2b = 0
. Но тогда b = −
1 2
(x
2 1
+
+ x
2 2
)
−
1 4
(x
1
+ x
2
)
2
=
−
1 4
10 класс. См. решение задачи 737.
746. В решении латинскими буквами везде обозначены натуральные числа.
По условию, (x − 1)
3
+ x
3
+ (x + 1)
3
= y
3
, или 3x(x
2
+ 2) = y
3
. Тогда
y
делится на 3, y = 3z и x(x
2
+ 2) = 9z
3
. Очевидно, НОД(x, x
2
+ 2)
Докажем, что случай НОД(x, x
2
+2) = невозможен. Действительно,
в этом случае либо x = и x
2
+ 2 = v
3
, либо x = u
3
, x
2
+ 2 = при некоторых натуральных u, v. В первом случае получаем 81u
6
+ 2 = что невозможно, так как куб целого числа при делении надает остаток или ±1. Аналогично, второе равенство влечет, что u
6
+ 2 = 9v
3
, что невозможно по тем же причинам
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Итак, НОД(x, x
2
+ 2) = 2
, x(x
2
+ 2) = 9z
3
. Тогда x и, следовательно) четно, поэтому x(x
2
+ делится на 8. Поскольку x
2
+ не делится на, получаем, что x делится на 4, что и требовалось. Ответ. См. решение задачи 739.
748. Обозначим через D и E точки касания ω со сторонами AB и, DE BC из симметрии относительно биссектрисы угла BAC (см.
рис. 322). Пустьпри гомотетии с центром A и коэффициентом
AK
AM
окружность ω переходит в окружность ω
. Окружность проходит через точку K, а следовательно, и через L из симметрии относительно биссектрисы угла BAC), а также касается лучей AB ив некоторых точках
D
и Из гомотетии следует, что MD KD
. Далее, по теореме о произведении отрезков касательных BD
2
= BK
· BL = BD
2
, откуда BD = По построению BK = BP , поэтому DKD
P
— параллелограмм, и значит. Отсюда вытекает, что точки M, D, P лежат на одной прямой. Аналогично, M, E и Q лежат на одной прямой. Треугольники и MP Q гомотетичны с центром M, следовательно, их описанные окружности также гомотетичны, те. касаются в точке Рис. Рис. 323
749. См. решение задачи 741.
750. Если AB = BC, то утверждение задачи очевидно. Пустьдля определенности см. рис. 323). Обозначим через I
1
, центры вписанных окружностей треугольников AKB и CLB соответственно, через, Q — вторые точки пересечения прямых BI
1
, с описанной окруж-
Итак, НОД(x, x
2
+ 2) = 2
, x(x
2
+ 2) = 9z
3
. Тогда x и, следовательно) четно, поэтому x(x
2
+ делится на 8. Поскольку x
2
+ не делится на, получаем, что x делится на 4, что и требовалось. Ответ. См. решение задачи 739.
748. Обозначим через D и E точки касания ω со сторонами AB и, DE BC из симметрии относительно биссектрисы угла BAC (см.
рис. 322). Пустьпри гомотетии с центром A и коэффициентом
AK
AM
окружность ω переходит в окружность ω
. Окружность проходит через точку K, а следовательно, и через L из симметрии относительно биссектрисы угла BAC), а также касается лучей AB ив некоторых точках
D
и Из гомотетии следует, что MD KD
. Далее, по теореме о произведении отрезков касательных BD
2
= BK
· BL = BD
2
, откуда BD = По построению BK = BP , поэтому DKD
P
— параллелограмм, и значит. Отсюда вытекает, что точки M, D, P лежат на одной прямой. Аналогично, M, E и Q лежат на одной прямой. Треугольники и MP Q гомотетичны с центром M, следовательно, их описанные окружности также гомотетичны, те. касаются в точке Рис. Рис. 323
749. См. решение задачи 741.
750. Если AB = BC, то утверждение задачи очевидно. Пустьдля определенности см. рис. 323). Обозначим через I
1
, центры вписанных окружностей треугольников AKB и CLB соответственно, через, Q — вторые точки пересечения прямых BI
1
, с описанной окруж-
УЧЕБНЫЙ ГОД, 11
КЛАСС
441
ностью треугольника ABC, а через R — середину дуги ABC этой окружности. Тогда P A = QC как хорды, стягивающие половины равных дуг.
Так как ∠P AI
1
=
∠P AK + ∠KAI
1
=
∠P BK + ∠BAI
1
=
∠ABI
1
+
+
∠BAI
1
=
∠AI
1
P
, то треугольник равнобедренный, и P A = P Аналогично QC = QI
2
; следовательно, P I
1
= QI
2
. Далее, P R = как хорды, стягивающие равные дуги, а ∠I
2
QR =
∠I
1
P как углы, опирающиеся на одну дугу. Тогда треугольники и равны по двум сторонами углу между ними, откуда и следует утверждение задачи. См. решение задачи 744.
752. Раскрасим клетки квадрата в черный и белый цвет в шахматном порядке. Каждая доминошка покрывает ровно одну черную клетку. Разобьем квадрат 3 000 × 3 000 на квадраты 6 × 6, ив каждом квадрате перекрасим черные клетки в 3 цвета как показано на рис. 324 или на рис. Окрасим доминошки в первый, второй и третий цвета так, чтобы доми- ношка накрывала клетку своего цвета 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
2 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
2 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
2 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 Рис. Рис. В квадрате 6 × 6 поровну клеток каждого цвета, значит ив квадрате 000
× 3 000 тоже. Следовательно, доминошек каждого цвета поровну.
Пустьдве клетки одного цвета покрыты соседними доминошками. Легко видеть, что для наших раскрасок это возможно только если эти две клетки имеют общую вершину. Для данной клетки на рис. 1 имеется не более двух клеток того же цвета, имеющих с ней общую вершину, а на рис. 2
— не более одной такой клетки. Отсюда следует, что если использовать раскраску рис. 1, то для любой доминошки имеется не более двух соседних доминошек того же цвета, а если использовать раскраску рис. 2, то даже не более одной соседней доминошки того же цвета класс. При x 1 имеем 1
√
x
x <
π
2
. Отсюда sin
√
x
sin Далее, поскольку 0 < sin x < 1, имеем sin x <
√
sin x
. Пусть 0 < x < 1.
КЛАСС
441
ностью треугольника ABC, а через R — середину дуги ABC этой окружности. Тогда P A = QC как хорды, стягивающие половины равных дуг.
Так как ∠P AI
1
=
∠P AK + ∠KAI
1
=
∠P BK + ∠BAI
1
=
∠ABI
1
+
+
∠BAI
1
=
∠AI
1
P
, то треугольник равнобедренный, и P A = P Аналогично QC = QI
2
; следовательно, P I
1
= QI
2
. Далее, P R = как хорды, стягивающие равные дуги, а ∠I
2
QR =
∠I
1
P как углы, опирающиеся на одну дугу. Тогда треугольники и равны по двум сторонами углу между ними, откуда и следует утверждение задачи. См. решение задачи 744.
752. Раскрасим клетки квадрата в черный и белый цвет в шахматном порядке. Каждая доминошка покрывает ровно одну черную клетку. Разобьем квадрат 3 000 × 3 000 на квадраты 6 × 6, ив каждом квадрате перекрасим черные клетки в 3 цвета как показано на рис. 324 или на рис. Окрасим доминошки в первый, второй и третий цвета так, чтобы доми- ношка накрывала клетку своего цвета 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
2 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
2 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
2 3
1 2
3 1
3 1
2 3
1 2
1 2
3 1
2 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 3
1 1
1 1
1 1
2 2
2 2
2 2
3 3
3 3
3 Рис. Рис. В квадрате 6 × 6 поровну клеток каждого цвета, значит ив квадрате 000
× 3 000 тоже. Следовательно, доминошек каждого цвета поровну.
Пустьдве клетки одного цвета покрыты соседними доминошками. Легко видеть, что для наших раскрасок это возможно только если эти две клетки имеют общую вершину. Для данной клетки на рис. 1 имеется не более двух клеток того же цвета, имеющих с ней общую вершину, а на рис. 2
— не более одной такой клетки. Отсюда следует, что если использовать раскраску рис. 1, то для любой доминошки имеется не более двух соседних доминошек того же цвета, а если использовать раскраску рис. 2, то даже не более одной соседней доминошки того же цвета класс. При x 1 имеем 1
√
x
x <
π
2
. Отсюда sin
√
x
sin Далее, поскольку 0 < sin x < 1, имеем sin x <
√
sin x
. Пусть 0 < x < 1.
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Перепишем неравенство sin
2
t < при 0 < t < 1. Так как sin
2 0 =
= sin(0 2
)
, то достаточно доказать (sin
2
t)
< (sin(t
2
))
, или 2 sin t cos t <
< 2t cos(t
2
)
. Поскольку t > t
2
> 0
, то cos t < cos(t
2
)
. Перемножив это неравенство и sin t < t, получим sin t cos t < t cos(t
2
)
754. Заметим, что чисто периодическая дробьс периодом T после до- множения на 10
T
−1 становится целым числом. Домножим наши две дроби и b на число 10
T
− 1 = 99 . . . 9
T
. Получатся два новых рациональных числа A = (10
T
− 1)a и B = (10
T
− 1)b. Числа A + B = (10
T
− 1)(a + и AB = (10
T
− целые, так как a + b и ab — дроби с периодом T становящиеся целыми при домножении на 10
T
− 1 и тем более на (10
T
−
− 1)
2
. Но два рациональных числа, сумма и произведение которых целые,
являются корнями приведенного квадратного цравнения с целыми коэффициентами, те. сами являются целыми числами. Значит, a и b могут бытьзаписаны в виде обыкновенных дробей со знаменателем 10
T
− 1, откуда и следует утверждение задачи. Ответ. Выигрывает первый.
Первое решение. Разобьем все отмеченные точки на пары так, что любой отрезок с концами в точках одной пары — горизонтальный отрезок длины 1. Опишем выигрышную стратегию первого игрока. Пустьпер- вым ходом он соединит точки из какой-нибудьпары. Далее, если второй соединяет отрезком две точки какой-нибудьпары, то первый соединяет отрезком две точки другой пары (назовем эти два проведенных отрезка двойкой первого типа. Если же второй соединяет отрезком две точки из разных пар, то первый соединяет отрезком две оставшиеся точки из этих пар (назовем такие два отрезка двойкой второго типа. Заметим, что количество точек делится на 4, поэтому последний ход сделает второй. Первый будет делатьответные ходы до тех пор, пока не останется одна пара — эти две оставшиеся точки соединит отрезком второй игрок. Теперьзаметим,
что в двойке первого типа можно выбратьнаправления так, чтобы сумма двух векторов равняласьнулевому вектору, а двойке второго типа можно выбратьнаправления так, чтобы сумма двух векторов равняласьгоризон- тальному вектору длины 2 (любого из двух направлений. Теперь первому нужно так выбратьнаправления в двойках второго типа, чтобы суммарная длина всех векторов в этих двойках равняласьлибо нулевому вектору, либо горизонтальному вектору длины 2. После этого останется только два отрезка длины 1 (первый ход первого игрока и последний ход второго),
на которых первому игроку нужно выбратьнаправления так, чтобы сумма всех векторов равняласьнулевому вектору
Перепишем неравенство sin
2
t < при 0 < t < 1. Так как sin
2 0 =
= sin(0 2
)
, то достаточно доказать (sin
2
t)
< (sin(t
2
))
, или 2 sin t cos t <
< 2t cos(t
2
)
. Поскольку t > t
2
> 0
, то cos t < cos(t
2
)
. Перемножив это неравенство и sin t < t, получим sin t cos t < t cos(t
2
)
754. Заметим, что чисто периодическая дробьс периодом T после до- множения на 10
T
−1 становится целым числом. Домножим наши две дроби и b на число 10
T
− 1 = 99 . . . 9
T
. Получатся два новых рациональных числа A = (10
T
− 1)a и B = (10
T
− 1)b. Числа A + B = (10
T
− 1)(a + и AB = (10
T
− целые, так как a + b и ab — дроби с периодом T становящиеся целыми при домножении на 10
T
− 1 и тем более на (10
T
−
− 1)
2
. Но два рациональных числа, сумма и произведение которых целые,
являются корнями приведенного квадратного цравнения с целыми коэффициентами, те. сами являются целыми числами. Значит, a и b могут бытьзаписаны в виде обыкновенных дробей со знаменателем 10
T
− 1, откуда и следует утверждение задачи. Ответ. Выигрывает первый.
Первое решение. Разобьем все отмеченные точки на пары так, что любой отрезок с концами в точках одной пары — горизонтальный отрезок длины 1. Опишем выигрышную стратегию первого игрока. Пустьпер- вым ходом он соединит точки из какой-нибудьпары. Далее, если второй соединяет отрезком две точки какой-нибудьпары, то первый соединяет отрезком две точки другой пары (назовем эти два проведенных отрезка двойкой первого типа. Если же второй соединяет отрезком две точки из разных пар, то первый соединяет отрезком две оставшиеся точки из этих пар (назовем такие два отрезка двойкой второго типа. Заметим, что количество точек делится на 4, поэтому последний ход сделает второй. Первый будет делатьответные ходы до тех пор, пока не останется одна пара — эти две оставшиеся точки соединит отрезком второй игрок. Теперьзаметим,
что в двойке первого типа можно выбратьнаправления так, чтобы сумма двух векторов равняласьнулевому вектору, а двойке второго типа можно выбратьнаправления так, чтобы сумма двух векторов равняласьгоризон- тальному вектору длины 2 (любого из двух направлений. Теперь первому нужно так выбратьнаправления в двойках второго типа, чтобы суммарная длина всех векторов в этих двойках равняласьлибо нулевому вектору, либо горизонтальному вектору длины 2. После этого останется только два отрезка длины 1 (первый ход первого игрока и последний ход второго),
на которых первому игроку нужно выбратьнаправления так, чтобы сумма всех векторов равняласьнулевому вектору
УЧЕБНЫЙ ГОД, 11
КЛАСС
443
Второе решение. Будем считать, что большая сторона прямоугольника параллельна оси Ox, а меньшая, при этом левый нижний угол прямоугольника совпадает с началом координат.
Лемма 1. Пустьигроки провели все отрезки. Тогда, независимо от расстановки стрелок, проекция вектора суммы на каждую из осей будет иметьчетную длину.
Д ока за тел ьс т во. Рассмотрим проекцию вектора суммы на ось. Для каждой точки в зависимости от направления вектора ее координата по оси Ox берется либо со знаком плюс, либо со знаком минус.
Сумма координат (с соответствующими знаками) по оси Ox всех точек прямоугольника и даст проекцию вектора суммы на ось Ox. Однако пятьдесят из этих точек имеют координату 0, пятьдесят имеют координату 1,
. . . , пятьдесят имеют координату 69. То естьсреди этих чисел четное количество нечетных. Это и означает, что соответствующая сумма будет четной. Аналогично проекция вектора суммы на ось Oy будет иметьчетную длину. Лемма доказана.
Лемма 2. Пустьимеется набор отрезков с концами в целочисленных точках прямоугольника 49 × 69. Тогда можно так выбратьнаправления на этих отрезках, что проекция вектора суммы на ось Ox будет меньше а на ось Oy — меньше Доказательство. Разобьем отрезки набора на четыре группы параллельных оси Ox группа A), параллельных оси Oy группа B), тех, у которых правый конец выше левого (группа C), и тех, у которых правый конец ниже левого (группа D). Заметим, что если взятьдва отрезка из одной группы, тона них так можно выбратьнаправления, что по модулю координаты вектора их суммы будут не больше 69 по оси Ox и не более по оси Oy назовем такой вектор коротким. Также заметим, что если у набора векторов все направления поменятьна противоположные, то вектор суммы изменит лишьзнак.
Будем теперьпроводитьследующую процедуру. На каждом шаге будем выбиратьпару отрезков из одной группы и заменятьих соответствующим отрезком, который соответствует короткому вектору (новый отрезок может попастьв другую группу. Если в процессе получится отрезок нулевой длины, выкинем его. Заметим тогда, что если в полученном наборе мы можем расставитьнаправления требуемым образом, то ив старом это было возможно.
Через некоторое число шагов мы придем к такой ситуации, что в каждой группе будет не более одного отрезка. Выбрав направления на отрезках из групп C и D, мы получим вектор, проекция которого на ось будет меньше 140, а на ось Oy — меньше 100. Пусть обе его координаты
КЛАСС
443
Второе решение. Будем считать, что большая сторона прямоугольника параллельна оси Ox, а меньшая, при этом левый нижний угол прямоугольника совпадает с началом координат.
Лемма 1. Пустьигроки провели все отрезки. Тогда, независимо от расстановки стрелок, проекция вектора суммы на каждую из осей будет иметьчетную длину.
Д ока за тел ьс т во. Рассмотрим проекцию вектора суммы на ось. Для каждой точки в зависимости от направления вектора ее координата по оси Ox берется либо со знаком плюс, либо со знаком минус.
Сумма координат (с соответствующими знаками) по оси Ox всех точек прямоугольника и даст проекцию вектора суммы на ось Ox. Однако пятьдесят из этих точек имеют координату 0, пятьдесят имеют координату 1,
. . . , пятьдесят имеют координату 69. То естьсреди этих чисел четное количество нечетных. Это и означает, что соответствующая сумма будет четной. Аналогично проекция вектора суммы на ось Oy будет иметьчетную длину. Лемма доказана.
Лемма 2. Пустьимеется набор отрезков с концами в целочисленных точках прямоугольника 49 × 69. Тогда можно так выбратьнаправления на этих отрезках, что проекция вектора суммы на ось Ox будет меньше а на ось Oy — меньше Доказательство. Разобьем отрезки набора на четыре группы параллельных оси Ox группа A), параллельных оси Oy группа B), тех, у которых правый конец выше левого (группа C), и тех, у которых правый конец ниже левого (группа D). Заметим, что если взятьдва отрезка из одной группы, тона них так можно выбратьнаправления, что по модулю координаты вектора их суммы будут не больше 69 по оси Ox и не более по оси Oy назовем такой вектор коротким. Также заметим, что если у набора векторов все направления поменятьна противоположные, то вектор суммы изменит лишьзнак.
Будем теперьпроводитьследующую процедуру. На каждом шаге будем выбиратьпару отрезков из одной группы и заменятьих соответствующим отрезком, который соответствует короткому вектору (новый отрезок может попастьв другую группу. Если в процессе получится отрезок нулевой длины, выкинем его. Заметим тогда, что если в полученном наборе мы можем расставитьнаправления требуемым образом, то ив старом это было возможно.
Через некоторое число шагов мы придем к такой ситуации, что в каждой группе будет не более одного отрезка. Выбрав направления на отрезках из групп C и D, мы получим вектор, проекция которого на ось будет меньше 140, а на ось Oy — меньше 100. Пусть обе его координаты
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
неотрицательны. Если теперь на отрезках из групп A и B выбратьотрица- тельные направления, то у итогового вектора суммы проекция на ось будет меньше 140, а на ось Oy — меньше Лемма доказана.
Перейдем к решению задачи. Опишем стратегию первого игрока. Ему необходимо будет провести 140 горизонтальных отрезков длины 1 и вертикальных отрезков длины 1 (назовем их красными. Тогда, после того как будут проведены все отрезки, на всех не красных отрезках по лемме он так может выбратьнаправления, что проекция вектора суммы на ось
Ox
будет меньше 140, а на Oy — меньше 100. Теперь ему останется вы- братьнаправления на красных отрезках так, чтобы проекция вектора суммы на каждую из осей будет равна нулю. Поскольку по лемме 1 проекция вектора суммы на каждую из осей будет иметьчетную длину, он сможет это сделатьи выиграет.
Рис. Покажем, как первому игроку провести требуемое количество красных отрезков. Выделим 25·35 =
= квадратиков, каждый из которых содержит четыре отрезка длины 1 (см. рис. 326). Каждым своим ходом первый будет отмечатьвертикальный или горизонтальный отрезок водном из квадратиков. Для этого ему потребуется 240 ходов, каждым из которых первый тратит один квадратик. Заметим, что второй каждым своим ходом
портит
не более двух квадратиков. Таким образом, после каждого хода первого и второго используется не более трех квадратиков. Поскольку 240 · 3 = 720 < 875, первый сможет провести красных отрезков нужных направлений, что и требовалось. Пустьбиссектрисы AI, BI, CI пересекают описанную окруж- ностьв точках A
0
, и соответственно. Точки и являются соответственно серединами дуги. Проведем через A прямую,
параллельную B
0
C
0
, пересекающую биссектрисы в точках и I
C
(см.
рис. 327). Имеем ∠AIB
0
=
∠ABI + ∠BAI = ∠ABB
0
+
∠BAA
0
=
=
∠B
0
BC +
∠CAA
0
=
∠B
0
AI
, поэтому треугольник равнобедренный. Аналогично, C
0
A = CI
, поэтому треугольники и равны. Далее, отрезок является серединным перпендикуляром ка высота в треугольнике II
B
I
C
. Отсюда следует, что средняя линия треугольника I
B
II
C
. Получаем следующие равенства для радиусов описанных окружностей R(I
B
II
C
) = 2R(B
0
IC
0
) =
= 2R(B
0
AC
0
) = 2R(ABC)
Теперьдостаточно доказать, что точки M и N лежат на описанной окружности треугольника I
B
II
C
. Заметим, что ∠AI
B
I =
∠C
0
B
0
I =
неотрицательны. Если теперь на отрезках из групп A и B выбратьотрица- тельные направления, то у итогового вектора суммы проекция на ось будет меньше 140, а на ось Oy — меньше Лемма доказана.
Перейдем к решению задачи. Опишем стратегию первого игрока. Ему необходимо будет провести 140 горизонтальных отрезков длины 1 и вертикальных отрезков длины 1 (назовем их красными. Тогда, после того как будут проведены все отрезки, на всех не красных отрезках по лемме он так может выбратьнаправления, что проекция вектора суммы на ось
Ox
будет меньше 140, а на Oy — меньше 100. Теперь ему останется вы- братьнаправления на красных отрезках так, чтобы проекция вектора суммы на каждую из осей будет равна нулю. Поскольку по лемме 1 проекция вектора суммы на каждую из осей будет иметьчетную длину, он сможет это сделатьи выиграет.
Рис. Покажем, как первому игроку провести требуемое количество красных отрезков. Выделим 25·35 =
= квадратиков, каждый из которых содержит четыре отрезка длины 1 (см. рис. 326). Каждым своим ходом первый будет отмечатьвертикальный или горизонтальный отрезок водном из квадратиков. Для этого ему потребуется 240 ходов, каждым из которых первый тратит один квадратик. Заметим, что второй каждым своим ходом
портит
не более двух квадратиков. Таким образом, после каждого хода первого и второго используется не более трех квадратиков. Поскольку 240 · 3 = 720 < 875, первый сможет провести красных отрезков нужных направлений, что и требовалось. Пустьбиссектрисы AI, BI, CI пересекают описанную окруж- ностьв точках A
0
, и соответственно. Точки и являются соответственно серединами дуги. Проведем через A прямую,
параллельную B
0
C
0
, пересекающую биссектрисы в точках и I
C
(см.
рис. 327). Имеем ∠AIB
0
=
∠ABI + ∠BAI = ∠ABB
0
+
∠BAA
0
=
=
∠B
0
BC +
∠CAA
0
=
∠B
0
AI
, поэтому треугольник равнобедренный. Аналогично, C
0
A = CI
, поэтому треугольники и равны. Далее, отрезок является серединным перпендикуляром ка высота в треугольнике II
B
I
C
. Отсюда следует, что средняя линия треугольника I
B
II
C
. Получаем следующие равенства для радиусов описанных окружностей R(I
B
II
C
) = 2R(B
0
IC
0
) =
= 2R(B
0
AC
0
) = 2R(ABC)
Теперьдостаточно доказать, что точки M и N лежат на описанной окружности треугольника I
B
II
C
. Заметим, что ∠AI
B
I =
∠C
0
B
0
I =
УЧЕБНЫЙ ГОД, КЛАСС =
∠C
0
CA =
∠ICA, значит точки A, I, C, лежат на одной окружности, отсюда B
1
A
· B
1
C = B
1
I
· B
1
I
B
. С другой стороны B
1
C = B
1
M
· B
1
N
, так как точки A, M, C, N лежат на одной окружности. Следовательно, B
1
M
· B
1
N = B
1
I
· B
1
I
B
, и точка лежит на описанной окружности треугольника IMN. Аналогично, на ней лежит точка I
C
, что и требовалось.
A
B
C
I
M
N
B
1
C
1
A
0
B
0
C
0
I
C
I
B
A
B
C
D
E
F
S
I
A
B
C
S
O
Рис. Рис. 328
∠C
0
CA =
∠ICA, значит точки A, I, C, лежат на одной окружности, отсюда B
1
A
· B
1
C = B
1
I
· B
1
I
B
. С другой стороны B
1
C = B
1
M
· B
1
N
, так как точки A, M, C, N лежат на одной окружности. Следовательно, B
1
M
· B
1
N = B
1
I
· B
1
I
B
, и точка лежит на описанной окружности треугольника IMN. Аналогично, на ней лежит точка I
C
, что и требовалось.
A
B
C
I
M
N
B
1
C
1
A
0
B
0
C
0
I
C
I
B
A
B
C
D
E
F
S
I
A
B
C
S
O
Рис. Рис. 328
757. Очевидно, начиная со второго члена, наши последовательности возрастают x
n+2
> x
2
n+1
> x
n+1
, y
n+2
> y
n+1
. Так как x
3
> 1 + 1 2
= 2
,
y
3
> 1 2
+ 1 = 2
, все члены каждой из последовательностей, начиная с третьего, больше 2. Аналогично при n > 3 получим x
n
> 3
, y
n
> Заметим теперь, что x
n+2
> x
2
n+1
> при n > 1. С другой стороны y
2
n
+ y
n+1
= y
2
n
+ y
n
+ y
2
n−1
< 3y
2
n
< при n > Итак, при n > 3 имеем x
n+2
lg y
n+2
>
4 lg x
n
3 lg y
n
, а lg x
2k
lg y
2k
>
4 3
k−1
·
lg x
2
lg При достаточно большом k правая частьпоследнего неравенства больше, а значит, x
2k
> y
2k
, что и требовалось доказать. Из теоремы о трех перпендикулярах следует, что SD — высота в грани SAB. Так как SS
— диаметр окружности, проходящей через S, и A, то ∠SAS
= см. рис. 328). Обозначив через R и r соответственно радиусы описанной сферы пирамиды и вписанной окружности треугольника, имеем S
A
2
= S
A
2
+ AA
2
= (SS
2
− SA
2
) + AD
2
= SS
2
−
− (SA
2
− AD
2
) = SS
2
− SD
2
= SS
2
− (SI
2
+ ID
2
) = (2R)
2
− SI
2
− Аналогично вычисляя и S
C
, получаем, что S
A
= S
B
= S
C
=
=
(2R)
2
− SI
2
− r
2
759. Перепишем условие задачи в виде равенства (x + 1)
n
− 1 =
= P (x)Q(x)
, где P (x) — многочлен с нечетными коэффициентами
ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ
Будем называтьдва многочлена f(x) и g(x) похожими и обозначать (x)
≡ g(x), если коэффициенты при одинаковых степенях у многочленов и g(x) имеют одинаковую четность. Тогда, если в верном равенстве мы заменим некоторые коэффициенты одного или нескольких многочленов на их остатки по модулю 2, то мы получим два похожих многочлена.
Следовательно,
(x + 1)
n
− 1 ≡ (x
k
+ x
k−1
+ . . . + Заменив в последнем равенстве переменную x на
1
x
и домножив обе части на x
n
, получаем + 1)
n
− x
n
≡ (x
k
+ x
k−1
+ . . . + При этом x
n−k
Q
1
x
— это некоторый многочлен степени, не превосходящей, от переменной x. Вычитая из (1) формулу (2), имеем 1 ≡ (x
k
+ x
k−1
+ . . . + для некоторого многочлена R(x). Пусть n не делится на k + 1, тогда n =
= q(k + 1) + r
, 0 < r < k + 1. Тогда многочлен x
n
− x
r
= x
r
(x
q(k+1)
− делится на x
k+1
− 1 = (x
k
+ . . . + 1)(x
− 1), а значит, x
r
− 1 = (x
n
− 1) −
− (x
n
− x
r
)
≡ (x
k
+ . . . + для некоторого многочлена R
1
(x)
. Это невозможно, ибо степеньмногочлена x
r
−1 не больше степени многочлена+ . . . + 1
, и они непохожи. В решении мы будем пользоваться следующей известной теоремой.
Теорема Холла. Пустьдан двудольный граф G те. его вершины разбиты на два подмножества A и B таких, что любое ребро соединяет вершины из разных подмножеств. Предположим, что для любого подмножества вершин A
1
⊆ A количество вершин вне больше, чем количество вершин, соединенных хотя бы с одной вершиной из A
1
. Тогда в графе найдется паросочетание (те. набор ребер с различными концами, содержащее все вершины множества Перейдем к решению задачи. Построим граф, вершины которого соответствуют пионерам, а ребра — знакомствам. Степени вершин этого графа не менее 50 и не более 100. Докажем вспомогательное утвержде- ние.
Лемма 1. Пусть k n m — натуральные числа. Тогда из
графа, степени вершин которого не менее n и не более m, можно
удалить несколько ребер так, чтобы степени всех вершин стали
не менее n − k и не более m − Доказательство. Понятно, что достаточно доказатьутверждение леммы для k = 1. До тех пор, пока естьребра, соединяющие пары вершин степени m, будем удалятьтакие ребра. Пустьтаких ребер больше нет
О
ТВЕТЫ
449
раскраски: а) все числа одного цвета б) числа 3k−2, k ∈ Z — цвета числа 3k − 1, k ∈ Z — цвета B, числа цвета C. 252. 150.
256. 2001.
257. p = 5, q = 3.
258. Нет. 265. Нельзя. 267. Выигрывает второй. Нельзя. Нельзя. Да, можно. n = 3.
287. Да, можно. 41. 294. Выигрывает первый. Верно. 297. 7. 299. Выигрывает второй. 301. 3. 308. Победит второй игрок. 310. 98. 313. α =
=
π
8
+
πn
2
. 315. 870. 317. x =
=
±1. 320. Не всегда. 321. 2 и 3.
329. Вили в 17.45. 330. 13.
332. Не существует. 333. Немо- жет. 335. 1. 336. Нельзя. 341. Не могло+ 1
350. 2.
356. Не сможет ни один из них. 101105. 359. 4.
362. Первый. Можно. 367. (2
k
, где k 0.
369. Шестьигр.
370. Можно. Не сможет. Не существует. 135
◦
380. N! (N! = 1 · 2 · . . . · N).
381. Можно. 383. (2, 2). 384. Не может. Таких чисел нет. −2.
387. N! (N! =
= 1
· 2 · . . . · N).
391. Больше тех, у которых семнадцатая с конца цифра — 7.
394. Может. Нельзя. 33.
398. Не может. A
1
B
1
C
1
— равносторонний, все углы равны. Может. Немо- гут. 405. 33. 407. Может. 412. Не может. 415. При всех нечетных n.
416.
2n
3
. 419. 13. 424. 30000.
425. Не может. Нельзя. 16.
431. 48.
432.
n + 1 2
436. При F = 8.
438. Верно, −
−1, −1, 1} с точностью до перестановки чисел четверки. 447. n =
= 8k + 1
, где k ∈ N.
451. Выигрывает начинающий. 25.
473. 0 или 12.
475. Не может. Можно. 478. 180
◦
. 479. 0.
481. Корней нет. 483. Существует. Нет, не могут. 494. При четных n.
497. Не представимых в таком виде. Нельзя. Не могла. Сможет тот сержант, который дежурит третьим. 512. Да,
мог. Например, записав числа 1/4,
1/2, 1, 2, 5, 5 2
, 5 4
, 5 8
, 5 16
, 5 32
513. Нет. Не существуют. Не существует. 520. За пять вопросов. Всем, кроме,
бытьможет, одного. Нет. 106.
529. (±1; 0); (±4; 3);
(
±4; 5).
533. Не существуют. m = n = l = 2. 538. 99 мудрецов. Трехчленов, не имеющих корней, больше. Найдутся. Верно. За часа. звена (здесь [x] целая частьчисла x). 557. Нельзя. Удачная расстановка единственна — все числа равны +1.
565. r
1998
= 1997,5
566. Да. 9. 572. Можно. 573. n(n+1).
576. Выигрывает Петя. 578. a
1
=
= a
2
= . . . = 2
585. Нет. Выигрывает Петя. a +
Будем называтьдва многочлена f(x) и g(x) похожими и обозначать (x)
≡ g(x), если коэффициенты при одинаковых степенях у многочленов и g(x) имеют одинаковую четность. Тогда, если в верном равенстве мы заменим некоторые коэффициенты одного или нескольких многочленов на их остатки по модулю 2, то мы получим два похожих многочлена.
Следовательно,
(x + 1)
n
− 1 ≡ (x
k
+ x
k−1
+ . . . + Заменив в последнем равенстве переменную x на
1
x
и домножив обе части на x
n
, получаем + 1)
n
− x
n
≡ (x
k
+ x
k−1
+ . . . + При этом x
n−k
Q
1
x
— это некоторый многочлен степени, не превосходящей, от переменной x. Вычитая из (1) формулу (2), имеем 1 ≡ (x
k
+ x
k−1
+ . . . + для некоторого многочлена R(x). Пусть n не делится на k + 1, тогда n =
= q(k + 1) + r
, 0 < r < k + 1. Тогда многочлен x
n
− x
r
= x
r
(x
q(k+1)
− делится на x
k+1
− 1 = (x
k
+ . . . + 1)(x
− 1), а значит, x
r
− 1 = (x
n
− 1) −
− (x
n
− x
r
)
≡ (x
k
+ . . . + для некоторого многочлена R
1
(x)
. Это невозможно, ибо степеньмногочлена x
r
−1 не больше степени многочлена+ . . . + 1
, и они непохожи. В решении мы будем пользоваться следующей известной теоремой.
Теорема Холла. Пустьдан двудольный граф G те. его вершины разбиты на два подмножества A и B таких, что любое ребро соединяет вершины из разных подмножеств. Предположим, что для любого подмножества вершин A
1
⊆ A количество вершин вне больше, чем количество вершин, соединенных хотя бы с одной вершиной из A
1
. Тогда в графе найдется паросочетание (те. набор ребер с различными концами, содержащее все вершины множества Перейдем к решению задачи. Построим граф, вершины которого соответствуют пионерам, а ребра — знакомствам. Степени вершин этого графа не менее 50 и не более 100. Докажем вспомогательное утвержде- ние.
Лемма 1. Пусть k n m — натуральные числа. Тогда из
графа, степени вершин которого не менее n и не более m, можно
удалить несколько ребер так, чтобы степени всех вершин стали
не менее n − k и не более m − Доказательство. Понятно, что достаточно доказатьутверждение леммы для k = 1. До тех пор, пока естьребра, соединяющие пары вершин степени m, будем удалятьтакие ребра. Пустьтаких ребер больше нет
УЧЕБНЫЙ ГОД, 11
КЛАСС
447
обозначим через A множество всех вершин степени m в полученном после удаления ребер графе G, а через B множество всех остальных вершин.
Рассмотрим двудольный граф на тех же вершинах, в котором останутся лишьребра между A и B. Проверим выполнение условия теоремы
Холла для этого графа. Рассмотрим множество A
1
⊂ A, пусть B
1
— множество вершин, смежных с вершинами из A
1
. Из выходит не менее ребер к вершинам множества B
1
, а в каждую вершину из входит менее m ребер, следовательно, |B
1
| |A
1
| через |X| мы, как обычно, обозначаем количество элементов в множестве X). Таким образом, по теореме Холла существует паросочетание, содержащее все вершины из Удалив из графа G ребра этого паросочетания, мы получим граф G
1
, степени вершин которого не менее n − 1 и не более m − 1. Лемма 1 доказана.
Перейдем к решению задачи. Применив лемму 1 для исходного графа и k = 30, мы получим граф H, степени вершин которого не менее 20 и не более 70. Сделаем его ребра красными. Для каждой вершины этого графа отметим 20 вершин среди ее соседей и попарно соединим эти вершин зелеными ребрами. Так как из каждой вершины выходит не более красных ребер, то из нее выходит не более, чем 70 · 19 = 1330 зеленых ребер.
Рассмотрим граф с зелеными ребрами на вершинах графа Несложно по очереди покраситьэти вершины в 1331 цвет так, чтобы соседние вершины были разноцветными рассматривая каждую следующую вершину, покрасим ее в любой незадействованный среди ее соседей цвет.
Теперьопятьрассмотрим граф H с красными ребрами. Среди соседей каждой его вершины есть выделенных и все они покрашены в разные цвета.
Замечание. Можно покраситьпилотки пионеров всего в 761 цвет.
Для доказательства этого факта надо заменим лемму 1 на более сильную лемму 2, доказательство которой предоставляется читателю.
Лемма 2. Пусть k n — натуральные числа. В графе G степени всех вершин не менее n и не более 2n. Тогда можно удалить
несколько ребер так, чтобы степени всех вершин стали не менее и не более 2k.
КЛАСС
447
обозначим через A множество всех вершин степени m в полученном после удаления ребер графе G, а через B множество всех остальных вершин.
Рассмотрим двудольный граф на тех же вершинах, в котором останутся лишьребра между A и B. Проверим выполнение условия теоремы
Холла для этого графа. Рассмотрим множество A
1
⊂ A, пусть B
1
— множество вершин, смежных с вершинами из A
1
. Из выходит не менее ребер к вершинам множества B
1
, а в каждую вершину из входит менее m ребер, следовательно, |B
1
| |A
1
| через |X| мы, как обычно, обозначаем количество элементов в множестве X). Таким образом, по теореме Холла существует паросочетание, содержащее все вершины из Удалив из графа G ребра этого паросочетания, мы получим граф G
1
, степени вершин которого не менее n − 1 и не более m − 1. Лемма 1 доказана.
Перейдем к решению задачи. Применив лемму 1 для исходного графа и k = 30, мы получим граф H, степени вершин которого не менее 20 и не более 70. Сделаем его ребра красными. Для каждой вершины этого графа отметим 20 вершин среди ее соседей и попарно соединим эти вершин зелеными ребрами. Так как из каждой вершины выходит не более красных ребер, то из нее выходит не более, чем 70 · 19 = 1330 зеленых ребер.
Рассмотрим граф с зелеными ребрами на вершинах графа Несложно по очереди покраситьэти вершины в 1331 цвет так, чтобы соседние вершины были разноцветными рассматривая каждую следующую вершину, покрасим ее в любой незадействованный среди ее соседей цвет.
Теперьопятьрассмотрим граф H с красными ребрами. Среди соседей каждой его вершины есть выделенных и все они покрашены в разные цвета.
Замечание. Можно покраситьпилотки пионеров всего в 761 цвет.
Для доказательства этого факта надо заменим лемму 1 на более сильную лемму 2, доказательство которой предоставляется читателю.
Лемма 2. Пусть k n — натуральные числа. В графе G степени всех вершин не менее n и не более 2n. Тогда можно удалить
несколько ребер так, чтобы степени всех вершин стали не менее и не более 2k.
ОТВЕТЫ. 987654321. 3. а) Необязательно. б) Обязательно. 4. Заходов. Выигрывает второй игрок. 17. n = 3. 21. Не сможет. Окружностьс центром в точке B и радиусом, равным высоте треугольника ABC. 25. 30 минут. Существует. При восьми лжецах. 31. p = 2, q = 7, r = 3,
s = или p = 2, q = 7, r = 11, s =
= 3
. 32. 4 месяца. 33. ада б) нет. 5. 38. 208. 50. Нельзя. 52. Не существует. 53. p = 3. 56. Нельзя 19 3
. 61. 3. 63. При четных. Не хватит. 10 6
− 10 · 9 5
. 75. Не существует. Можно.
См. рис. 67. 78. α = 30
◦
. 79. 4.
81. x
2
+ax
, x
2
−ax, a — любое число. Выигрывает второй. 85. n =
= 1996
91. Прямая, перпендикулярная биссектрисе угла B т. е.
биссектриса внешнего угла) без самой точки B.
98. при четном n,
n + 1 при нечетном n.
101. 16. 102. n = 2. 104. Несу- ществует.
110. 2. 111. p = 7,
q = 3
. 112. 14. 114. Выигрывает партнер игрока, делающего первый ход. 124. Нельзя. 126. 12.
135. Не существуют. 136. α = 1.
137. Не существуют. 138. Немо- гут. 145. Все треугольники, длины сторон которых пропорциональны и 5 (Египетский треугольник. Не могут. Выигрывает первый. Нельзя. 153. b = 0, 0 a <
< 4
. 156. Начинающий. 157. x =
=
−3 +
√
9 + 12n
6
, n = 0, 1, 2, 3, 4, 5.
158. Нет. 159. (n − 2)
3
. 160. рублей. 1260.
164. Нельзя. Нет 6
170. 1999.
171. CA
1
: A
1
B =
= BC
1
: C
1
A = AB
1
: B
1
C =
= 2 : 1
172. 5.
175. Выигрывает первый игрок. 176. Нельзя. Да. 197. Нет. 7. 204. Если количество монет в мешках различается небо- лее, чем на 1, то алмаз достанется второму пирату, в противном случае первому. 205. Не обманывает. 48. 209. Сможет. 210. Существуют. Одним взвешиванием. Не существует. 226. Тремя. При N 8.
233. Нельзя. 14. 236. При любых n и m победит первый игрок. 238. Обязательно. Нельзя. 242. Верно. 25. 246. Существует. Например или 2 · 5 2000
. 251. Две
∗)
Приведены ответы ко всем задачам кроме тех, в которых требуется доказатьутвержде- ние.
s = или p = 2, q = 7, r = 11, s =
= 3
. 32. 4 месяца. 33. ада б) нет. 5. 38. 208. 50. Нельзя. 52. Не существует. 53. p = 3. 56. Нельзя 19 3
. 61. 3. 63. При четных. Не хватит. 10 6
− 10 · 9 5
. 75. Не существует. Можно.
См. рис. 67. 78. α = 30
◦
. 79. 4.
81. x
2
+ax
, x
2
−ax, a — любое число. Выигрывает второй. 85. n =
= 1996
91. Прямая, перпендикулярная биссектрисе угла B т. е.
биссектриса внешнего угла) без самой точки B.
98. при четном n,
n + 1 при нечетном n.
101. 16. 102. n = 2. 104. Несу- ществует.
110. 2. 111. p = 7,
q = 3
. 112. 14. 114. Выигрывает партнер игрока, делающего первый ход. 124. Нельзя. 126. 12.
135. Не существуют. 136. α = 1.
137. Не существуют. 138. Немо- гут. 145. Все треугольники, длины сторон которых пропорциональны и 5 (Египетский треугольник. Не могут. Выигрывает первый. Нельзя. 153. b = 0, 0 a <
< 4
. 156. Начинающий. 157. x =
=
−3 +
√
9 + 12n
6
, n = 0, 1, 2, 3, 4, 5.
158. Нет. 159. (n − 2)
3
. 160. рублей. 1260.
164. Нельзя. Нет 6
170. 1999.
171. CA
1
: A
1
B =
= BC
1
: C
1
A = AB
1
: B
1
C =
= 2 : 1
172. 5.
175. Выигрывает первый игрок. 176. Нельзя. Да. 197. Нет. 7. 204. Если количество монет в мешках различается небо- лее, чем на 1, то алмаз достанется второму пирату, в противном случае первому. 205. Не обманывает. 48. 209. Сможет. 210. Существуют. Одним взвешиванием. Не существует. 226. Тремя. При N 8.
233. Нельзя. 14. 236. При любых n и m победит первый игрок. 238. Обязательно. Нельзя. 242. Верно. 25. 246. Существует. Например или 2 · 5 2000
. 251. Две
∗)
Приведены ответы ко всем задачам кроме тех, в которых требуется доказатьутвержде- ние.
О
ТВЕТЫ
449
раскраски: а) все числа одного цвета б) числа 3k−2, k ∈ Z — цвета числа 3k − 1, k ∈ Z — цвета B, числа цвета C. 252. 150.
256. 2001.
257. p = 5, q = 3.
258. Нет. 265. Нельзя. 267. Выигрывает второй. Нельзя. Нельзя. Да, можно. n = 3.
287. Да, можно. 41. 294. Выигрывает первый. Верно. 297. 7. 299. Выигрывает второй. 301. 3. 308. Победит второй игрок. 310. 98. 313. α =
=
π
8
+
πn
2
. 315. 870. 317. x =
=
±1. 320. Не всегда. 321. 2 и 3.
329. Вили в 17.45. 330. 13.
332. Не существует. 333. Немо- жет. 335. 1. 336. Нельзя. 341. Не могло+ 1
350. 2.
356. Не сможет ни один из них. 101105. 359. 4.
362. Первый. Можно. 367. (2
k
, где k 0.
369. Шестьигр.
370. Можно. Не сможет. Не существует. 135
◦
380. N! (N! = 1 · 2 · . . . · N).
381. Можно. 383. (2, 2). 384. Не может. Таких чисел нет. −2.
387. N! (N! =
= 1
· 2 · . . . · N).
391. Больше тех, у которых семнадцатая с конца цифра — 7.
394. Может. Нельзя. 33.
398. Не может. A
1
B
1
C
1
— равносторонний, все углы равны. Может. Немо- гут. 405. 33. 407. Может. 412. Не может. 415. При всех нечетных n.
416.
2n
3
. 419. 13. 424. 30000.
425. Не может. Нельзя. 16.
431. 48.
432.
n + 1 2
436. При F = 8.
438. Верно, −
−1, −1, 1} с точностью до перестановки чисел четверки. 447. n =
= 8k + 1
, где k ∈ N.
451. Выигрывает начинающий. 25.
473. 0 или 12.
475. Не может. Можно. 478. 180
◦
. 479. 0.
481. Корней нет. 483. Существует. Нет, не могут. 494. При четных n.
497. Не представимых в таком виде. Нельзя. Не могла. Сможет тот сержант, который дежурит третьим. 512. Да,
мог. Например, записав числа 1/4,
1/2, 1, 2, 5, 5 2
, 5 4
, 5 8
, 5 16
, 5 32
513. Нет. Не существуют. Не существует. 520. За пять вопросов. Всем, кроме,
бытьможет, одного. Нет. 106.
529. (±1; 0); (±4; 3);
(
±4; 5).
533. Не существуют. m = n = l = 2. 538. 99 мудрецов. Трехчленов, не имеющих корней, больше. Найдутся. Верно. За часа. звена (здесь [x] целая частьчисла x). 557. Нельзя. Удачная расстановка единственна — все числа равны +1.
565. r
1998
= 1997,5
566. Да. 9. 572. Можно. 573. n(n+1).
576. Выигрывает Петя. 578. a
1
=
= a
2
= . . . = 2
585. Нет. Выигрывает Петя. a +
ОТВЕТЫ+ b + c =
−3. 601.
2 1001
−2 3
− 500.
604. Нельзя. 605. 7.
617. Эти суммы одинаковы. 500 или. 624. n = p
m
, где p — простое число, m ∈ N. 632. n = p
k
, p простое, или n = 12. 633. 97 средних чисел. 636. При n участниках. Нельзя. 644. 10. 646. n = k−
−1. 661. 10010. 668. a
2003
= 10p
671. Нельзя. 680. 209.
691. За вопросов. 693. Существуют. Всегда. 695. 51 хорошая пара. За 2003 вопроса. Существует. Верно. 716. Может. За вопроса. 725. 16. 729. 49.
733. Не существует. 734. Нельзя. 117. 743. Выигрывает игрок,
делающий второй ход. 117.
755. Выигрывает первый
−3. 601.
2 1001
−2 3
− 500.
604. Нельзя. 605. 7.
617. Эти суммы одинаковы. 500 или. 624. n = p
m
, где p — простое число, m ∈ N. 632. n = p
k
, p простое, или n = 12. 633. 97 средних чисел. 636. При n участниках. Нельзя. 644. 10. 646. n = k−
−1. 661. 10010. 668. a
2003
= 10p
671. Нельзя. 680. 209.
691. За вопросов. 693. Существуют. Всегда. 695. 51 хорошая пара. За 2003 вопроса. Существует. Верно. 716. Может. За вопроса. 725. 16. 729. 49.
733. Не существует. 734. Нельзя. 117. 743. Выигрывает игрок,
делающий второй ход. 117.
755. Выигрывает первый
СПИСОК ЛИТЕРАТУРЫ
451
СПИСОК ЛИТЕРАТУРЫ Агаханов Н.Х., Купцов Л.П., Нестеренко Ю.В., Резниченко С.В.,
Слинько А.М. Математические олимпиады. 9 класс. – М Просвещение, Учеб. лит. 1997. – 208 с Агаханов Н.Х., Подлипский О.К. Математические олимпиады Московской области. – Изд. е, испр. и доп. – М Физматкнига, 2006. –
320 с Агаханов Н.Х., Подлипский О.К. Всероссийская олимпиада школьников по математике Методическое пособие / Науч. ред. Э.М. Ни- китин – М АПК и ППРО, 2005. – 140 с Агаханов Н.Х., Терешин ДА, Кузнецова ГМ. Школьные математические олимпиады. – М Дрофа, 1999. – 128 с Берлов С.Л., Иванов СВ, КохасьК.П. Петербургские математические олимпиады. – Изд. е стереотип. – Санкт-Пететрбург, Москва, Краснодар Лань, 2005. – 606 с Васильев Н.Б., Егоров А.А. Задачи Всесоюзных математических олимпиад. М Наука, 1988. – 288 с Виленкин Н.Я., Виленкин АН, Виленкин ПА. Комбинаторика. М ФИМА, МЦНМО, 2006. – 400 с Гальперин ГА, Толпыго А.К. Московские математические олимпиады М Просвещение, 1986. – 303 с Генкин С.А., Итенберг ИВ, Фомин Д.В. Ленинградские математические кружки. – Киров Аса, 1994. – 272 с Горбачев Н.В. Сборник олимпиадных задач по математике, – М.:
МЦНМО, 2005. – 560 с Зарубежные математические олимпиады / Под ред. И.Н. Сергеева. М Наука, 1987. – 416 с Канель-Белов А.Я., Ковальджи А.К. Как решают нестандартные задачи Изд. е, испр. / Под редакцией ВО. Бугаенко. – М МЦН-
МО, 2004. – 96 с Купцов Л.П., Нестеренко Ю.В., Резниченко СВ, Слинько А.М.
Математические олимпиады. 10 класс. – М Просвещение, Учеб.
лит. 1998. – 256 с Купцов Л.П., Нестеренко Ю.В., Резниченко СВ, Слинько А.М.
Математические олимпиады. 11 класс. – М Просвещение, Учеб.
лит. 1999. – 254 с Купцов Л.П., Резниченко СВ, Терешин ДА. Российские математические олимпиады школьников. Книга для учащихся. – Ростов-на-
Дону: Феникс, 1996. – 640 с
451
СПИСОК ЛИТЕРАТУРЫ Агаханов Н.Х., Купцов Л.П., Нестеренко Ю.В., Резниченко С.В.,
Слинько А.М. Математические олимпиады. 9 класс. – М Просвещение, Учеб. лит. 1997. – 208 с Агаханов Н.Х., Подлипский О.К. Математические олимпиады Московской области. – Изд. е, испр. и доп. – М Физматкнига, 2006. –
320 с Агаханов Н.Х., Подлипский О.К. Всероссийская олимпиада школьников по математике Методическое пособие / Науч. ред. Э.М. Ни- китин – М АПК и ППРО, 2005. – 140 с Агаханов Н.Х., Терешин ДА, Кузнецова ГМ. Школьные математические олимпиады. – М Дрофа, 1999. – 128 с Берлов С.Л., Иванов СВ, КохасьК.П. Петербургские математические олимпиады. – Изд. е стереотип. – Санкт-Пететрбург, Москва, Краснодар Лань, 2005. – 606 с Васильев Н.Б., Егоров А.А. Задачи Всесоюзных математических олимпиад. М Наука, 1988. – 288 с Виленкин Н.Я., Виленкин АН, Виленкин ПА. Комбинаторика. М ФИМА, МЦНМО, 2006. – 400 с Гальперин ГА, Толпыго А.К. Московские математические олимпиады М Просвещение, 1986. – 303 с Генкин С.А., Итенберг ИВ, Фомин Д.В. Ленинградские математические кружки. – Киров Аса, 1994. – 272 с Горбачев Н.В. Сборник олимпиадных задач по математике, – М.:
МЦНМО, 2005. – 560 с Зарубежные математические олимпиады / Под ред. И.Н. Сергеева. М Наука, 1987. – 416 с Канель-Белов А.Я., Ковальджи А.К. Как решают нестандартные задачи Изд. е, испр. / Под редакцией ВО. Бугаенко. – М МЦН-
МО, 2004. – 96 с Купцов Л.П., Нестеренко Ю.В., Резниченко СВ, Слинько А.М.
Математические олимпиады. 10 класс. – М Просвещение, Учеб.
лит. 1998. – 256 с Купцов Л.П., Нестеренко Ю.В., Резниченко СВ, Слинько А.М.
Математические олимпиады. 11 класс. – М Просвещение, Учеб.
лит. 1999. – 254 с Купцов Л.П., Резниченко СВ, Терешин ДА. Российские математические олимпиады школьников. Книга для учащихся. – Ростов-на-
Дону: Феникс, 1996. – 640 с
СПИСОК ЛИТЕРАТУРЫ Кюршак Й, Нейкомм Д, Хайош Д, Шурани Я. Венгерские математические олимпиады. – М Мир, 1976. – 543 с Леман А.А. Сборник задач Московских математических олимпиад. М Просвещение, 1965. – 384 с Муштари Д.Х. Подготовка к математическим олимпиадам. – Казань:
Изд-во Казан. матем. об-ва, 2000. – 239 с Оре О. Графы и их применение. – Изд. е стереотип. – М КомКни- гас Прасолов В.В. Задачи по планиметрии. – Изд. е испр. и доп. – М.:
МЦНМО, 2006. – 640 с Прасолов В.В., Шарыгин И.Ф. Задачи по стереометрии. – М Наука с Савин А.П. и др. Физико-математические олимпиады. Сборник. М Знание, 1977. – 160 с Седракян НМ, Авоян А.М. Неравенства. Методы доказательства М Физматлит, 2002. – 256 с Серпинский В. 250 задач по теории чисел. – М НИЦ РХД, 2004. –
160 с Фомин Д.В. Санкт-Петербургские математические олимпиады. –
СПб.: Политехника, 1994. – 309 с Федоров Р.М., Канель-Белов А.Я., Ковальджи А.К., Ященко И.В.
Московские математические олимпиады 1993–2005 г. / Под ред.
В.М. Тихомирова. – М МЦНМО, 2006. – 456 с Шарыгин И.Ф. Геометрия. Планиметрия. 9 — 11 кл. – Изд. е стереотип М Дрофа, 2001. – 398 с Эвнин А. Ю. Элементарная теория чисел. Сборник олимпиадных задач Челябинск Изд-во ЧГТУ, 1996. — 76 с Яковлев Г.Н., Купцов Л.П., Резниченко СВ, Гусятников П.Б. Всероссийские математические олимпиады школьников. – М Просвещение с
Изд-во Казан. матем. об-ва, 2000. – 239 с Оре О. Графы и их применение. – Изд. е стереотип. – М КомКни- гас Прасолов В.В. Задачи по планиметрии. – Изд. е испр. и доп. – М.:
МЦНМО, 2006. – 640 с Прасолов В.В., Шарыгин И.Ф. Задачи по стереометрии. – М Наука с Савин А.П. и др. Физико-математические олимпиады. Сборник. М Знание, 1977. – 160 с Седракян НМ, Авоян А.М. Неравенства. Методы доказательства М Физматлит, 2002. – 256 с Серпинский В. 250 задач по теории чисел. – М НИЦ РХД, 2004. –
160 с Фомин Д.В. Санкт-Петербургские математические олимпиады. –
СПб.: Политехника, 1994. – 309 с Федоров Р.М., Канель-Белов А.Я., Ковальджи А.К., Ященко И.В.
Московские математические олимпиады 1993–2005 г. / Под ред.
В.М. Тихомирова. – М МЦНМО, 2006. – 456 с Шарыгин И.Ф. Геометрия. Планиметрия. 9 — 11 кл. – Изд. е стереотип М Дрофа, 2001. – 398 с Эвнин А. Ю. Элементарная теория чисел. Сборник олимпиадных задач Челябинск Изд-во ЧГТУ, 1996. — 76 с Яковлев Г.Н., Купцов Л.П., Резниченко СВ, Гусятников П.Б. Всероссийские математические олимпиады школьников. – М Просвещение с
Приложение АВТОРЫ ЗАДАЧ
Курсивом помечены задачи, написанные в соавторстве
С. Августинович
(2)
: 90, Н. Авилов
(2)
: 63, Н. Агаханов
(53)
: 1, 29, 33, 38, 41, 105, 109,
135, 137, 153, 173, 174, 201, 225, 242, 249,
258, 269, 270, 274, 281, 285, 289, 290, 294,
313, 329, 331, 334, 342, 349, 377, 398, 402,
429, 469, 513, 515, 525, 533, 543, 593, 597,
609, 617, 618, 641, 665, 673, 681, 685, А. Акопян
(4)
: 366, 706, 719, И. Акулич
(2)
: 170, М. Антонов 180, А. Бадзян
(3)
: 372, 412, Ф. Бахарев
(3)
: 577, 688, А. Белов
(9)
: 57, 104, 116, 130, 167, 462, 491,
568, А. Берзиньш
(2)
: 60, С. Берлов
(61)
: 34, 39, 40, 178, 181, 192, 195,
211, 219, 232, 247, 283, 310, 315, 322, 326,
340, 343, 352, 360, 426, 466, 572, 575, 582,
586, 589, 598, 600, 603, 610, 616, 619, 622,
623, 631, 637, 638, 647, 648, 650, 658, 662,
666, 670, 671, 672, 674, 689, 692, 695, 699,
715, 720, 736, 737, 738, 739, 742, 744, И. Богданов 279, 287, 292, 296, 320,
328, 363, 365, 368, 376, 380, 385, 392, 395,
413, 424, 610, 611, 630, 656, 668, 693, 704,
708, 718, 723, 737, О. Богопольский
(1)
: А. Быстриков
(1)
: В. Вавилов 6, С. Волчёнков
(7)
: 234, 353, 384, 547, 569,
578, А. Воронецкий
(1)
: А. Галочкин
(3)
: 69, 449, Г. Гальперин
(1)
: А. Гарбер
(2)
: 416, М. Гарбер
(1)
: Е. Гладкова
(1)
: А. Глебов А. Голованов 193, 198, 200, 248, 261,
297, 323, 389, 391, 457, 461, 465, 485, 489,
493, 497, 517, 581, 594, 601, 649, 651, 681,
754, В. Гордон
(1)
: Я. Губин
(1)
: С. Гулько
(1)
: С. Дворянинов
(3)
: 49, 78, Д. Джукич
(4)
: 235, 610, 624, О. Дмитриев В. Дольников
(30)
: 68, 92, 99, 131, 140, 155,
187, 191, 224, 232, 245, 276, 282, 348, 554,
556, 563, 584, 590, 608, 611, 612, 635, 639,
656, 667, 675, 676, 703, С. Дужин
(3)
: 64, 102, Ф. Дужин
(1)
: М. Евдокимов
(6)
: 190, 196, 209, 504, Л. Емельянов 36, 124, 136, 165, 203,
213, 218, 240, 243, 254, 278, 295, 298, 306,
307, 309, 314, 318, 338, 351, 371, 374, 388,
390, 396, 399, 400, 404, 414, 420, 640, 642,
655, 672, 690, 699, 706, 731, Т. Емельянова
(5)
: 250, 354, 607, 627, Р. Женодаров
(17)
: 2, 16, 28, 31, 53, 61, 85,
89, 97, 156, 233, 237, 257, 363, 369, 386, В. Жуховицкий
(1)
: Жюри 221, 545, 691, С. Зайцев В. Замков В. Замятин
(1)
: А. Заславский
(2)
: 327, С. Злобин
(4)
: 179, 275, 583, Е. Знак И. Иванов С. Иванов С. Игонин
(1)
: И. Изместьев
(8)
: 60, 81, 96, 139, 166, 479,
552, М. Исаев
(1)
: А. Калинин 5, 18, 46, 450, Р. Карасёв
(10)
: 66, 135, 263, 324, 358, 563,
564, 567, 626, Д. Карпов 4, 224, 232, 454, 480, 523,
564, 570, 576, 592, 596, 628, 702, 760
Курсивом помечены задачи, написанные в соавторстве
С. Августинович
(2)
: 90, Н. Авилов
(2)
: 63, Н. Агаханов
(53)
: 1, 29, 33, 38, 41, 105, 109,
135, 137, 153, 173, 174, 201, 225, 242, 249,
258, 269, 270, 274, 281, 285, 289, 290, 294,
313, 329, 331, 334, 342, 349, 377, 398, 402,
429, 469, 513, 515, 525, 533, 543, 593, 597,
609, 617, 618, 641, 665, 673, 681, 685, А. Акопян
(4)
: 366, 706, 719, И. Акулич
(2)
: 170, М. Антонов 180, А. Бадзян
(3)
: 372, 412, Ф. Бахарев
(3)
: 577, 688, А. Белов
(9)
: 57, 104, 116, 130, 167, 462, 491,
568, А. Берзиньш
(2)
: 60, С. Берлов
(61)
: 34, 39, 40, 178, 181, 192, 195,
211, 219, 232, 247, 283, 310, 315, 322, 326,
340, 343, 352, 360, 426, 466, 572, 575, 582,
586, 589, 598, 600, 603, 610, 616, 619, 622,
623, 631, 637, 638, 647, 648, 650, 658, 662,
666, 670, 671, 672, 674, 689, 692, 695, 699,
715, 720, 736, 737, 738, 739, 742, 744, И. Богданов 279, 287, 292, 296, 320,
328, 363, 365, 368, 376, 380, 385, 392, 395,
413, 424, 610, 611, 630, 656, 668, 693, 704,
708, 718, 723, 737, О. Богопольский
(1)
: А. Быстриков
(1)
: В. Вавилов 6, С. Волчёнков
(7)
: 234, 353, 384, 547, 569,
578, А. Воронецкий
(1)
: А. Галочкин
(3)
: 69, 449, Г. Гальперин
(1)
: А. Гарбер
(2)
: 416, М. Гарбер
(1)
: Е. Гладкова
(1)
: А. Глебов А. Голованов 193, 198, 200, 248, 261,
297, 323, 389, 391, 457, 461, 465, 485, 489,
493, 497, 517, 581, 594, 601, 649, 651, 681,
754, В. Гордон
(1)
: Я. Губин
(1)
: С. Гулько
(1)
: С. Дворянинов
(3)
: 49, 78, Д. Джукич
(4)
: 235, 610, 624, О. Дмитриев В. Дольников
(30)
: 68, 92, 99, 131, 140, 155,
187, 191, 224, 232, 245, 276, 282, 348, 554,
556, 563, 584, 590, 608, 611, 612, 635, 639,
656, 667, 675, 676, 703, С. Дужин
(3)
: 64, 102, Ф. Дужин
(1)
: М. Евдокимов
(6)
: 190, 196, 209, 504, Л. Емельянов 36, 124, 136, 165, 203,
213, 218, 240, 243, 254, 278, 295, 298, 306,
307, 309, 314, 318, 338, 351, 371, 374, 388,
390, 396, 399, 400, 404, 414, 420, 640, 642,
655, 672, 690, 699, 706, 731, Т. Емельянова
(5)
: 250, 354, 607, 627, Р. Женодаров
(17)
: 2, 16, 28, 31, 53, 61, 85,
89, 97, 156, 233, 237, 257, 363, 369, 386, В. Жуховицкий
(1)
: Жюри 221, 545, 691, С. Зайцев В. Замков В. Замятин
(1)
: А. Заславский
(2)
: 327, С. Злобин
(4)
: 179, 275, 583, Е. Знак И. Иванов С. Иванов С. Игонин
(1)
: И. Изместьев
(8)
: 60, 81, 96, 139, 166, 479,
552, М. Исаев
(1)
: А. Калинин 5, 18, 46, 450, Р. Карасёв
(10)
: 66, 135, 263, 324, 358, 563,
564, 567, 626, Д. Карпов 4, 224, 232, 454, 480, 523,
564, 570, 576, 592, 596, 628, 702, 760
АВТОРЫ ЗАДАЧ
К. Кноп 73, 75, 103, 400, А. Ковальджи
(2)
: 499, П. Кожевников 7, 146, 151, 186, 223,
247, 312, 395, 615, 679, С. Кожухов П. Козлов 408, С. Конягин
(1)
: К. Кохась
(2)
: 79, А. Кочерова
(1)
: Д. Кузнецов 17, 55, 138, 177, 633, Б. Кукушкин Е. Куликов 361, 392, 722, М. Куликов Л. Купцов 434, 486, А. Левин
(1)
: Ю. Лифшиц
(9)
: 244, 251, 252, 266, 268, 620,
621, 643, Д. Любшин
(1)
: О. Ляшко
(2)
: 436, Е. Малинникова
(7)
: 9, 24, 108, 465, 519,
521, П. Мартынов Л. Медников 87, 94, С. Мисник
(1)
: Д. Митькин
(2)
: 433, М. Мурашкин
(4)
: 406, 409, 419, О. Мусин
(7)
: 70, 452, 484, 508, 542, 559, Н. Нецветаев
(1)
: В. Ню М. Островский
(1)
: А. Пастор 356, 652, 660, И. Певзнер
(1)
: А. Перлин
(6)
: 11, 12, 27, 427, 456, Ф. Петров 610, О. Подлипский
(27)
: 150, 164, 239, 258, 265,
279, 287, 296, 299, 332, 341, 362, 393, 395,
410, 424, 549, 585, 604, 609, 637, 669, 694,
710, 714, 717, Е. Порошенко
(1)
: В. Произволов
(2)
: 107, А. Протопопов А. Разборов И. Рубанов
(19)
: 44, 76, 100, 121, 147, 148,
149, 208, 226, 267, 277, 293, 304, 316, 325,
330, 432, 512, С. Рукшин
(2)
: 40, А. Савин
(1)
: Р. Садыков
(3)
: 189, 216, Н. Седракян
(1)
: 259 302, 305, 321, 333, 345, 359, 367, 375, В. Сендеров
(28)
: 197, 210, 217, 256, 301,
383, 415, 418, 481, 499, 507, 659, 681, 709,
721, 727, 732, 746, И. Сергеев А. Скопенков
(3)
: 59, 133, Д. Скробот
(1)
: А. Смирнов
(3)
: 696, 699, Л. Смирнова
(2)
: 122, М. Смуров
(6)
: 19, 455, 505, 511, 540, И. Соловьёв
(1)
: М. Сонкин
(34)
: 15, 35, 43, 51, 54, 62, 71, 82,
87, 91, 94, 119, 127, 128, 143, 154, 162, 184,
207, 212, 215, 230, 502, 518, 527, 529, 534,
550, 562, 571, 579, 587, 595, Е. Сопкина
(1)
: Д. Тамаркин
(3)
: 32, 440, Д. Тарасенко
(1)
: О. Тен
(1)
: Д. Терёшин
(19)
: 25, 47, 66, 212, 430, 438,
446, 448, 459, 463, 471, 478, 490, 495, 498,
515, 531, 591, С. Токарев
(27)
: 20, 52, 58, 80, 88, 111, 134,
183, 206, 214, 231, 271, 272, 335, 344, 350,
443, 447, 464, 473, 475, 476, 520, 535, 580,
636, С. Тухвебер
(1)
: В. Уфнаровский
(1)
: К. Фельдман
(1)
: В. Филимонов
(2)
: 364, Фольклор 262, А. Фомин 117, Д. Фон-дер-Флаас
(8)
: 8, 48, 439, 444, 503,
523, 536, Б. Френкин
(1)
: А. Храбров
(19)
: 222, 229, 246, 253, 284, 291,
336, 369, 378, 403, 413, 522, 574, 606, 613,
614, 668, 678, Д. Храмцов
(16)
: 83, 152, 159, 168, 175, 204,
236, 264, 288, 308, 311, 317, 319, 355, Ю. Хромин
(2)
: 320, Д. Цветов Г. Челноков 264, 292, 368, 376, 380, 392,
395, Е. Черепанов
(4)
: 189, 216, 605, Е. Чернышов
(1)
: А. Шаповалов
(25)
: 50, 56, 74, 77, 98, 106,
110, 113, 114, 115, 142, 157, 161, 169, 171,
176, 205, 483, 509, 514, 526, 532, 544, И. Шарыгин
(1)
: И. Ященко
(2)
: 112, Л. Ященко
(1)
: 481
Приложение ТЕМАТИЧЕСКИЙ РУБРИКАТОР
Олимпиадные задачи нестандартны по формулировками для решения многих из них требуются яркие и оригинальные математической идеи.
Тем не менее, условно разобьем задачи на рубрики по содержанию и методам решения, а также дадим краткий обзор наиболее часто употребляемых приемов и фактов. После каждого раздела рубрикатора приводятся номера иллюстрирующих его задач из настоящего сборника.
Некоторые общие методы решения олимпиадных задач
Выделим наиболее важные идеи, которые применяются во многих ситуациях. При решении трудных многоходовых задач они могут служить средством для доказательства вспомогательных утверждений.
Метод математической индукции
Этот метод состоит в следующем.
Пустьимеется последовательностьутверждений T
1
, T
2
, T
3
, . . . , про которую известно, что) верно (база индукции) из того, что верно, вытекает, что верно (для n = 1, 2, 3, . . переходили шаг индукции).
Тогда вся последовательность состоит из верных утверждений.
Возможна вариация условия 2): из предположения, что утверждения, T
2
, . . . , верны, вытекает, что верно (для n = 1, 2, 3, . . Также возможно применение индукции в форме
спуска
— сведения доказательства утверждения к доказательству утверждений для некоторых k < n. Иногда к утверждению задачи индукция напрямую неприменима, но можно сформулироватьвспомогательное утверждение,
которое доказывается при помощи индукции, 68, 144, 180, 192, 227, 284, 291, 312, 440, 446, 456, 560, 565, 566,
574, 596, 597, 600, 608, 626, 684, Принцип Дирихле
Классическая формулировка этого принципа заключается в следующем если в n клетках сидит n + 1 кроликов, то найдется клетка, в которой сидит не менее двух кроликов.
Более общая форма если в nk клетках сидит не менее nk+1 кроликов,
то найдется клетка, в которой сидит не менее k + 1 кроликов, 55, 140, 181, 187, 191, 239, 264, 282, 396, 409, 489, 526, 530, 573,
616, 620, 622, 641, 645, 648.
Олимпиадные задачи нестандартны по формулировками для решения многих из них требуются яркие и оригинальные математической идеи.
Тем не менее, условно разобьем задачи на рубрики по содержанию и методам решения, а также дадим краткий обзор наиболее часто употребляемых приемов и фактов. После каждого раздела рубрикатора приводятся номера иллюстрирующих его задач из настоящего сборника.
Некоторые общие методы решения олимпиадных задач
Выделим наиболее важные идеи, которые применяются во многих ситуациях. При решении трудных многоходовых задач они могут служить средством для доказательства вспомогательных утверждений.
Метод математической индукции
Этот метод состоит в следующем.
Пустьимеется последовательностьутверждений T
1
, T
2
, T
3
, . . . , про которую известно, что) верно (база индукции) из того, что верно, вытекает, что верно (для n = 1, 2, 3, . . переходили шаг индукции).
Тогда вся последовательность состоит из верных утверждений.
Возможна вариация условия 2): из предположения, что утверждения, T
2
, . . . , верны, вытекает, что верно (для n = 1, 2, 3, . . Также возможно применение индукции в форме
спуска
— сведения доказательства утверждения к доказательству утверждений для некоторых k < n. Иногда к утверждению задачи индукция напрямую неприменима, но можно сформулироватьвспомогательное утверждение,
которое доказывается при помощи индукции, 68, 144, 180, 192, 227, 284, 291, 312, 440, 446, 456, 560, 565, 566,
574, 596, 597, 600, 608, 626, 684, Принцип Дирихле
Классическая формулировка этого принципа заключается в следующем если в n клетках сидит n + 1 кроликов, то найдется клетка, в которой сидит не менее двух кроликов.
Более общая форма если в nk клетках сидит не менее nk+1 кроликов,
то найдется клетка, в которой сидит не менее k + 1 кроликов, 55, 140, 181, 187, 191, 239, 264, 282, 396, 409, 489, 526, 530, 573,
616, 620, 622, 641, 645, 648.
ТЕМАТИЧЕСКИЙ РУБРИКАТОР
Вариацией принципа Дирихле является метод усреднения, состоящий в следующем. Пустьдля каждому из n вариантов сопоставлено некое число. Тогда если сумма всех n чисел равна S, то одному из вариантов сопоставлено число, не меньшее S/n.
12, 195, 468, Принцип крайнего
При решении задач полезно рассматриватьобъекты и случаи, являющиеся в некотором смысле
крайними
. Приведем примеры начала рассуждений по принципу крайнего:
среди данных n точек выберем пару наиболее удаленных
,
предположим, что условие неверно, и рассмотрим многочлен минимальной степени, не удовлетворяющий условию
,
среди всех подмножеств данного конечного множества чисел выберем подмножество с наибольшей суммой
и т. д, 211, 276, 294, 310, 316, 324, 330, 332, 392, 584.
Инварианты
Если в задаче речьидет о последовательном выполнении некоторых операций, то ключевым шагом к решению может оказаться нахождение величины или характеристики, которая сохраняется при выполнении операций (такая величина называется инвариантом, либо нахождение величины, которая изменяется монотонно (например, не увеличивается) при выполнении операций (такая величина называется полуинвариантом).
4, 33, 139, 164, 165, 269, 394, 427, 479, Олимпиадные задачи можно условно разделитьна четыре раздела:
алгебра
,
теория чисел
(задачи о целых числах),
геометрия
и наиболее богатый по тематике раздел
комбинаторика
1. Алгебра
Алгебраические преобразования
При решении уравнений, систем и некоторых других задач, по формулировке близких к
школьным
, основным моментом в решении является выполнение некоторой выкладки, тождественного преобразования (например, группировки слагаемых или сомножителей, использование основных алгебраических формул, 18, 57, 73, 89, 102, 117, 125, 128, 201, 237, 289, 302, 361, 386, 408,
423, 425, 449, 453, 521, 565, 617, 665, Задачи об арифметических, геометрических прогрессиях и других числовых последовательностях, 168, 222, 261, 375, 381, 578, 678, Текстовые задачи на составление уравнений, неравенств
Вариацией принципа Дирихле является метод усреднения, состоящий в следующем. Пустьдля каждому из n вариантов сопоставлено некое число. Тогда если сумма всех n чисел равна S, то одному из вариантов сопоставлено число, не меньшее S/n.
12, 195, 468, Принцип крайнего
При решении задач полезно рассматриватьобъекты и случаи, являющиеся в некотором смысле
крайними
. Приведем примеры начала рассуждений по принципу крайнего:
среди данных n точек выберем пару наиболее удаленных
,
предположим, что условие неверно, и рассмотрим многочлен минимальной степени, не удовлетворяющий условию
,
среди всех подмножеств данного конечного множества чисел выберем подмножество с наибольшей суммой
и т. д, 211, 276, 294, 310, 316, 324, 330, 332, 392, 584.
Инварианты
Если в задаче речьидет о последовательном выполнении некоторых операций, то ключевым шагом к решению может оказаться нахождение величины или характеристики, которая сохраняется при выполнении операций (такая величина называется инвариантом, либо нахождение величины, которая изменяется монотонно (например, не увеличивается) при выполнении операций (такая величина называется полуинвариантом).
4, 33, 139, 164, 165, 269, 394, 427, 479, Олимпиадные задачи можно условно разделитьна четыре раздела:
алгебра
,
теория чисел
(задачи о целых числах),
геометрия
и наиболее богатый по тематике раздел
комбинаторика
1. Алгебра
Алгебраические преобразования
При решении уравнений, систем и некоторых других задач, по формулировке близких к
школьным
, основным моментом в решении является выполнение некоторой выкладки, тождественного преобразования (например, группировки слагаемых или сомножителей, использование основных алгебраических формул, 18, 57, 73, 89, 102, 117, 125, 128, 201, 237, 289, 302, 361, 386, 408,
423, 425, 449, 453, 521, 565, 617, 665, Задачи об арифметических, геометрических прогрессиях и других числовых последовательностях, 168, 222, 261, 375, 381, 578, 678, Текстовые задачи на составление уравнений, неравенств
ТЕМАТИЧЕСКИЙ РУБРИКАТОР, 79, 141, 145, 169, 173, 206, 271, 298, 329, Задачи, использующие тригонометрические функции и преобразования, Задачи о рациональных и иррациональных числах, 665, 673, 714.
Неравенства
При доказательстве неравенств часто используется следующие классические неравенства между средним гармоническим, геометрическим,
арифметическим и квадратическим (неравенство о средних) для положительных чисел a
1
, a
2
, . . . , a
n
:
n
1
a
1
+
1
a
2
+ . . . +
1
a
n
n
√
a
1
a
2
. . . a
n
a
1
+ a
2
+ . . . + a
n
n
a
2 1
+ a
2 2
+ . . . + Наиболее часто применимо неравенство между средним арифметическими средним геометрическим. Для двух чисел оно выглядит так + В неравенствах о средних равенства достигаются тогда и только тогда,
когда a
1
= a
2
= . . . = a
n
, поэтому они часто применимы при доказательстве симметричных неравенств (те. неравенств, не изменяющихся при перестановке любых двух переменных, 11, 49, 89, 179, 229, 342, 378, 403, 412, 653, 670, 692, В некоторых оценочных задачах используются соображения роста функций или последовательностей Вот простые примеры подобных оценок при n > 1 (говоря неформально, последовательность растет быстрее
последовательности n), x
2
> при x > 100 (квадратичная функция
растет быстрее
линейной). Различные оценки для наборов чисел и неравенства, связанные с упорядоченностью чисел, 168, 445, 602, 605, 612, 709, Разные неравенства (см. также оценочные задач из других разделов, 197, 345, 488, 583, 586, 675.
Многочлены
Задачи о свойствах квадратного трехчлена, 249, 274, 285, 305, 317, 427, 475, 512, 521, 525, 533, 541, 545,
593, 637, Для корней α
1
, α
2
, . . . , многочлена P (x) = x
n
+ c
1
x
n−1
+ . . . +
+ c
n−1
x + справедливы формулы (теорема Виета):
c
1
=
−(α
1
+ α
2
+ . . . + α
n
)
,
Неравенства
При доказательстве неравенств часто используется следующие классические неравенства между средним гармоническим, геометрическим,
арифметическим и квадратическим (неравенство о средних) для положительных чисел a
1
, a
2
, . . . , a
n
:
n
1
a
1
+
1
a
2
+ . . . +
1
a
n
n
√
a
1
a
2
. . . a
n
a
1
+ a
2
+ . . . + a
n
n
a
2 1
+ a
2 2
+ . . . + Наиболее часто применимо неравенство между средним арифметическими средним геометрическим. Для двух чисел оно выглядит так + В неравенствах о средних равенства достигаются тогда и только тогда,
когда a
1
= a
2
= . . . = a
n
, поэтому они часто применимы при доказательстве симметричных неравенств (те. неравенств, не изменяющихся при перестановке любых двух переменных, 11, 49, 89, 179, 229, 342, 378, 403, 412, 653, 670, 692, В некоторых оценочных задачах используются соображения роста функций или последовательностей Вот простые примеры подобных оценок при n > 1 (говоря неформально, последовательность растет быстрее
последовательности n), x
2
> при x > 100 (квадратичная функция
растет быстрее
линейной). Различные оценки для наборов чисел и неравенства, связанные с упорядоченностью чисел, 168, 445, 602, 605, 612, 709, Разные неравенства (см. также оценочные задач из других разделов, 197, 345, 488, 583, 586, 675.
Многочлены
Задачи о свойствах квадратного трехчлена, 249, 274, 285, 305, 317, 427, 475, 512, 521, 525, 533, 541, 545,
593, 637, Для корней α
1
, α
2
, . . . , многочлена P (x) = x
n
+ c
1
x
n−1
+ . . . +
+ c
n−1
x + справедливы формулы (теорема Виета):
c
1
=
−(α
1
+ α
2
+ . . . + α
n
)
,
ТЕМАТИЧЕСКИЙ РУБРИКАТОР α
1
α
2
+ α
1
α
3
+ . . . + α
n−1
α
n
,
c
n
= (
−1)
n
α
1
α
2
. . . те. (равно сумме произведений корней во всевозможных подмножествах из i корней).
Если дан набор из n чисел, иногда полезно рассмотретьмногочлен,
корнями которого являются эти числа. Задачи о корнях многочленов, 29, 34, 81, 149, 225, 242, 258, 293, 325, 355, 519, 553, 629, 649,
685, Разные задачи о многочленах, 38, 200, 253, 349, 412, 418, 432, 618, 683, 707, Функции и их свойства
Функциональные уравнения, неравенства, 136, 153, 221, 443, 458, 609, Использование графиков функций, 101, 225, В задачах могут использоваться различные свойства функций четность и нечетность, монотонность, непрерывность, дифференцируемость,
выпуклость, периодичность и т. д. В некоторых задачах речь идет оспе- циальных функциях ([x], {x} и т. д, 100, 128, 157, 193, 323, 490, 574, 601, 678, 753.
2. Теория чисел
Остатки
Пусть n — натуральное число, и для целых чисел a, q, r выполнено равенство, причем 0 r < n. Тогда q называется неполным
частным, а r — остатком при делении a на n. Целые числа a и b, дающие равные остатки при делении на n, иногда называются сравнимыми
по модулю n пишется a ≡ b (mod Рассмотрение остатков может бытьполезным в самых разных ситуациях. Остатки могут бытьпрепятствием для разрешимости уравнений в целых числах. Например, не существует натуральных x, y, для которых+ 1 = 3
y
, поскольку не может даватьостаток 2 при делении на Остаток может являться инвариантом в задачах, связанных с процес- сами.
Если r — остаток при делении a на b, то НОД(a, b)=НОД(r, b). На этом соображении основан алгоритм Евклида нахождения наибольшего общего делителя (НОД) целых чисел a и b: разделив a = на b = r
1
, в остатке получим r
2
; разделив на r
2
, в остатке получим r
3
, и т. д, в конце концов разделится на без остатка и будет равен НОД(a, b).
1
α
2
+ α
1
α
3
+ . . . + α
n−1
α
n
,
c
n
= (
−1)
n
α
1
α
2
. . . те. (равно сумме произведений корней во всевозможных подмножествах из i корней).
Если дан набор из n чисел, иногда полезно рассмотретьмногочлен,
корнями которого являются эти числа. Задачи о корнях многочленов, 29, 34, 81, 149, 225, 242, 258, 293, 325, 355, 519, 553, 629, 649,
685, Разные задачи о многочленах, 38, 200, 253, 349, 412, 418, 432, 618, 683, 707, Функции и их свойства
Функциональные уравнения, неравенства, 136, 153, 221, 443, 458, 609, Использование графиков функций, 101, 225, В задачах могут использоваться различные свойства функций четность и нечетность, монотонность, непрерывность, дифференцируемость,
выпуклость, периодичность и т. д. В некоторых задачах речь идет оспе- циальных функциях ([x], {x} и т. д, 100, 128, 157, 193, 323, 490, 574, 601, 678, 753.
2. Теория чисел
Остатки
Пусть n — натуральное число, и для целых чисел a, q, r выполнено равенство, причем 0 r < n. Тогда q называется неполным
частным, а r — остатком при делении a на n. Целые числа a и b, дающие равные остатки при делении на n, иногда называются сравнимыми
по модулю n пишется a ≡ b (mod Рассмотрение остатков может бытьполезным в самых разных ситуациях. Остатки могут бытьпрепятствием для разрешимости уравнений в целых числах. Например, не существует натуральных x, y, для которых+ 1 = 3
y
, поскольку не может даватьостаток 2 при делении на Остаток может являться инвариантом в задачах, связанных с процес- сами.
Если r — остаток при делении a на b, то НОД(a, b)=НОД(r, b). На этом соображении основан алгоритм Евклида нахождения наибольшего общего делителя (НОД) целых чисел a и b: разделив a = на b = r
1
, в остатке получим r
2
; разделив на r
2
, в остатке получим r
3
, и т. д, в конце концов разделится на без остатка и будет равен НОД(a, b).
ТЕМАТИЧЕСКИЙ РУБРИКАТОР, 18, 31, 36, 37, 111, 164, 165, 208, 251, 281, 296, 429, 469, 494, 552,
597, 648, 714, 721, 727, Делимость, простые числа, разложение на простые множители
Во многих задачах о делимости, НОД, НОК, используется существование и единственностьразложения на простые сомножители (основная
теорема арифметики. Полезно рассмотрение простого делителя p и показателя степени, в которой p входит в разложение чисел на простые множители, 58, 83, 110, 142, 149, 192, 232, 257, 279, 297, 336, 340, 349, 461,
485, 499, 501, 507, 535, 589, 594, 600, 624, 632, 664, 732, Отметим задачи с ключевой идеей четности, 92, 137, 202, 265, 394, 397, 433, 525, 533, В разных задачах на делимостьполезным оказываются следующие утверждения a
n
− делится на a − b для различных целых a, b и натурального+ делится на a + b для различных целых a, b и нечетного. Как следствие, получаем, что P (a) − P (b) делится на a − b для различных целых a, b и любого многочлена P (x) с целыми коэффициентами, 217, 321, 381, 389, Цифры и десятичная запись
Задачи о десятичной записи натуральных чисел и бесконечных десятичных дробях, 147, 170, 177, 238, 269, 335, 350, 365, 393, 477, 513, 547, 569,
581, 661, 668, 704, Признак делимости на 11: натуральное число делится на 11 тогда и только тогда, когда разность сумм цифр, стоящих начетных и на нечетных местах, делится на 11. Обобщение признаков делимости на 3 и на 9: натуральное число и его сумма цифр дают равные остатки при делении на и на 9. Используются также более простые признаки делимости на 4, 5, и т. д, 131, 308, 341, 363, Оценочные задачи в теории чисел
Несложными примерами могут служитьследующие оценки расстояние между двумя различными числами, делящимися на n, не меньше если a и b — точные квадраты, причем a > b > n, то a − b > 2
√
n
. Разные оценочные задачи, 105, 131, 248, 256, 277, 287, 311, 319, 367, 375, 383, 391, 465,
509, 517, 529, 638, 651, 693.
Теоретико-числовые функции
597, 648, 714, 721, 727, Делимость, простые числа, разложение на простые множители
Во многих задачах о делимости, НОД, НОК, используется существование и единственностьразложения на простые сомножители (основная
теорема арифметики. Полезно рассмотрение простого делителя p и показателя степени, в которой p входит в разложение чисел на простые множители, 58, 83, 110, 142, 149, 192, 232, 257, 279, 297, 336, 340, 349, 461,
485, 499, 501, 507, 535, 589, 594, 600, 624, 632, 664, 732, Отметим задачи с ключевой идеей четности, 92, 137, 202, 265, 394, 397, 433, 525, 533, В разных задачах на делимостьполезным оказываются следующие утверждения a
n
− делится на a − b для различных целых a, b и натурального+ делится на a + b для различных целых a, b и нечетного. Как следствие, получаем, что P (a) − P (b) делится на a − b для различных целых a, b и любого многочлена P (x) с целыми коэффициентами, 217, 321, 381, 389, Цифры и десятичная запись
Задачи о десятичной записи натуральных чисел и бесконечных десятичных дробях, 147, 170, 177, 238, 269, 335, 350, 365, 393, 477, 513, 547, 569,
581, 661, 668, 704, Признак делимости на 11: натуральное число делится на 11 тогда и только тогда, когда разность сумм цифр, стоящих начетных и на нечетных местах, делится на 11. Обобщение признаков делимости на 3 и на 9: натуральное число и его сумма цифр дают равные остатки при делении на и на 9. Используются также более простые признаки делимости на 4, 5, и т. д, 131, 308, 341, 363, Оценочные задачи в теории чисел
Несложными примерами могут служитьследующие оценки расстояние между двумя различными числами, делящимися на n, не меньше если a и b — точные квадраты, причем a > b > n, то a − b > 2
√
n
. Разные оценочные задачи, 105, 131, 248, 256, 277, 287, 311, 319, 367, 375, 383, 391, 465,
509, 517, 529, 638, 651, 693.
Теоретико-числовые функции
ТЕМАТИЧЕСКИЙ РУБРИКАТОР
В некоторых задачах участвуют различные функции, определенные на множестве натуральных чисел число делителей, сумма делителей и т. д, 85, 606, 614.
Конструктивы
Задачи на построение интересных примеров и конструкций, 183, 189, 210, 246, 363, 393, 477, 483, 493, 547, 566, 610, 738.
3. Геометрия
Основные факты. Признаки равенства треугольников
Широко используются основные факты школьного курса геометрии:
свойства средней линии, свойства равнобедренных треугольников, признаки равенства треугольников, свойства и признаки параллелограмма. В
задачах на вычисления применяются теоремы Пифагора, синусов, косинусов, также для вычислений привлекаются векторы или массы, 51, 62, 103, 107, 143, 174, 270, 275, 303, 309, 318, 334, 354, 366,
399, 455, 467, 527, 531, 619, 642, 650, 679.
Подобие
В подобных фигурах отношения любых соответствующих линейных элементов равно коэффициенту подобия. Подобие или теорема Фалеса используется, например, при вычислении отношения отрезков, лежащих на параллельных прямых, 9, 66, 119, 138, 151, 171, 190, 230, 243, 283, 374, 420, 486, 550,
555, 575, 582, 587, 603, 623, 674, 719, 735.
Площади
Отметим следующее свойство если прямые AB и CD пересекаются в точке O отличной от A, B, C, D), то отношение площадей треугольников
AOC
и BOD равно · OC
OB · OD
. Иногда площадьиспользуется как вспомогательное средство для вычислений, 94, 278, 390, 631, Вписанный угол
При решении большого числа планиметрических задач используется теорема о равенстве вписанных углов, опирающихся на одну дугу.
Предельным
вариантом этой теоремы является теорема об угле между касательной и хордой. Следствием теоремы о вписанных углах является теорема об угле между двумя секущими.
В геометрических конфигурациях можно проводитьвспомогательные окружности, пользуясь критерием вписанности четырехугольника (сумма
В некоторых задачах участвуют различные функции, определенные на множестве натуральных чисел число делителей, сумма делителей и т. д, 85, 606, 614.
Конструктивы
Задачи на построение интересных примеров и конструкций, 183, 189, 210, 246, 363, 393, 477, 483, 493, 547, 566, 610, 738.
3. Геометрия
Основные факты. Признаки равенства треугольников
Широко используются основные факты школьного курса геометрии:
свойства средней линии, свойства равнобедренных треугольников, признаки равенства треугольников, свойства и признаки параллелограмма. В
задачах на вычисления применяются теоремы Пифагора, синусов, косинусов, также для вычислений привлекаются векторы или массы, 51, 62, 103, 107, 143, 174, 270, 275, 303, 309, 318, 334, 354, 366,
399, 455, 467, 527, 531, 619, 642, 650, 679.
Подобие
В подобных фигурах отношения любых соответствующих линейных элементов равно коэффициенту подобия. Подобие или теорема Фалеса используется, например, при вычислении отношения отрезков, лежащих на параллельных прямых, 9, 66, 119, 138, 151, 171, 190, 230, 243, 283, 374, 420, 486, 550,
555, 575, 582, 587, 603, 623, 674, 719, 735.
Площади
Отметим следующее свойство если прямые AB и CD пересекаются в точке O отличной от A, B, C, D), то отношение площадей треугольников
AOC
и BOD равно · OC
OB · OD
. Иногда площадьиспользуется как вспомогательное средство для вычислений, 94, 278, 390, 631, Вписанный угол
При решении большого числа планиметрических задач используется теорема о равенстве вписанных углов, опирающихся на одну дугу.
Предельным
вариантом этой теоремы является теорема об угле между касательной и хордой. Следствием теоремы о вписанных углах является теорема об угле между двумя секущими.
В геометрических конфигурациях можно проводитьвспомогательные окружности, пользуясь критерием вписанности четырехугольника (сумма
ТЕМАТИЧЕСКИЙ РУБРИКАТОР
461
противоположных углов равна 180
◦
) и следующим утверждением для того, чтобы выпуклый четырехугольник ABCD был вписанным, необходимо и достаточно, чтобы выполнялосьравенство углов ABD и Приведем два полезных факта для произвольного треугольника. (лемма о трезубце) Середина дуги BC не содержащей точки описанной окружности треугольника ABC равноудалена от B, C и центра вписанной окружности. Точка, симметричная ортоцентру треугольника ABC относительно стороны, лежит на описанной окружности.
Эти факты несложно доказываются с помощью теоремы о вписанных углах и нередко используются как вспомогательные утверждения в более трудных конструкциях, 23, 35, 43, 47, 54, 59, 71, 82, 91, 127, 146, 154, 162, 178, 184, 212,
215, 219, 223, 247, 254, 295, 322, 338, 343, 372, 404, 414, 430, 434, 442,
474, 478, 502, 505, 518, 534, 571, 579, 595, 607, 666, 696, 731, 742, Секущие и касательные к окружностям
Из равенства отрезков касательных, проведенных из точки к окружности, вытекает, например, следующее полезное утверждение в треугольнике точки касания вписанной и вневписанной окружностей со стороной симметричны относительно середины BC.
Пустьдана окружность радиуса R с центром O и точка X на расстоянии от O. Если секущая, проходящая через точку X, пересекает окружностьв точках A и B, то произведение XA · XB не зависит от проведенной секущей и равно ±(d
2
− R
2
)
, где знак
+
выбирается для точки
X
вне ω, знак
−
выбирается для точки X внутри ω. Величина (d
2
− называется степенью точки X относительно окружности ω.
Пустьданы две неконцентрические окружности и ω
2
. Множество точек, имеющих равные степени относительно и ω
2
, является прямой, перпендикулярной линии центров, и называется радикальной осью
окружностей и Имеются пространственные аналоги степеньточки относительно сферы, радикальная плоскость двух неконцентрических сфер, 186, 388, 498, 555, 615, 662, 672, 724, Геометрические преобразования
Задачи с использованием движений осевой симметрии, поворота, параллельного переноса, 20, 23, 151, 207, 307, 343, 351, 364, 690, 713.
461
противоположных углов равна 180
◦
) и следующим утверждением для того, чтобы выпуклый четырехугольник ABCD был вписанным, необходимо и достаточно, чтобы выполнялосьравенство углов ABD и Приведем два полезных факта для произвольного треугольника. (лемма о трезубце) Середина дуги BC не содержащей точки описанной окружности треугольника ABC равноудалена от B, C и центра вписанной окружности. Точка, симметричная ортоцентру треугольника ABC относительно стороны, лежит на описанной окружности.
Эти факты несложно доказываются с помощью теоремы о вписанных углах и нередко используются как вспомогательные утверждения в более трудных конструкциях, 23, 35, 43, 47, 54, 59, 71, 82, 91, 127, 146, 154, 162, 178, 184, 212,
215, 219, 223, 247, 254, 295, 322, 338, 343, 372, 404, 414, 430, 434, 442,
474, 478, 502, 505, 518, 534, 571, 579, 595, 607, 666, 696, 731, 742, Секущие и касательные к окружностям
Из равенства отрезков касательных, проведенных из точки к окружности, вытекает, например, следующее полезное утверждение в треугольнике точки касания вписанной и вневписанной окружностей со стороной симметричны относительно середины BC.
Пустьдана окружность радиуса R с центром O и точка X на расстоянии от O. Если секущая, проходящая через точку X, пересекает окружностьв точках A и B, то произведение XA · XB не зависит от проведенной секущей и равно ±(d
2
− R
2
)
, где знак
+
выбирается для точки
X
вне ω, знак
−
выбирается для точки X внутри ω. Величина (d
2
− называется степенью точки X относительно окружности ω.
Пустьданы две неконцентрические окружности и ω
2
. Множество точек, имеющих равные степени относительно и ω
2
, является прямой, перпендикулярной линии центров, и называется радикальной осью
окружностей и Имеются пространственные аналоги степеньточки относительно сферы, радикальная плоскость двух неконцентрических сфер, 186, 388, 498, 555, 615, 662, 672, 724, Геометрические преобразования
Задачи с использованием движений осевой симметрии, поворота, параллельного переноса, 20, 23, 151, 207, 307, 343, 351, 364, 690, 713.
ТЕМАТИЧЕСКИЙ РУБРИКАТОР
В ряде задач уместно использование гомотетии. Полезно заметить, что две касающиеся окружности могут бытьпереведены одна в другую гомотетией с центром в точке касания, 259, 351, 450, 463, 562, 615, 627, 655, 699, 706, 740, 748.
Стереометрия
Основные свойства, связанные со сферой — равенство отрезков касательных, проведенных из одной точки, и теорема о произведении отрезков секущих. Задачи, в которых фигурирует сфера, 327, 360, 495, 543, 591, 640, В стереометрических задачах полезно рассмотрение сечений или проекций фигур. Разные задачи по стереометрии, 66, 167, 196, 262, 290, 422, 471, 515, Геометрические неравенства
Отметим основные несложные факты неравенство треугольника, наклонная не меньше проекции, в треугольнике против большей стороны лежит больший угол, в трехгранном угле сумма двух плоских углов больше третьего, 39, 78, 135, 235, 268, 331, 406, 426, 459, Комбинаторная геометрия
В этот раздел традиционно относят задачи о множествах точек, отрезков, произвольных многоугольниках, многогранниках, задачи о размещении фигур внутри других фигур, покрытии фигур другими фигурами.
Подходы для решения задач этого раздела часто ищутся исходя из
принципа крайнего:
рассмотрим среди данных точек точку с наименьшей абсциссой
,
выберем треугольник наибольшей площади сверши- нами в точках данного конечного множества
,
рассмотрим выпуклую
оболочку конечного множества точек те. наименьший выпуклый многоугольник, содержащий данные точки, и т.д.)
В ряде задач уместно использование гомотетии. Полезно заметить, что две касающиеся окружности могут бытьпереведены одна в другую гомотетией с центром в точке касания, 259, 351, 450, 463, 562, 615, 627, 655, 699, 706, 740, 748.
Стереометрия
Основные свойства, связанные со сферой — равенство отрезков касательных, проведенных из одной точки, и теорема о произведении отрезков секущих. Задачи, в которых фигурирует сфера, 327, 360, 495, 543, 591, 640, В стереометрических задачах полезно рассмотрение сечений или проекций фигур. Разные задачи по стереометрии, 66, 167, 196, 262, 290, 422, 471, 515, Геометрические неравенства
Отметим основные несложные факты неравенство треугольника, наклонная не меньше проекции, в треугольнике против большей стороны лежит больший угол, в трехгранном угле сумма двух плоских углов больше третьего, 39, 78, 135, 235, 268, 331, 406, 426, 459, Комбинаторная геометрия
В этот раздел традиционно относят задачи о множествах точек, отрезков, произвольных многоугольниках, многогранниках, задачи о размещении фигур внутри других фигур, покрытии фигур другими фигурами.
Подходы для решения задач этого раздела часто ищутся исходя из
принципа крайнего:
рассмотрим среди данных точек точку с наименьшей абсциссой
,
выберем треугольник наибольшей площади сверши- нами в точках данного конечного множества
,
рассмотрим выпуклую
оболочку конечного множества точек те. наименьший выпуклый многоугольник, содержащий данные точки, и т.д.)
1 ... 56 57 58 59 60 61 62 63 64
68, 75, 99, 211, 276, 348, 466, 559, 563, 590, 608, 611, 626, 656, 667,
710, Разные задачи на взаимное расположение фигур, 140, 158, 226, 245, 312, 416, 438, 448, 511, 532, 542, 635, 658,
676, 703, Разные оценочные задачи комбинаторной геометрии, 113, 155, 187, 263, 316, 484, 491, 522, 546, 554, 567.
Конструктивы
Разрезания, придумывание интересных геометрических конструкций, 203, 240, 300.
ТЕМАТИЧЕСКИЙ РУБРИКАТОР. Комбинаторика
Подсчет или оценка количества вариантов
Простейший способом отыскатьколичество вариантом является комбинаторный принцип счета если объект A можно выбрать a способами, и для каждого из этих a способов имеется b способов выбратьобъ- ект B, то количество способов выбратьпару (упорядоченную) объектов, равно ab. Пусть, например, требуется найти количество возможных обедов, состоящих из первого, второго и напитка, если на первое предложено 3 разных блюда, на второе — 7 блюд, на третье — 4 напитка.
Из принципа комбинаторного счета вытекает ответ 3 · 7 · 4 = В некоторых задачах используется основные формулы комбинатори- ки:
количество перестановок n символов равно n! = 1·2·3·. . формула для числа сочетаний количество элементных подмножеств элементного множества равно C
k
n
=
n!
k!(n − k)!
(0 k n).
32, 40, 74, 96, 108, 112, 126, 208, 410, 457, 462, 497, 500, 604, Различные оценочные задачи
Во многих задачах оконечных множествах, наборах чисел, таблицах,
ставится вопрос о нахождении экстремума некоторой величины или об установлении некоторой оценки комбинаторными методами, 115, 288, 304, 320, 358, 362, 369, 392, 419, 424, 428, 436, 439,
444, 454, 464, 480, 503, 508, 514, 520, 528, 556, 622, 633, 636, 680, 691,
695, 698, 708, 722.
Соответствия
Решающей идеей в задаче может бытьпостроение некоторого соответствия между объектами, 161, 166, 198, 202, 213, 234, 252, 380, 452, 460, 500, 524, 538,
541, 546, 551, 552, 580, 643, 718, Важный частный случай соответствия — разбиение на пары, 125, 147, 398, 523, 574, 617, Процессы и операции
Если в задачах речьидет о некотором пошаговом процессе, важным соображением (помимо отыскания инварианта или полуинварианта) может оказаться периодичность процесса, обратимость операции, так называемая дискретная непрерывность некоторой величины (так говорят,
если за одну операцию величина изменяется
не намного, Задачи на решетках
Подсчет или оценка количества вариантов
Простейший способом отыскатьколичество вариантом является комбинаторный принцип счета если объект A можно выбрать a способами, и для каждого из этих a способов имеется b способов выбратьобъ- ект B, то количество способов выбратьпару (упорядоченную) объектов, равно ab. Пусть, например, требуется найти количество возможных обедов, состоящих из первого, второго и напитка, если на первое предложено 3 разных блюда, на второе — 7 блюд, на третье — 4 напитка.
Из принципа комбинаторного счета вытекает ответ 3 · 7 · 4 = В некоторых задачах используется основные формулы комбинатори- ки:
количество перестановок n символов равно n! = 1·2·3·. . формула для числа сочетаний количество элементных подмножеств элементного множества равно C
k
n
=
n!
k!(n − k)!
(0 k n).
32, 40, 74, 96, 108, 112, 126, 208, 410, 457, 462, 497, 500, 604, Различные оценочные задачи
Во многих задачах оконечных множествах, наборах чисел, таблицах,
ставится вопрос о нахождении экстремума некоторой величины или об установлении некоторой оценки комбинаторными методами, 115, 288, 304, 320, 358, 362, 369, 392, 419, 424, 428, 436, 439,
444, 454, 464, 480, 503, 508, 514, 520, 528, 556, 622, 633, 636, 680, 691,
695, 698, 708, 722.
Соответствия
Решающей идеей в задаче может бытьпостроение некоторого соответствия между объектами, 161, 166, 198, 202, 213, 234, 252, 380, 452, 460, 500, 524, 538,
541, 546, 551, 552, 580, 643, 718, Важный частный случай соответствия — разбиение на пары, 125, 147, 398, 523, 574, 617, Процессы и операции
Если в задачах речьидет о некотором пошаговом процессе, важным соображением (помимо отыскания инварианта или полуинварианта) может оказаться периодичность процесса, обратимость операции, так называемая дискретная непрерывность некоторой величины (так говорят,
если за одну операцию величина изменяется
не намного, Задачи на решетках
ТЕМАТИЧЕСКИЙ РУБРИКАТОР
Задачи о клетчатых досках, таблицах, решетках, 159, 176, 181, 216, 220, 255, 266, 288, 292, 352, 384, 402, 424,
431, 439, 523, 528, 540, 568, 580, 598, 641, 645, 671, 680, 689, 708, В некоторых задачах используются вспомогательные раскраски, 63, 124, 152, 282, 332, 504, 573, 737.
Графы
Задачи огородах и дорогах, авиалиниях, турнирах зачастую являются переформулировкой вопросов из теории графов.
Граф (или граф без петель и кратных ребер) задается конечным множеством — множеством вершин графа, и множеством неупорядоченных пар вершин — ребер графа. Вершины графа удобно изображатьточ- ками, а ребра — линиями, соединяющими соответствующие пары вершин.
Вершины, соединенные ребром, называются соседними или смежными. Количество вершин, смежных с вершиной A, называется степенью
вершины A; вершина степени 1 называется висячей. В любом графе число вершин нечетной степени четно.
Путь — это последовательность ребер A
1
A
2
, A
2
A
3
, . . . , здесь BC — ребро, соединяющее вершины B и C); вершины и называются соответственно началом и концом пути. Путьпо ребрам A
1
A
2
,
A
2
A
3
, . . . , называется циклом, если A
1
= A
n
; цикл называется
простым, если вершины A
1
, A
2
, . . . , A
n−1
различны.
Компонентой связности вершины A называется множество вершин, включающее A и все вершины X, для которых существует путьс началом A и концом X. Компоненты связности различных вершин либо не пересекаются, либо совпадают, поэтому множество вершин графа разбивается на несколько попарно не пересекающихся компонент связности;
если компонента всего одна, то граф называется связным.
Теорема Эйлера утверждает, что в связном графе. существует цикл, содержащий каждое ребро ровно по разу, тогда и только тогда, когда степени всех вершин четны. существует путь, содержащий каждое ребро ровно по разу, тогда и только тогда, когда степени всех вершин, кроме возможно двух, четны.
Связный граф, в котором нет циклов, называется деревом. Количество ребер в дереве с n вершинами равно n − Если на каждом ребре графа задано направление, то граф называется
ориентированным.
Задачи о связности и компонентах связности, 159, 255, 356, 564, 570, 628, 644, Задачи о путях по ребрам графа, обходах ребер и вершин графа
466
С
ОДЕРЖАНИЕ
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Принятые обозначения . . . . . . . . . . . . . . . . . . . . . . . УСЛОВИЯ ЗАДАЧ
Окружной этап олимпиады . . . . . . . . . . . . . . . . . . . . . .
7 1993–1994 . . . . . . . . . . . . . . . . . . . . . .
10 1994–1995 . . . . . . . . . . . . . . . . . . . . . .
13 1995–1996 . . . . . . . . . . . . . . . . . . . . . .
16 1996–1997 . . . . . . . . . . . . . . . . . . . . . .
19 1997–1998 . . . . . . . . . . . . . . . . . . . . . .
23 1998–1999 . . . . . . . . . . . . . . . . . . . . . .
27 1999–2000 . . . . . . . . . . . . . . . . . . . . . .
30 2000–2001 . . . . . . . . . . . . . . . . . . . . . .
34 2001–2002 . . . . . . . . . . . . . . . . . . . . . .
38 2002–2003 . . . . . . . . . . . . . . . . . . . . . .
42 2003–2004 . . . . . . . . . . . . . . . . . . . . . .
45 2004–2005 . . . . . . . . . . . . . . . . . . . . . .
49 2005–2006 . . . . . . . . . . . . . . . . . . . . . Заключительный этап олимпиады . . . . . . . . . . . . . . . . . . . . . .
56 1993–1994 . . . . . . . . . . . . . . . . . . . . . .
58 1994–1995 . . . . . . . . . . . . . . . . . . . . . .
62 1995–1996 . . . . . . . . . . . . . . . . . . . . . .
64 1996–1997 . . . . . . . . . . . . . . . . . . . . . .
67 1997–1998 . . . . . . . . . . . . . . . . . . . . . .
71 1998–1999 . . . . . . . . . . . . . . . . . . . . . .
74 1999–2000 . . . . . . . . . . . . . . . . . . . . . .
77 2000–2001 . . . . . . . . . . . . . . . . . . . . . .
80 2001–2002 . . . . . . . . . . . . . . . . . . . . . .
83 2002–2003 . . . . . . . . . . . . . . . . . . . . . .
86 2003–2004 . . . . . . . . . . . . . . . . . . . . . .
89 2004–2005 . . . . . . . . . . . . . . . . . . . . . .
92 2005–2006 . . . . . . . . . . . . . . . . . . . . . РЕШЕНИЯ ЗАДАЧ
Окружной этап олимпиады . . . . . . . . . . . . . . . . . . . . . .
99
467 1993–1994 . . . . . . . . . . . . . . . . . . . . . . 111 1994–1995 . . . . . . . . . . . . . . . . . . . . . . 120 1995–1996 . . . . . . . . . . . . . . . . . . . . . . 131 1996–1997 . . . . . . . . . . . . . . . . . . . . . . 143 1997–1998 . . . . . . . . . . . . . . . . . . . . . . 150 1998–1999 . . . . . . . . . . . . . . . . . . . . . . 163 1999–2000 . . . . . . . . . . . . . . . . . . . . . . 173 2000–2001 . . . . . . . . . . . . . . . . . . . . . . 187 2001–2002 . . . . . . . . . . . . . . . . . . . . . . 201 2002–2003 . . . . . . . . . . . . . . . . . . . . . . 216 2003–2004 . . . . . . . . . . . . . . . . . . . . . . 229 2004–2005 . . . . . . . . . . . . . . . . . . . . . . 241 2005–2006 . . . . . . . . . . . . . . . . . . . . . . Заключительный этап олимпиады . . . . . . . . . . . . . . . . . . . . . . 267 1993–1994 . . . . . . . . . . . . . . . . . . . . . . 280 1994–1995 . . . . . . . . . . . . . . . . . . . . . . 293 1995–1996 . . . . . . . . . . . . . . . . . . . . . . 305 1996–1997 . . . . . . . . . . . . . . . . . . . . . . 320 1997–1998 . . . . . . . . . . . . . . . . . . . . . . 333 1998–1999 . . . . . . . . . . . . . . . . . . . . . . 347 1999–2000 . . . . . . . . . . . . . . . . . . . . . . 360 2000–2001 . . . . . . . . . . . . . . . . . . . . . . 370 2001–2002 . . . . . . . . . . . . . . . . . . . . . . 382 2002–2003 . . . . . . . . . . . . . . . . . . . . . . 394 2003–2004 . . . . . . . . . . . . . . . . . . . . . . 408 2004–2005 . . . . . . . . . . . . . . . . . . . . . . 421 2005–2006 . . . . . . . . . . . . . . . . . . . . . . Ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . Авторы задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Тематический рубрикатор . . . . . . . . . . . . . . . . . . . . . . 455
Агаханов Назар Хангельдыевич
Богданов Илья Игоревич
Кожевников Павел Александрович
Подлипский Олег Константинович
Терешин Дмитрий Александрович
ВСЕРОССИЙСКИЕ ОЛИМПИАДЫ ШКОЛЬНИКОВ
ПО МАТЕМАТИКЕ
1993–2006
ОКРУЖНОЙ И ФИНАЛЬНЫЙ ЭТАПЫ
Редактор ФИ. Кизнер
Оригинал-макет изготовлен А. В. Полозовым
Обложка АР. Сафарова
Оригинал-макет предоставлен авторами
Подписано в печать г. Формат 60 × 90 1
/
16
. Бумага офсетная № 1.
Печатьофсетная. Печ. л. 29,5. Заказ Издательство Московского центра непрерывного математического образования, Москва, Большой Власьевский пер, 11. Тел. Отпечатано с готовых диапозитивов в ППП Типография Наука, Москва, Шубинский пер, 6.
Задачи о клетчатых досках, таблицах, решетках, 159, 176, 181, 216, 220, 255, 266, 288, 292, 352, 384, 402, 424,
431, 439, 523, 528, 540, 568, 580, 598, 641, 645, 671, 680, 689, 708, В некоторых задачах используются вспомогательные раскраски, 63, 124, 152, 282, 332, 504, 573, 737.
Графы
Задачи огородах и дорогах, авиалиниях, турнирах зачастую являются переформулировкой вопросов из теории графов.
Граф (или граф без петель и кратных ребер) задается конечным множеством — множеством вершин графа, и множеством неупорядоченных пар вершин — ребер графа. Вершины графа удобно изображатьточ- ками, а ребра — линиями, соединяющими соответствующие пары вершин.
Вершины, соединенные ребром, называются соседними или смежными. Количество вершин, смежных с вершиной A, называется степенью
вершины A; вершина степени 1 называется висячей. В любом графе число вершин нечетной степени четно.
Путь — это последовательность ребер A
1
A
2
, A
2
A
3
, . . . , здесь BC — ребро, соединяющее вершины B и C); вершины и называются соответственно началом и концом пути. Путьпо ребрам A
1
A
2
,
A
2
A
3
, . . . , называется циклом, если A
1
= A
n
; цикл называется
простым, если вершины A
1
, A
2
, . . . , A
n−1
различны.
Компонентой связности вершины A называется множество вершин, включающее A и все вершины X, для которых существует путьс началом A и концом X. Компоненты связности различных вершин либо не пересекаются, либо совпадают, поэтому множество вершин графа разбивается на несколько попарно не пересекающихся компонент связности;
если компонента всего одна, то граф называется связным.
Теорема Эйлера утверждает, что в связном графе. существует цикл, содержащий каждое ребро ровно по разу, тогда и только тогда, когда степени всех вершин четны. существует путь, содержащий каждое ребро ровно по разу, тогда и только тогда, когда степени всех вершин, кроме возможно двух, четны.
Связный граф, в котором нет циклов, называется деревом. Количество ребер в дереве с n вершинами равно n − Если на каждом ребре графа задано направление, то граф называется
ориентированным.
Задачи о связности и компонентах связности, 159, 255, 356, 564, 570, 628, 644, Задачи о путях по ребрам графа, обходах ребер и вершин графа
ТЕМАТИЧЕСКИЙ РУБРИКАТОР, 24, 63, 176, 596, 652, 669, Покраска вершин или ребер графа, разные задачи о графах, 64, 224, 232, 584, 639, 660, 675, 694, 711, 728, 760.
Игры
В некоторых играх возможные ходы соперников разбиваются на пары.
Один из игроков может выигрывать, отвечая парным ходом. В частности,
к этому типу относятся игры, допускающие симметричную стратегию за одного из соперников, 84, 156, 175, 204, 236, 371, 576, 592, В различных играх возможно определитьвыигрышные ситуации для каждого из игроков. Чтобы это сделать, полезно анализировать игру с конца. В небольшом количестве задач предположение о существовании выигрышной стратегии у одного из игроков иногда можно опровергнуть
(путем так называемой передачи хода. В таком случае наличие выигрышной стратегии можно обосноватьбез явного ее предъявления. Разные игры, 16, 21, 114, 150, 242, 267, 294, 299, 308, 356, 362, 432, 451, 472,
577, 743.
Конструктивы
Задачи на отыскание алгоритмов и стратегий, 160, 172, 244, 296, 344, 510, 512, 524, 538, 544, 548, 572, 594,
646, 691, 698, 716, 720, 723, Отдельно выделим задачи на взвешивания, 205, 214, 218, 272, Разные задачи на придумывание интересных конструкций, 33, 60, 77, 144, 231, 301, 353, 368, 376, 447, 476, 506.
Игры
В некоторых играх возможные ходы соперников разбиваются на пары.
Один из игроков может выигрывать, отвечая парным ходом. В частности,
к этому типу относятся игры, допускающие симметричную стратегию за одного из соперников, 84, 156, 175, 204, 236, 371, 576, 592, В различных играх возможно определитьвыигрышные ситуации для каждого из игроков. Чтобы это сделать, полезно анализировать игру с конца. В небольшом количестве задач предположение о существовании выигрышной стратегии у одного из игроков иногда можно опровергнуть
(путем так называемой передачи хода. В таком случае наличие выигрышной стратегии можно обосноватьбез явного ее предъявления. Разные игры, 16, 21, 114, 150, 242, 267, 294, 299, 308, 356, 362, 432, 451, 472,
577, 743.
Конструктивы
Задачи на отыскание алгоритмов и стратегий, 160, 172, 244, 296, 344, 510, 512, 524, 538, 544, 548, 572, 594,
646, 691, 698, 716, 720, 723, Отдельно выделим задачи на взвешивания, 205, 214, 218, 272, Разные задачи на придумывание интересных конструкций, 33, 60, 77, 144, 231, 301, 353, 368, 376, 447, 476, 506.
466
С
ОДЕРЖАНИЕ
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Принятые обозначения . . . . . . . . . . . . . . . . . . . . . . . УСЛОВИЯ ЗАДАЧ
Окружной этап олимпиады . . . . . . . . . . . . . . . . . . . . . .
7 1993–1994 . . . . . . . . . . . . . . . . . . . . . .
10 1994–1995 . . . . . . . . . . . . . . . . . . . . . .
13 1995–1996 . . . . . . . . . . . . . . . . . . . . . .
16 1996–1997 . . . . . . . . . . . . . . . . . . . . . .
19 1997–1998 . . . . . . . . . . . . . . . . . . . . . .
23 1998–1999 . . . . . . . . . . . . . . . . . . . . . .
27 1999–2000 . . . . . . . . . . . . . . . . . . . . . .
30 2000–2001 . . . . . . . . . . . . . . . . . . . . . .
34 2001–2002 . . . . . . . . . . . . . . . . . . . . . .
38 2002–2003 . . . . . . . . . . . . . . . . . . . . . .
42 2003–2004 . . . . . . . . . . . . . . . . . . . . . .
45 2004–2005 . . . . . . . . . . . . . . . . . . . . . .
49 2005–2006 . . . . . . . . . . . . . . . . . . . . . Заключительный этап олимпиады . . . . . . . . . . . . . . . . . . . . . .
56 1993–1994 . . . . . . . . . . . . . . . . . . . . . .
58 1994–1995 . . . . . . . . . . . . . . . . . . . . . .
62 1995–1996 . . . . . . . . . . . . . . . . . . . . . .
64 1996–1997 . . . . . . . . . . . . . . . . . . . . . .
67 1997–1998 . . . . . . . . . . . . . . . . . . . . . .
71 1998–1999 . . . . . . . . . . . . . . . . . . . . . .
74 1999–2000 . . . . . . . . . . . . . . . . . . . . . .
77 2000–2001 . . . . . . . . . . . . . . . . . . . . . .
80 2001–2002 . . . . . . . . . . . . . . . . . . . . . .
83 2002–2003 . . . . . . . . . . . . . . . . . . . . . .
86 2003–2004 . . . . . . . . . . . . . . . . . . . . . .
89 2004–2005 . . . . . . . . . . . . . . . . . . . . . .
92 2005–2006 . . . . . . . . . . . . . . . . . . . . . РЕШЕНИЯ ЗАДАЧ
Окружной этап олимпиады . . . . . . . . . . . . . . . . . . . . . .
99
467 1993–1994 . . . . . . . . . . . . . . . . . . . . . . 111 1994–1995 . . . . . . . . . . . . . . . . . . . . . . 120 1995–1996 . . . . . . . . . . . . . . . . . . . . . . 131 1996–1997 . . . . . . . . . . . . . . . . . . . . . . 143 1997–1998 . . . . . . . . . . . . . . . . . . . . . . 150 1998–1999 . . . . . . . . . . . . . . . . . . . . . . 163 1999–2000 . . . . . . . . . . . . . . . . . . . . . . 173 2000–2001 . . . . . . . . . . . . . . . . . . . . . . 187 2001–2002 . . . . . . . . . . . . . . . . . . . . . . 201 2002–2003 . . . . . . . . . . . . . . . . . . . . . . 216 2003–2004 . . . . . . . . . . . . . . . . . . . . . . 229 2004–2005 . . . . . . . . . . . . . . . . . . . . . . 241 2005–2006 . . . . . . . . . . . . . . . . . . . . . . Заключительный этап олимпиады . . . . . . . . . . . . . . . . . . . . . . 267 1993–1994 . . . . . . . . . . . . . . . . . . . . . . 280 1994–1995 . . . . . . . . . . . . . . . . . . . . . . 293 1995–1996 . . . . . . . . . . . . . . . . . . . . . . 305 1996–1997 . . . . . . . . . . . . . . . . . . . . . . 320 1997–1998 . . . . . . . . . . . . . . . . . . . . . . 333 1998–1999 . . . . . . . . . . . . . . . . . . . . . . 347 1999–2000 . . . . . . . . . . . . . . . . . . . . . . 360 2000–2001 . . . . . . . . . . . . . . . . . . . . . . 370 2001–2002 . . . . . . . . . . . . . . . . . . . . . . 382 2002–2003 . . . . . . . . . . . . . . . . . . . . . . 394 2003–2004 . . . . . . . . . . . . . . . . . . . . . . 408 2004–2005 . . . . . . . . . . . . . . . . . . . . . . 421 2005–2006 . . . . . . . . . . . . . . . . . . . . . . Ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . Авторы задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Тематический рубрикатор . . . . . . . . . . . . . . . . . . . . . . 455
Агаханов Назар Хангельдыевич
Богданов Илья Игоревич
Кожевников Павел Александрович
Подлипский Олег Константинович
Терешин Дмитрий Александрович
ВСЕРОССИЙСКИЕ ОЛИМПИАДЫ ШКОЛЬНИКОВ
ПО МАТЕМАТИКЕ
1993–2006
ОКРУЖНОЙ И ФИНАЛЬНЫЙ ЭТАПЫ
Редактор ФИ. Кизнер
Оригинал-макет изготовлен А. В. Полозовым
Обложка АР. Сафарова
Оригинал-макет предоставлен авторами
Подписано в печать г. Формат 60 × 90 1
/
16
. Бумага офсетная № 1.
Печатьофсетная. Печ. л. 29,5. Заказ Издательство Московского центра непрерывного математического образования, Москва, Большой Власьевский пер, 11. Тел. Отпечатано с готовых диапозитивов в ППП Типография Наука, Москва, Шубинский пер, 6.
1 ... 56 57 58 59 60 61 62 63 64
