Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
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, будем удалятьтакие ребра. Пустьтаких ребер больше нет УЧЕБНЫЙ ГОД, 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. ОТВЕТЫ. 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. Две ∗) Приведены ответы ко всем задачам кроме тех, в которых требуется доказатьутвержде- ние. О ТВЕТЫ 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. Выигрывает первый СПИСОК ЛИТЕРАТУРЫ 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 с Яковлев Г.Н., Купцов Л.П., Резниченко СВ, Гусятников П.Б. Всероссийские математические олимпиады школьников. – М Просвещение с Приложение АВТОРЫ ЗАДАЧ Курсивом помечены задачи, написанные в соавторстве С. Августинович (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 АВТОРЫ ЗАДАЧ |