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