Олімпіади

Готуємось до олімпіад з математики

Перелік сайтів та умови задач математичних олімпіад різних рівнів

Типи олімпіадних задач з математики

Олімпіадні задачі в математиці - термін для позначення кола задач, для вирішення яких обов'язково потрібно несподіваний і оригінальний підхід.Олімпіадні задачі отримали свою назву від популярних змагань школярів і студентів, так званих математичних олімпіад. Мета створення задач цієї категорії - виховання в майбутніх математиків таких якостей як творчий підхід, нетривіальне мислення та вміння вивчити проблему з різних сторін. Не випадково академік А. Н. Колмогоров у своїй промові на відкритті порівняв роботу математика з «низкою розв'язання (часом великих і важких) олімпіадних задач».Зовнішня простота олімпіадних задач – їх умови і розв'язання повинні бути зрозумілі будь-якому школяру - оманлива. Кращі олімпіадні задачі зачіпають глибокі проблеми з самих різних областей математики . Іноді цією уявною простотою користувалися не за призначенням: у часи СРСР на приймальних іспитах у ВНЗ  за допомогою таких завдань відсівали абітурієнтів небажаних національностей. Не дивно, що олімпіадні задачі з арсеналу таких приймальних комісій стали називати «гробами».Рішення олімпіадних задач може зажадати істотної кількості часу навіть від сильного (але нетренованих на їх розв'язання) професійного математика.Олімпіадні задачі можна знайти в Інтернеті, в періодичних виданнях (журнали Квант , Математическоее просвещение ), а також у вигляді окремих збірок. Вони широко використовуються в роботі математичних гуртків, заочних шкіл і для таких математичних змагань як олімпіади, турніри міст і математичні бої .Великий внесок у популяризацію методів вирішення олімпіадних завдань внесли публікації журналу «Квант», книги серій « Популярні лекції з математики »,« Бібліотека математичного гуртка » , Збірники олімпіадних завдань, що випускалися видавництвами « Наука »,« Просвещение », перекладені - видавництвом« Мир », і інші книги, а також численні веб-сайти, присвячені олімпіадних задачах.Завдання олімпіадного типу, відома з часів Евкліда , наприклад:Довести, що існує нескінченно багато простих чисел .Задача розв'язується методом від супротивного . Припустивши, що простих чисел скінченне число N, розглядаємо число, наступне за їх добутком   SHAPE  \* MERGEFORMAT  . Очевидно, що воно не ділиться ні на одне з використаних у добутку простих чисел, даючи в залишку 1. Значить, або воно саме просте, або воно ділиться на просте число, не враховане в нашому (імовірно повному) списку. У квсякому разі, простих чисел, принаймні, N+1. Протиріччя з припущенням про скінченність.[37]Незважаючи на унікальність олімпіадних завдань, можна все-таки виділити кілька типових ідей, які складають  суть задач.  Зрозуміло, за визначенням, такий список буде неповним.·        Задачі на інваріант·        Задача – гра·        Комбінаторика·        Теорія графів·        Геометрія  Не існує єдиного методу розв’язання  олімпіадних задач.  Навпаки, кількість методів постійно поповнюється. Деякі зазачі можна розв`язати   кількома різними методами або комбінацією методів. Характерна особливість олімпіадних задач в тому, що розв’язання  з вигляду нескладної проблеми може зажадати застосування методів, що використовуються в серйозних математичних дослідженнях. Нижче наводиться (за визначенням) неповний список методів розв’язання олімпіадних задач:·        Доведення выд супротивного·        Принцип Діріхле·        Метод розмальовки·        Контр приклад·        Математична індукція·        Рекурсія·        Метод додаткової побудови·        Метод Гауса1.1. ІнваріантУ цьому розділі розглянемо одне, але дуже важливе математичне поняття - інваріант. Буває воно в задачах, де ми маємо справу з якимись операціями, з якимось процесом, який змінює даний в умові об'єкт. От якщо у об'єкта є якась властивість або характеристика, яка не змінюється при цих операціях - вона і називається інваріантом. Якщо у об'єкта є два стани, при яких інваріант приймає різні значення, то з одного з них не можна перейти в інший (і з другого в перше теж). Але однакове значення інваріанта ще не означає, що так перейти можна. Задача 1.1. У файлі зберігаються 2003 одиниці і 232 нуля. Програма читає з файлу два довільних числа, видаляє, і записує на їх місце 0, якщо вони були рівні, і 1, якщо ні. Програма запускається багаторазово. Наприкінці у файлі залишається тільки одне число. Чому воно дорівнює, 0 або 1?Розв’язання: Незважаючи на те, що варіантів дії програми дуже багато, ми можемо встановити відповідь однозначно. Що може прочитати програма за кажний окремий  запуск? Або 0 і 0 (і записати 0), або 0 і 1 (і записати 1), або 1 і 1 (і записати 0). У перших двох випадках сума всіх чисел у файлі не змінюється, в останньому - зменшується на 2. У кожному разі, парність цієї суми залишається колишньою. Початково сума була      2003 * 1 +232 * 0 = 2003 - непарна, значить, і в кінці буде непарна. Але наприкінці залишається тільки одне число - воно і дорівнює сумі всіх - тому воно непарне. А так як у файлі бувають тільки нулі й одиниці, то це 1.Задача 1.2. Є три числа, які можна замінювати за такими правилами: числа a, b і c стираються і замість них записуються (a + b) / 2, (b + c) / 2 і (a + c) / 2.Можно Чи з чисел 101, 73, 125 отримати 77, 79 і 83?Розв’язання: А давайте так, "про всяк випадок", подивимося, як міняється сума чисел. Було a + b + c, а стало ... замість них записуються (a + b) / 2 + (b + c) / 2 + (a + c) / 2 = (2a +2 b +2 c) / 2 = a + b + c - не змінилася. Тобто, як не крути, а сума трьох чисел не змінюється. Але 101 +73 +125 = 299, а 77 +79 +83 = 239 - суми вихідної та кінцевої трійки різні. Тому з однієї не можна отримати іншу.(!) А ті, хто захоче взяти в якості інваріанта парність суми або її залишок по якомусь модулю, швидше за все, помиляться, так як початкова та кінцева суми розрізняються на 60, а дільників у 60 ох як багато.Задача 1.3. Знову є три числа, які можна замінювати вже за іншими правилами: a, b і c - на ab/c, ac/b і bc/a. Чи можна з 5, 17/6 і 3/5 отримати 16/5, 9/4 та 7/6?Розв’язання: Ну, про те, куди тут переходить сума чисел, навіть думати не хочеться. Що ще буває, крім суми? Добуток, наприклад. Перед операцією добуток  чисел - abc, а після: (ab/c) * (ac/b) * (bc/a) = a2b2c2/abc=abc - не змінилося!З начить, добуток трьох чисел залишається постійним при всіх операціях. Але на початку воно було рівним 5*(17/6)*(3/5)= 8,5, а наприкінці (16/5)*(9/4)*(7/6) = 8,4 - не рівні. Тому відповідь "не можна".(!) Якщо у нас є якийсь набір чисел, над яким здійснюються операції, то завжди варто перевірити, як змінюються при цих операціях сума і добуток всіх чисел. Дуже часто вони самі або їхні залишки по якомусь модулю є інваріантом, за допомогою якого розв’язується завдання.Зауваження. У завданнях, де питається "чи можна" за допомогою інваріанта можна доводити тільки відповідь "не можна"! Якщо придуманий вами інваріант нічому не суперечить (його значення на початку і наприкінці передбачуваної послідовності операцій не зміниться), то це не означає, що відповідь "можна". По-перше, зазвичай це означає, що придуманий поганий інваріант. По-друге, відповідь "можна" доводиться пред'явленням конкретного прикладу і ніяк інакше.Інваріант як характеристика нечислових об'єктів. У всіх попередніх прикладах в задачі фігурували числа, від яких ми в якості інваріанта брали якусь функцію. Але, звичайно, у початковому формулюванні може не бути ніяких чисел! Що тоді робити? Звичайно, ці числа придумати.Задача 1.4. У мові програмування MustDie всього дві команди, для стислості званих M і D. Через збій в компіляторі, дія програми не зміниться, якщо з неї викинути шматок коду MDDM, а також якщо в будь-яке її місце вставити шматок коду DMMDMD або MDMD. Чи можуть програми MMDMD і DMMDD виконуватися однаково?Розв’язанная: Наше кажучи: чи існує таке рівнозначне перетворення коду, яке переводить одну програму в іншу? Ні, звичайно, і ви вже здогадалися що інваріант тільки треба придумати. В одному шматку 2 команди M 2 команди D, у другому тих і інших по 3, у третьому - знову по 2. Здається, ясно: у будь-якому вставленомк або видаленому шматку команд M і D порівну. Значить не змінюється, правильно, різниця між числом тих і інших команд. Вона буде нашим інваріантом - і дуже добре, так як в одній програмі на одну більше команд M, а в інший на одну більше команд D (значення різниці помінялося в 1 на -1).Вправа 1.1. Доведіть, що всі білки можуть зібратися на одній ялинки тоді і тільки тоді, коли їх непарне число. (Тобто, для парних чисел узагальнити дане вище рішення, для непарних - придумати приклад.)(!) Різниця якихось кількостей і набір попарних різниць - теж типові інваріанти. Після суми і твори наступним справою треба перевіряти саме різниці.Розв’язання: Де ж шукати інваріант? Із сумою чисел у файлі якось складно, тому що третя програма змінює її чорт знає як. В тому сенсі, що знаючи суми чисел у двох вхідних файлах ми не можемо визначити суму чисел у вихідному файлі. Зрізницею чисел у файлі все краще: перша програма не змінює різницю ((X+1)-(Y +1) =XY), друга -ділить її на 2 (X/2-Y/2 = (XY) / 2) , а третя - складає різниці (XZ = (XY) + (YZ)). Що ж не змінюється при всіх цих перетвореннях - так відразу і не збагнеш ...Поставимо ескперімент (так, математика - наука експериментальна!).Вихідний файл (5, 19) можна пропустити тільки через першу програму і отримати файл (6, 20). З нього можна далі робити послідовність (7, 21), (8, 22) і т.д., а можна запустити другу програму і отримати файл (3, 10). З нього можна зробити послідовність (4, 11), (5, 12) ... (19, 26). Потім можна запустити третю програму на (5, 19) і (19, 26) і отримати файл (5, 26) ...Порахуємо різниці: 5-19 = -14 = 6-20 = 7-21 = 8-22 = ...; 3-10 = -7 = 4-11 = 5-12 = ... = 19-26; 5-26 = -21. Що ж спільного у чисел -14, -7, -21? Звичайно, вони всі на 7 діляться. От нехай ця подільність і буде інваріантом.Дійсно, коли різниця не змінюється, то й подільність збережеться; коли різниця ділиться на 2, то подільність на 7 не зникне (2 і 7 взаємно прості); а коли різниці, що діляться на 7, складаються, то сума теж ділиться на 7.Зрозуміло, що, маючи на початку файл з різницю чисел, що ділиться на 7, ми тільки такі різниці і будемо отримувати. Але різниця 1-2004 = -2003 на 7 не ділиться, і такий файл ми отримати не зможемо.Вправа 1.2. Доведіть, що тут можна отримати всі ті і тільки ті файли, де перше число менше другого, а їх різниця ділиться на 7.Глибокий сенс тут у чому: інваріант може залежати не тільки від правил, за якими проводяться перетворення, але і від початкових даних. Як тут: значення різниці за модулем 7, взагалі кажучи - не інваріант при вироблених перетвореннях. Але при конкретних початкових умовах, коли це значення з самого початку дорівнює 0 - тоді воно стає інваріантом.Безумовно, якщо типові інваріанти (сума, добуток, різниці та їх значення за якимось,зразу помітним, модулем) не підходять, то корисно поставити експеримент: проробити кілька перетворень і пошукати деякі закономірності в тому, що при цьому буде виходити.Виділення зазначеної частини. Нерідко допомагає інваріант, який приймають за характеристику не всього об'єкта, а тільки його окремої частини. Придумується вона щоразу по своєму. Якась загальна логіка: ця частина повинна бутирегулярною за своїм устроєм і містити всі нерегулярності для початкового або кінцевого стану. Взагалі, може підійти всяка частина, на якій перетворення загального вигляду буде виглядати більш просто.Задача 1.5. На дошці 3x5 всі клітини білі, а один кут чорний. За хід можна поміняти колір всіх клітин в одному рядку або стовпці. Чи можна всі клітини зробити білими?Розв’язання: Парність числа чорних клітин на всій дошці, на жаль, змінюється дуже часто, а тому нам не допоможе. Де б знайти таку частину дошки, на якій ця парність незмінна? У нас тут в умові нерегулярність в кутку - так візьмемо 4 кута. При операції перефарбування змінює колір рівно два кути, або жоден - тобто парність числа чорних кутів - інваріант. Але на початку такий кут один, а наприкінці хочеться нуль - не можна.Задача 1.6. На колі стоїть 12 точок, в одній написано -1, в інших +1. Можна змінити знак у трьох одиниць підряд. Чи можна здвинути єдину -1 до сусідньої вершину?Розв’язання: Нехай, для визначеності, ми зрушили -1 до сусідньої проти годинникової стрілки вершину (інакше можна всю картинку дзеркально відобразити і отримати саме таку). Давайте занумеруем вершини, починаючи з вихідної -1, вже за годинниковою стрілкою (тоді те місце, куди зрушила -1 - це вершина 12). Давайте виділимо таку частину (безліч вершин), де є перша вершина, немає 12-й, а парність кількості-1 - інваріант (тоді ця кількість в даній частині треба буде змінити з 1 до 0, а це неможливо з- за парності).Інваріант і розмальовки дощок у клітинку. Дуже важливий клас задач на інваріант - якісь перетворення на кліткових дошках. Або ми ходимо чим-небудь по дошці, або заставляємо дошку фігурами. У будь-якому разі, дуже корисною може бути розмальовка дошки в два або більше кольорів, що володіє якимись особливими властивостями. Найбільш поширені розмальовки:- Шахова (два кольори чергуються так, що будь-які дві сусідні по стороні клітини - різних кольорів);- "матрас" (чередування строк, викрашенних у два кольори - або стовбців);- "Матрац" (чергування рядків, пофарбованих у два кольори - або стовпців);- Збільшена шахова (у шаховому порядку фарбуються не окремі клітини, а цілі блоки 2x2, 3x3 і т.д.);- Збільшений"матрац" (чергуються не рядки, а однакові по товщині блоки з рядків);- "Матрац" в N кольорів: чергуються рядки, пофарбовані у кольори, 1-й, 2-й, ... N-й, 1-й, 2-й і т.д.- Шахова в N кольорів - легше показати, ніж написати; приклад для 3-х кольорів; можна і по-іншому, щоб одноколірні діагоналі були нахилені в інший бік. Звичайний інваріант - колір клітин, по яких ми ходимо (або якесь чергування кольорів, або якісь кольору, на які ми ніколи не потрапляємо ...), або кількості клітин тих і інших кольорів на всій дошці і в фігурах замощення (якщо не збігаються, то замостити не можнаЗадача 1.7. Доведіть, що шахову дошку не можна замостити 15-тима прямоугольничками 1x4 і однієї фігуркою виду  .Розв’язання: Шахова розмальовка тут не допоможе. Вона, так скажемо, не відрізняє особливу фігурку від прямокутничка: і в ній і в них рівно 2 білих і 2 чорних клітини. І ніщо не суперечить тому, що дошку можна замостити 16-ю фігурами з такою властивістю. Спробуємо іншу розмальовку, скажімо, "матрац". Тоді в прямокутнички 1x4 чи то 0, то 2, чи то 4 чорні клітини (дивлячись як він лежить). А в особливій фігурці - чи то 1, чи то 3. Коротше, там-парне, тут - непарне. А сума 15 парних чисел і одного непарного непарна і не може тому бути дорівнює 32 (числу чорних клітин на шаховій дошці).Власне, інваріантом тут можна назвати парність кількості чорних клітин. Тільки ми тут не перетворимо об'єкт або набір об'єктів, а складаємо один об'єкт (дошку) з інших.Задача 1.8. Фішка ходить по дошці NxN, зрушуючи на 1 клітину вгору, вправо або вниз-вліво по діагоналі. Чи може фішка обійти всі клітини дошки по разу і закінчити шлях зверху від початкової клітини.Розв'язання : Підберемо розмальовку, при якій фішка буде однаково міняти колір при будь-якому ході. Просто шахова і "матрац" не підійдуть. А зате шахова розмальовка в 3 кольори - просто чудово Наша фішка буде ходити з червоного на жовтий, з жовтого на зелений, з зеленого на червоний і т.д. Нехай, скажімо, початкова клітина червона - тоді кінцева буде жовта. Кольори чергуються по циклу довжини 3, тому число ходів: 3k +1 (тобто = 1 по mod 3). Але те ж число ходів на дошці NxN одно N2 -1. Звідси N 2 = 2 (mod 3), чого, з міркувань теорії чисел не буває. Відповідь "не можна".(!) Інваріант інваріантом, але і про інші галузі математики по ходу справи не треба забувати. Часто рішення може прийти саме звідти.Треба акуратно підходите до завдань про різні процеси з питанням "чи можна". Так, більша частина з них - з відповіддю "не можна", який доводиться через інваріант. Але трапляються іноді завдання з відповіддю "можна", де треба будувати приклад. Іноді, захопившись пошуком інваріанта, можна не помітити існування простого прикладу. 1.2. ІгриЗадачі про ігри - вельми популярний вид олімпіадних завдань, особливо в молодших класах. Найбільш загальна проблема у початківців - зрозуміти, "що взагалі від нас хочуть", які міркування є правильним рішенням завдання, а які - ні.Звичайно передбачається що грають двоє, роблячи ходи по черзі (пропускати свій хід не можна!), А в задачі запитують "хто виграє при правильній грі?" Стандартна помилка по суті - розуміти слова "при правильній грі" так, як ніби обидва супротивники грають оптимальним для себе чином (тим більше, що розв’язуючий  задачу часто неправильно розуміє, що таке "оптимальним чином"!). Тоді придумується виграшна стратегія, яка дає відповідь тільки на оптимальний хід супротивника (зазвичай ще "оптимальним" вважається такий хід, коли супротивник слід придуманої нами ж стратегії - хоча для іншого гравця така стратегія може бути, навпаки, зовсім нікчемною!). Насправді, треба вміти придумувати відповідь на будь-який хід противника, яким би ідіотським він нам не здавався. Зазвичай правильна стратегія, на відміну від неправильної, не має випадків різної складності, а з однаковою легкістю знаходить гідну відповідь на будь-який хід!Ігри-жарти. Найперший і простий клас ігор - ігри-жарти, в яких, насправді, немає ніякої стратегії (а нас хочуть обдурити, що вона нібито є!). Просто як би хто не ходив, або завжди виграє перший гравець (той, хто починає гру), або завжди другий. Задача - в тому, щоб математично довести таку закономірність (а помітити її можна, зігравши самому з собою рази 3-4). Для доказу зазвичай знаходиться якась величина, яка зрозуміло чому дорівнює на початку і кінці і зрозуміло як змінюється на кожному ходу - тут навіть часто число ходів до кінця однозначно порахувати можна. Або якийсь інваріант (тобто щось, що не міняють ні за якого ходу), однозначно залежить від початкової позиції (найчастіше - від парності) і визначальний вигравшого у кінці.Задача 2.1. Двоє по черзі ламають шоколадку 5x8. За хід можна розламати будь-який шматок по прямій лінії між часточками. Програє той, хто не може зробити хід (І це  стандартна  умова, що ми її будемо мати на увазі, якщо не сказано протилежне. Питання "хто виграє при правильній грі?")Розв'язання: Що значить, що гра закінчилася? Звичайно, що шоколадка вже вся розламані на окремі часточки. Часточок завжди буде 5x8 = 40 штук, а шоколадка на початку була одна. Зауважимо, що на кожному ходу один шматок шоколадки завжди розламується на 2, тобто кількість різних шматків шоколадки збільшується на 1. На початку ця кількість дорівнює 1, а в кінці, як ми помітили, 40. Значить, гра тривала рівно 39 ходів ("ходом" ми називаємо хід одного гравця, а не пару "хід - хід"). Тому останній (39-й) хід був обов'язково ходом першого (його ходи - перший, третій і всі з непарними номерами) - і перший виграв.Ось такий вийшов жарт - як не ходи, перший завжди виграє.Задача 2.2. На дошці написані 10 нулів і 10 одиниць. За хід можна стерти дві будь-які цифри і написати замість них 0, якщо вони були однакові або 1, якщо вони були різні. Якщо на дошці залишається 1 - виграє перший. Якщо 0 - другий.Розв'язання : Ну, оскільки число цифр з кожним ходом зменшується рівно на 1 (2 стираємо, одну пишемо), а на початку їх 20 і в кінці повинна залишитися одна, то гра буде продовжуватися рівно 19 ходів. Останнім ходом буде хід  першого , тільки в цьому завданні не факт, що перший тоді виграє.Виграш залежить від парності останнього числа, звернемо на це увагу. Такий стандартний інваріант, як парність суми всіх чисел, не змінюється при ходах. Дійсно, сума двох однакових цифр - парна і, віднімаючи її, ми додаємо парний нуль. А сума двох різних цифр - непарна (0 +1 = 1), і ми додаємо замість неї непарну одиницю. Початкова сума всіх чисел парна, тому що серед них парне число непарних – одиниць, тому і в кінці буде парна. А це означає, що останнє число, що залишилося в кінці гри, буде парне, тобто воно буде нулем - і виграє другий.Заодно ми переконалися, що не в будь-якій грі той, хто робить останній хід, виграє: можна змусити (як воно тут і відбувається) суперника зробити хід, після якого він програє.Ідея "ідіотських ходів":Задача 2.3. На дошці 10x12 можна за хід викреслити одну лінію (горизонталь або вертикаль, тобто рядок або стовпець) якщо в ній ще є одна невикреслена клітина.Розв’язання : (Так, програє той, хто не може зробити хід - якщо хто не зрозумів.) Давайте  злегка переформулюємо задачу інакше: нехай лінія не викреслюється, а вирізається з дошки зі склеюванням країв розрізу. Тоді правило зміниться на - "можна вирізати будь-яку існуючу лінію" і гра закінчується, коли від дошки нічого не залишається.Нехай раптом після свого ходу залишили, скажімо, дошку з одним рядком. Звичайно, своїм ходом суперник може вирізати цей рядок - і ми програємо. Тому такий хід був «ідіотським» - давайте так його і називати. Подивимося, коли не можна буде не зробити «ідіотського»  ходу. Якщо дошка 1xN (або Nx1) - то такий хід уже зробив супротивник. Якщо ширина і висота дошки не менше 2, а більша з них - не менше 3 - то виріжемо лінію поперек більшої розмірності - і залишиться дошка хоча б 2x2. А от якщо перед ходом дошка - 2x2, то хід обов'язково буде «ідіотський». Ясно, що виграє той, хто залишить противнику дошку 2x2. На кожному ходу висота або ширина дошки зменшується на 1 (тобто, їх сума зменшується на 1). Початково ця сума дорівнює 10 +12 = 22, в кінці повинна стати 2 +2 = 4. Різниця 22-4 = 18 - парне число ходів, тому дошка 2x2 залишиться після ходу другого - і другий виграє (як у звичайній грі-жарті!).[42]Строго кажучи: стратегія другого - грати як завгодно, тільки не роблячи «ідіотських» ходів. Якщо перший десь зробить «ідіотський» хід (а це формально заважає загнати його на дошку 2x2) - наступним ходом виграємо. Якщо ніхто не зробить «ідіотського» ходу - то після 18 ходів у першого буде дошка 2x2 - і тут він все одно зробить «ідіотський» хід.Симетрія. Це  потужний красивим, але дуже простий методом розв’язання  ігрових завдань - симетрична стратегія. Суть його - робити щоразу хід, симетричний ходу супротивника або доповнює його до чого-небудь. Доказ правильності нашої стратегії буде користуватися тим, що після кожного нашого ходу позиція симетрична: раз так, то якщо противник зумів зробити свій хід, то і ми зможемо зробити хід, симетричний йому. Неправильно думати що симетрія - стратегія тільки для другого гравця. Якщо вихідна позиція - несиметрична, то зазвичай перший гравець може її якось зробити симетричною, а потім грати по симетрії, відповідаючи на ходи другого.Задача 2.4 . Двоє по черзі кладуть п'ятаки на круглий стіл так, щоб вони не накладалися один на одного. (Програє, як звичайно, той, хто не може зробити хід.)Розв’язання : Як би так першому гравцеві зробити свій хід, куди можна покласти п'ятак на порожньому круглому столі? А давайте його в центр покладемо! Увага: після такого ходу розташування п'ятаків на столі стало центрально симетричним Тепер давайте відповідати на кожен п'ятак другого гравця центрально симетричним йому п'ятаком. Чому ж стратегія ніколи не підводить (і ми не програємо)? Крах стратегії означає ,що другий поклав кудись п'ятак, а ми не змогли покласти п'ятак в симетричне місце (там вже щось лежить). Після нашого попереднього ходу позиція була симетричною (з симетричності не тільки зроблених ходів, а й самого столу), а місце, куди другий поклав п'ятак було вільне. Центрально симетричне йому місце, куди ми хочемо покласти свій п'ятак, теж було вільно. Але не міг же другий зайняти це місце своїм п'ятаком (це теж важливо відмітити, не у всіх задачах так буде!). Значить, не може бути так, щоб нам не було куди покласти свій п'ятак. Перший виграє.Задача 2.5. Двоє по черзі ставлять слонів в клітини шахової дошки так, щоб вони не били один одного (колір слонів значення не має).Розв’язання : Ну тут, здавалося б, без фокусів. Дошка має розмір 8x8, і ніяка клітина центром симетрії не буде. Тому другий може завжди відповідати на ходи першого симетричними ходами і виграє. АЛЕ: Нехай перший гравець поставив слона на діагональ дошки. Якщо другий гравець ставить свого слона в центрально симетричну клітку, то він опиниться на тій же діагоналі ... якраз під боєм слона, поставленого першим гравцем! Дійсно, буває так, що черговому симетричному ходу заважає хід, щойно зроблений супротивником (тому треба уважно стежити за такими ситуаціями!).Вихід з положення - застосувати симетрію не центральну, а осьову (відносно середньої лінії дошки). Неважко переконатися, що клітку, симетричну своєї позиції щодо осі, слон ніколи не б'є. Після кожного ходу другого вся позиція симетрична, в т.ч. розташування не б'ющихся полів; хід першого теж не ставить під бій поле, симетричне тому, куди він був зроблений. Тому симетричне поле не б'ється. Другий завжди може зробити хід і виграє.Задача 2.6. Є дві купки каміння, по 17 у кожній. За хід можна взяти кілька каменів, з однієї купки.Розв’язання : І це теж симетрія! Виграє другий - він бере з іншої купки стільки каменів, скільки перший взяв з однієї. При цьому після кожного ходу другого каменів в обох купках буде порівну - тому стратегію можна продовжувати.А якби купки були нерівні, то виграв би перший. Першим ходом він взяв би з більшою купки стільки каменів, щоб зрівняти її з меншою, а далі користувався б стратегією симетрії. [24]Насправді, нерідке явище: в залежності від вихідних даних одна і та ж стратегія приносить успіх то першому, то другому гравцеві.Аналіз виграшних позицій.Безперечно, самий потужний і універсальний спосіб розв’язання задачі -гри - пошук виграшних позицій. Тут називається виграшною та позицію, яку вигідно залишати після свого ходу, а програшною, відповідно, ту, яку невигідно (у згоді  з однією половиною методичної літератури і на противагу іншій половині ) Тоді фінальна позиція, з якої вже не можна зробити хід - виграшна. Основні властивості позицій такі:1.) Кожна позиція - або виграшна, або програшна (проміжних варіантів немає!);2.) З виграшної позиції можна піти тільки на програшну;3.) З будь-якої програшної позиції можна піти на виграшну.Тоді, якщо початкова позиція - програшна, виграє перший, якщо виграшна - другий. Стратегія однакова: кожен раз ходити на виграшну позицію. Тоді суперник повинен буде походити на програшну позицію (властивість 2), а ми знову зможемо піти на виграшну (властивість 3).Задача 2.7. "Хрома тура" може ходити по прямій вправо або вгору. Початково вона стоїть в нижньому лівому кутку дошки. Грають двоє. Виграє той, хто поставить туру у верхній правий кут.Розв’язання : Початково тура стоїть на головній (в даному випадку) діагоналі дошки. Перший гравець своїм ходом веде її з діагоналі в бік. Тоді другий гравець може повернути туру назад на діагональ. Потім перший знову зрушить її з діагоналі (ходів з головної діагоналі на неї ж немає), а другий знову зможе повернути і т.д. Так як клітка призначення лежить на головній діагоналі, то на ній тура обов'язково виявиться після ходу другого - і другий виграє. [23]Читаємо між рядків: "безліч виграшних позицій - це головна діагональ".Аналіз з кінця: як же шукати виграшні позиції, якщо вгадати їх не вдалося? Можна просто послідовно розібрати всі позиції, починаючи з останньої (бажано, для зручності, щоб безліч позицій вміщувалося на двовимірної дошці або таблиці). Фінальна позиція виграшна. Тому всі, з яких на неї можна піти - програшні. Тепер повинні утворитися позиції, з яких можна піти тільки на програшні - вони будуть виграшними. Всі позиції, з яких можна піти на якусь із цих виграшних - програшні і т.д., поки не дійдемо до початкової позиції.1.3. КомбінаторикаКомбінаторика - це математична наука, грубо кажучи, про підрахунок числа способів зробити що-небудь. Незважаючи на вузькість предмета вивчення, наука ця вельми глибока. Крім того, в олімпіадних задачах комбінаторика використовується настільки часто, що її знання абсолютно необхідно кожному математику-олімпіаднику.Хоча багато комбінаторних задач здаються очевидними, але багато школярів, особливо початківці, плутаються в них, приймаючи задачу одного типу за іншу. Уникнути плутанини в голові можна саме систематичним вивченням теорії.Основні комбінаторні формули і міркування:1.Адитивність взаємовиключних випадків. Якщо у задачі з комбінаторики є декілька взаємовиключних випадків/варіантів вибору, загальна кількість способів дорівнює сумі кількостей способів в кожному з цих випадків.2.Мультипликативність незалежних випадків. Якщо спосіб (кількість яких треба порахувати) повністю визначається декількома незалежними один від одного етапами вибору (на кожному етапі вибір варіантів - взаємовиключний!), То загальне число способів дорівнює добутку кількостей варіантів вибору на кожному етапі.Доведення Нехай всього є k етапів. Позначимо кількість варіантів вибору на першому етапі - n1, на другому етапі - n2, на останньому - nk. На першому етапі у нас є n1 варіантів вибору, тобто утворюється n1 випадків. На другому етапі в кожному з цих випадків ми може вибрати будь який з n2 варіантів, утворивши n2 подвипадків. Таким чином, після двох етапів буде вже n1* n2 випадків. На третьому етапі в кожному з них ми можемо вибрати будь-який з n3 варіантів  і після трьох етапів буде n1 * n2 * n3 випадків. Продовжуючи цей процес, ми отримуємо після всіх етапів n1 * n2 * ... * nk випадків - і це будуть вже остаточні способи. Їх кількість якраз дорівнює добутку кількостей варіантів вибору.Знову ж, у розв’язанні задач цю властивість можна навіть не формулювати якщо впевнені, що застосували його в правильній ситуації.[9]Насправді, доводячи п.2, ми користуємося твердженням п.1. Наприклад, як докладніше пояснити, чому після двох етапів є n1*n2 випадків? У нас є взаємовиключні випадки - варіанти вибору на першому етапі, яких n1 штук. У кожному з них є n2способів зробити вибір на двох етапах (на першому етапі варіант вже відомий, залишилося вибрати n2 варіантів на другому етапі). А щоб знайти загальне число способів зробити вибір на перших двох етапах, треба (відповідно до п.1) скласти n1 чисел, рівних n2, тобто помножити n1 на n2.3.Загальне правило мультипликативности подвипадків. Якщо спосіб повністю визначається декількома, можливо залежними один від одного, етапами вибору, але кількість варіантів вибору на кожному етапі не залежить від того, як був зроблений вибір на попередніх етапах, то загальне число способів дорівнює добутку кількостей варіантів вибору на кожному етапі.Доведення: Нічим не відрізняється від доведення попередньго, тому що там користувалися незалежністю від попередніх етапів вибору тільки кількость варіантів на даному етапі.Дуже поширеною помилкою є переплутування області застосування п.1 та п.2, аж до повного нерозуміння, де і чому треба складати варіанти, а де - множити. Тому тут же проілюструємо їх відмінність на прикладах.Приклади:Задача 3.1. З міста А в місто Б веде 6 доріг, з міста Б у місто В - 4 дороги, і більше ніяких доріг з цих міст не виходить. Скількома шляхами можна проїхати з міста А в місто В?Розв’язання : На першому етапі нам треба вибрати дорогу, по якій ми поїдемо з А в Б, і тут у нас є 6 варіантів. На другому етапі треба вибрати дорогу, по якій ми поїдемо з Б в В, і там у нас 4 варіанти. Ці два етапи повністю визначають шлях проїзду. Вибір незалежний, тому що по якій би дорозі ми не поїхали в Б, ми зможемо потім поїхати в В за кожної з доріг. Таким чином, ми маємо справу з незалежними етапами вибору, і повинні перемножать варіанти. Всього отримуємо 6 * 4 = 24 різних шляху.Задача 3.2. З глухого глухого міста Г, де зроду не було ніяких доріг, проклали 2 нові дороги в місто В з попередньої задачі. Крім того, з міста А з попередньої задачі в місто Г проклали ще 2 нові дороги. Скількома шляхами тепер можна проїхати з міста А в місто В?[47]Розв’язання : У цій задачі треба на самому початку виділити два взаємовиключних випадку: коли ми їдемо через місто Б, і коли їдемо через місто Г. Знайти кількість шляхів у першому випадку - це в точності завдання 1, і відповідь буде 6 * 4 = 24 ( по п.2). Знайти кількість шляхів у другому випадку - це завдання, аналогічна завданню 1, але з відповіддю 2 * 2 = 4. Тепер, за п.1, ці кількості шляхів треба скласти, і у відповіді виходить 24 +4 = 28 шляхів проїзду.Тепер займемося такими видами задач, де треба вибирати якісь предмети або елементи множин (для стандартизації, скажімо, що нам треба з n елементів вибрати k):4. Вибір з повтореннями, з урахуванням порядку (заповнення позицій елементами множини).Загальна задача може формулюватися так: "Є алфавіт з n букв. Скільки в цьому алфавіті" слів "які складаються з k літер?" Відповідь буде -nk.Доведення 1 : У нас є n способів вибрати першу літеру, n способів вибрати другу літеру ... n способів вибрати k-у  букву. Всього має k етапів вибору, по n варіантів на кожному. При цьому вибір незалежний (які б не були перші кілька букв, ми можемо вибрати будь-яку наступну). Тому, можна застосувати п.2 і отримати відповідь nk.Доведення 2: (Тут покажемо, як можна не ссилатися на затвердження п.2, а відтворити його доведення прямо в розв’язанні.) У нас є n способів написати першу букву (це дає n випадків). У кожному з них ми можемо n способами приписати до першої букви другу і отримати n двобуквений слів (утворюється n подвипадків). Всього буде n * n = n2 способів написати перші дві букви. У кожному з цих n2 випадків ми можемо n способами приписати в перших двох буквах третю і отримати n трибуквених слів (знову утворюється n подсвипадків). Всього буде n2 * n = n3 способів написати перші 3 літери. І так далі, поки ми не напишемо все слово - тут число способів буде n в степені, що дорівнює довжині слова, тобто nk.5. Вибір без повторень, з урахуванням порядку (розкладка в ряд).Загальна задача може формулюватися так: "Є купа з n різних предметів. Ми послідовно беремо з них k предметів і ставимо в ряд. Скільки є різних способів заповнення ряду?" Число у відповіді має своє спеціальне позначення: Ank і обчислюється за формулоюAn k = n * (n-1) * (n-2) * ... * (n-k +1) або Ank = n!/(n-k)! (друга формула виходить при множенні і діленні першою на (n-k)!)Доведення: У нас є n способів вибрати (взяти і поставити в ряд) перший предмет (назвемо це першим етапом вибору). Далі у нас є, незалежно від того, як обраний перший предмет, n-1 способів взяти другий предмет - в будь-якому випадку, це може бути який завгодно предмет, крім першого обраного. Потім є n-2 способи взяти третій предмет - він може бути який завгодно, крім перших двох обраних  и так далі. Звернемо увагу, що число способів вибрати останній, k-й предмет - не n-k, а n-k +1 = n-(k-1), тому що їм може бути будь-який, крім перших k-1 обраних. Разом, ми має k етапів вибору, на кожному з яких число варіантів одно (незалежно від того, як зроблено вибір на попередніх етапах), відповідно, n, n-1 ... n-k +1. Тому, відповідно до п.2 ', ми отримуємо загальне число способів вибору k предметів n*(n-1)* ... * (n-k +1).Вправи: Придумати доказ з повною підстановкою міркування з п.2, тобто схоже на док-во № 2 попереднього пункту.6. Перестановки n предметів.Мається n різних предметів. Скільки у нас способів виставити їх усі в ряд?Зазвичай це завдання розглядають як окрему і повторюють окремо всі комбинаторні міркування (як в дов-нні  2 п.4). Але зауважимо, що це завдання - окремий випадок п.5 при k = n. Тому відповідь буде Ann = n!7. Вибір без повторень, без урахування порядку (число сполучень).Загальна задача може формулюватися так: "Є купа з n різних предметів. Ми беремо з них k предметів і кидаємо в мішок. Скільки є різних способів заповнення мішка?" Число у відповіді має своє спеціальне позначення: Cnk і обчислюється за Сnk=Ank/k!  або Cnk=(n*(n-1)*(n-2)*...*(n-k+1))/k!  або Cnk=n!/(k!*(n-k)!) (друга і третя формули виходять при підстановці в першу формулу формул для Ank) .[2]Доведення : Досить довести тільки першу формулу. Нехай ми спочатку вибираємо k предметів послідовно і ставимо в ряд, а потім закидаємо цей ряд у мішок. Число можливих рядів і є An k. Доведемо, що заповнень мішка рівно в k! разів менше, ніж різних рядів - тоді формула буде доведена. (Зауважимо, що один і той же ряд не може переходити в два різних заповнення мішка!) Тепер обгорнемо процес закидання ряду в мішок: нехай у мішку лежать якісь k предметів, а ми дістаємо їх і ставимо в ряд. Згідно п.6, у нас для кожного заповнення мішка буде рівно k! різних рядів. Крім того, за нашим зауваженням, з двох різних заповнень мішка не можна отримати один і той же ряд. Тому рядів рівно в k! разів більше, ніж заповнення мішка.Взагалі кажучи, Cnk = Cnn-k для будь-якого n> = 0 і 0 <= k <= n.Приклади застосування пп.4-7:Задача 3.3. Скільки існує 6-цифрових чисел, в запису яких є хоча б одна парна цифра?Розв’язання : Розбирати випадки, скільки парних цифр і на яких місцях стоїть у нашому числі - занадто довго і противно. Скористаємося хитрим прийомом: порахувати те, що нам не потрібно. Тобто, вважати будемо числа з одних непарних цифр. Непарні цифри - це "алфавіт" з 5 "букв", а 6-значне число - "слово" з 6 "букв" цього "алфавіту". Таких слів-чисел, згідно п.4, буде рівно 56 штук. А чисел, які нас цікавлять (це всі інші) - рівно 900000-56 = 900000-15625 = 984375 (всього 6-значних чисел 900000).Задача 3.4. За Конституцією, прапор країни складається з трьох однакових горизонтальних смуг трьох різних кольорів, причому на прапорі можуть бути тільки білий, червоний, жовтий, зелений, блакитний і чорний кольори. Скільки різних прапорів дозволяє така Конституція?Розв’язання : Ми маємо справу з вибором 3-х з 6. Вибір відбувається без повторень (кольори повинні бути різні) і з урахуванням порядку (важливо, який колір вгорі, який внизу і який в середині). Згідно п.5, відповіддю буде число A63 = 6 * 5 * 4 = 120.Задача 3.5. Один професор математики написав 6 книг, інший - 8. Кожен з хоче подарувати іншому 3 свої книги з автографом. Скількома способами вони можуть обмінятися подарунками?Розв’язання: Перший професор може вибрати для подарунка 3 книги зі своїх 6, а це можна зробити C63 = 20 способами (див. п.6). Другий професор може вибрати для подарунка 3 книги зі своїх 8, вже C83= 56 способами. Обидва вибори відбуваються незалежно і однозначно визначають спосіб обміну, тому варіанти потрібно перемножувати. Відповідь: C63*C83=56*20=1120 способів.8. Перестановки предметів, серед яких є однакові. Ми розглянемо тут на прикладах один стандартний метод такого підрахунку. Загальний вигляд відповіді краще зрозуміти і запам'ятати не у вигляді формули, а у вигляді правила: "взяти факторіал кількості всіх предметів і поділити на факторіали розмірів всіх груп однакових предметів".Приклади:Задача 3.6. Скільки "слів" можна отримати, переставляючи букви в слові ЛІНІЯ?Розв’язання: У цьому слові є 2 однакові літери (І). Будемо тимчасово вважати їх різними: І1 і І2. За п.6 отримуємо, що тепер можна скласти 5! = 120 слів. Насправді, це в кілька разів більше, ніж потрібно. У скільки ж саме? Зрозуміло, що слова, різняться тільки перестановкою літер І1 і І2 на тих же місцях (наприклад, ЛІ 1 ЯНІ 2 і ЧИ 2 ЯНІ 1), насправді однакові, хоча ми порахували їх як різні. Всього на одних і тих же місцях можна розставити букви І1 і І2 рівно 2! = 2-ма способами, отже, кожного разу ми замість одного слова отримуємо 2 різних. Значить, ми отримали 120:2 = 60 різних слів. [30] "Цешка", трикутник Паскаля і Біном Ньютона:У попередніх прикладах ми обчислювали числа Cnk безпосередньо за формулою, роблячи багато множень і ділень. Виявляється, є метод обчислювати відразу багато різних "цешок", використовуючи тільки додавання. Особливо важливо це при програмній реалізації, оскільки комп'ютер складає числа набагато швидше, ніж примножує і тим більше ділить. Cn +1 k +1= Cnk + Cnk +1.Побудуємо з чисел два нескінченних трикутника. У першому з них будемо 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 C00 C10 C11 C20 C21 C22 C30 C31 C32 C33 C40 C41 C42 C43 C44 ставити одиниці в самому верху і по краях кожному наступного рядка, а кожне з інших чисел буде дорівнює сумі двох, що стоять над ним зліва і справа (цей трикутник називається трикутником Паскаля). (A + b) n = (a + b) (a + b) ... (a + b) (n дужок). Розкриваючи дужки, отримуємо в окремих доданків твори n букв, кожна з яких - a або b, тобто a nk b k при якомусь k від 0 до n. Доведемо, що для кожного такого k число таких доданків - рівно C n k, звідки, привівши подібні, і отримуємо формулу бінома. Але це правда: a nk b k виходить шляхом взяття a з k дужок і b з nk залишилися; різні такі доданки виходять шляхом різного вибору цих самих k дужок, а k дужок з n можна вибрати саме C n k способами, ч.т . д. Теорія "кульок і перегородок":Задача 3.7. Є k ящиків і n> = k Однаково кульок. Скількома способами можна розкласти кульки  по ящиках так, щоб жодна скринька не виявилася порожньою?Розв’язання: Визначимо розкладку так: викладемо кульки в ряд і поставимо між ними k-1 перегородку. Те, що зліва від першої перегородки, покладемо в перший ящик, між першою і другою - у другий ... те, що праворуч від останньої - в останній, k-й ящик. Ящик буде порожнім, тільки якщо дві перегородки стоять поруч не розділені кулями, або перегородка стоїть скраю, лівіше або правіше всіх куль. Так давайте це заборонимо! Нехай на кожне зn-1 місць між n кулями можна поставити не більше однієї з k-1 перегородок. Тобто, з n-1 місць треба буде вибрати k-1, куди ми ставимо перегородки. Звідси отримуємо відповідь: Cn-1k-1.Задача 3.8. А скільки способів розкласти кульки, якщо можуть бути порожні ящики?Розв'язання : Якщо визначати розкладку так само, ставлячи між кулямиk-1 перегородку, то обмежень вже не буде: кульки та перегородки можна ставити в довільному порядку. Давайте вважати, що у нас розставлено в ряд    n+k-1 об'єктів: n з них кульки, а інші - перегородки. Тоді розкладка буде визначатися тим, на яких місцях які об'єкти стоять. З n+k-1 місць можна вибрати n місць для куль Cn+k-1n способами, або: k-1 місце для перегородокCn+k-1k-1 способами. Ці числа рівні і обидва є відповіддю. 1.4. ГрафиПоняття графа. Ребра і вершини.Графом в математиці називається картинка з крапочок, з'єднаних паличками (більш суворе визначення існує, але на практиці ніколи не потрібне). Ці крапочки називаються вершинами графа, а палички (вони можуть бути і кривими; деякі графи взагалі неможливо намалювати так, щоб усі палички були прямими) - ребрами графа. Дві вершини, з'єднані ребром, називаються сусідніми. Послідовність ребер, що з'єднують дві вершини, називається шляхом.Оскільки теорія графів не входить до шкільної програми з математики, то в умовах олімпіадних завдань не буває слова "граф". Проте завдання з теорії графів легко впізнавані - найчастіше це завдання про людей і знайомства (а також інші види відносин), або про міста і дороги (та інші лінії зв'язку).Орієнтований граф - це граф на ребрах якого розставляються стрілочки, і проводити шляхи дозволяється тільки в напрямку стрілок. Типові формулювання задач - про дороги з одностороннім рухом, або про односторонні відносини між людьми.Однакові за структурою графи називаються ізоморфними, при цьому вони можуть малюватися зовсім по-різному. Точне визначення ізоморфізму: вершини обох графів можна занумерувати так, що дві вершини в одному графі сусідні тоді і тільки тоді, коли сусідні дві вершини з тими ж номерами в іншому графі. Наприклад, ізоморфізм графів, зображених внизу, зовні неочевидний, але перевіряється за визначенням.Для ізоморфізму орієнтованих графів потрібно також, щоб напрям ребер між вершинами з однаковими номерами було однаковим.Можливі графи з деякими крайніми випадками: існування в орієнтованому графі 2-х ребер, що з'єднують одну і ту ж пару вершин у різних напрямках (зустрічається найчастіше); наявність в неорієнтованому графі кількох ребер між одними і тими ж двома вершинами; наявність у графі "петель" - ребер, що з'єднують вершину з самою собою. Завжди слід з'ясовувати, які з цих ситуацій можуть бути присутніми в даній задачі, і які з них можете отримати ви самі, проводячи перетворення графа.Ступені вершин, число ребер і парність.Ступенем вершини в графі називається число ребер, що виходять з неї. У орієнтованому графі у кожної вершини є 2 ступеня: вхідна (число ребер, що входять у вершину) та вихідна (число ребер, що виходять з вершини). Ми говоримо, що вершина графа парна, якщо її ступінь парний, і що вершина непарна - в іншому випадку (у графі на рис. Нагорі всі вершини парні). Для орієнтованого графа поняття парності вершини зазвичай не вводиться.У графі ступені вершин і кількість ребер пов'язані важливими співвідношеннями:Задача 4.1. У державі 100 міст, з кожного виходить 2 дороги, окрім столиці, звідки виходить 5 доріг і міста Гірський, звідки виходить одна єдина дорога. Скільки всього доріг в державі? [20]Розв’язання : Складемо кількості доріг, що виходять з усіх міст:98 * 2 +5 +1 = 202. Це число - кількість кінців всіх доріг. Оскільки кожна дорога має 2 кінці, то кількість доріг буде вдвічі менше, а саме 101.Аналогічними міркуваннями доводиться, що в будь-якому графі кількість ребер вдвічі менше суми ступенів усіх вершин.Задача 4.2. На острів Коневец завезли 13 телефонів. Настоятель хоче організувати таку схему телефонного зв'язку, щоб з'єднати кожен телефон рівно з 7-ма іншими. Чи вдасться йому це?Розв’язання : Порахуємо, скільки проводів потрібно, щоб здійснити таку схему. Кінців проводів буде 13 * 7 = 91, а самих проводів - удвічі менше, тобто ... 45,5 штук. Це означає, що така схема зв'язку неможлива.Зауваження. Число непарних вершин будь-якого графа парне (саме ця властивість заважає побудувати мережу зв'язку в попередній задачі).Доведення: Сума кількох цілих чисел парна тоді і тільки тоді, коли серед чисел парне число непарних. Застосуємо це до ступеня вершин: сума ступенів вершин парна тоді і тільки тоді, коли непарних вершин парне число. Але сума ступенів вершин завжди парна (вона рівно вдвічі більше числа ребер). Значить, і парних вершин завжди парне число.Компоненти зв'язності.Назвемо граф зв'язним, якщо будь-які 2 вершини можуть бути з'єднані шляхом з ребер. Незв'язний граф складається з декількох шматків, кожен з яких зв'язний. Такі шматки називаються компонентами зв'язності. Будь який зв'язний граф складається з одного компоненти зв'язності - всього графа. У орієнтованому графи є різні види зв'язності: одностороння і двостороння. Щодо останньої граф теж розбивається на компоненти зв'язності.Приклади:Задача 4.3 Довести, що в державі (з задачі:У державі 100 міст, з кожного виходить 2 дороги, окрім столиці, звідки виходить 5 доріг і міста Гірський, звідки виходить одна єдина дорога. Скільки всього доріг в державі?) можна зі столиці доїхати (як-небудь, можливо, з декількома пересадками в різних містах), до міста Гірський.Розв’язання: Твердження задачі означає, що столиця і місто Гірський знаходяться в одному компоненті зв'язності. Нехай це не так. Тоді візьмемо компоненту зв'язності, що містить столицю. Розглянемо її як окремий граф . У цьому графі столиця - єдина непарна вершина (міста Гірський там, за нашим припущенням, немає). Але в будь-якому графі парне число непарних вершин , значить, наше припущення не могло бути вірно. Тоді столиця і місто Гірський знаходяться в одній компоненті зв'язності.Слід звернути увагу на запропонований прийом - розглянути компоненту зв'язності як окремий зв'язний граф і застосувати якесь твердження до цього графуЗадача 4.4.  На острові Коневец 13 привезених телефонів з'єднали між собою, причому з кожного телефону виходить не менш 6-ти проводів Довести, що а) з будь-якого телефону можна зв'язатися з будь-яким, б) це можна зробити, використовуючи не більше ніж 1 телефон в якості проміжної станції.Розв’язання: Оскільки парність степенів вершин нам невідома, то відповідним твердженням ми користуватися не будемо. Зате, оскільки на степені вершин є оцінка знизу, то оцінимо знизу розмір компоненту зв'язності. У будь компоненті зв'язності є хоча б 1 вершина (1 телефон), а разом з нею - всі її сусіди (з'єднаний з ним проводами), що не менше 6 штук. Всього буде не менше 7 вершин.[18]а) Якщо б у графі було хоча б 2 компоненти зв'язності, то було б не менше 2 * 7 = 14 вершин. А раз вершин всього лише 13, то компонента одна, тобто граф зв'язний.б) Нам треба довести, що будь-які дві вершини - або сусіди, або мають загального сусіда. Це означає, що будь-які два "пучка" перетинаються (пучком буде називати безліч з однієї вершини - "центру пучка" - і всіх її сусідів). Але у попередньому пункті ми оцінювали компоненти зв'язності саме пучком. Там ми довели, насправді, що в будь-якому пучку не менше 7 вершин, тому двох непересічних пучків у графі з 13 вершин бути не може.Ейлерові графи.Поняття ейлерового графа пов'язано зі наступними задачами: чи можна намалювати даний граф, не відриваючи олівець від паперу і проводячи кожне ребро рівно по разу? А чи можна так зробити, щоб врешті олівець повернувся в першу намальовану вершину? Виявляється, як встановив в XVIII столітті Леонард Ейлер, існує дуже простий критерій розв'язності цієї задачі.А чи можна намалювати, не відриваючи олівця, два графа на малюнку внизу?Ейлеровим шляхом  у графі називається шлях, що проходить по всіх ребрах графа рівно по разу. Існування ейлерова шляху якраз і означає, що граф можна намалювати, не відриваючи олівця від паперу і проводячи кожне ребро рівно по разу. ейлерова циклом називається такий тип ейлерова шляху, в якому початкова та кінцева вершини збігаються (тобто, тут утворюється цикл і в ньому початковою вершиною можна вважати будь-яку ). Існування ейлерова циклу означає, що граф можна намалювати ще й так, щоб олівець повернувся в першу намальовану вершину. ейлерова графом для стислості називають граф, що містить Ейлеровий шлях або Ейлеровий цикл.Критерій Ейлера:  У зв'язковому графі існує Ейлеровий шлях тоді і тільки тоді, коли в ньому не більше 2-х непарних вершин, а Ейлеровий цикл - тоді і тільки тоді, коли в ньому всі вершини парні . У незв'язному графі очевидно, що ейлерового шляху існувати не може (але він існує в тих компонентах зв'язності, які задовольняють критерію).Доведення: У бік необхідності критерію все досить просто: у будь-яку вершину Ейлеровий шлях кілька разів заходить і щоразу, вже по іншому ребру, виходить (при цьому кожен новий захід йде вже по новим, ще не пройденим раніше ребрам). Об'єднаємо такі 2 ребра в пару - тоді всі ребра, що виходять з однієї вершини, розіб'ються на пари. Тому цих ребер парне число - і вершина парна. Виникають ще два винятки: перше ребро, що виходить з початкової вершини шляху і останнє ребро, що входить в кінцеву вершину шляху, ні з ким не об'єднуються в пару (але якщо шлях є циклом, їх можна об'єднати в пару один з одним, тому що вони виходять з однієї вершини). Таким чином, у графі, де є Ейлеровий цикл , всі вершини - парні (ми про будь-яку вершини довели, що вона парна), а в графі, де є Ейлеровий шлях (який не є циклом), парні всі вершини, окрім двох - початку і кінця цього шляху.Насправді, разом з необхідністю критерію Ейлера ми довели ще ряд попутних фактів:- Початок і кінець ейлерового шляху, якщо вони різні, завжди вершини непарного ступеня;- тому в графі, де всі вершини парні, будь-який Ейлеровий шлях буде ейлеровим циклом;- А в графі, де є 2 непарні вершини, тільки вони можуть бути початком і кінцем ейлерового шляху;- Графи ж з одною непарною вершиною ми не розглядаємо, тому що їх немає в природі . 1.5. ГеометріяНерівність трикутника.Ця нерівність - найвідоміша, найголовніша і практично єдина геометрична нерівність - в тому сенсі, що всі нерівності в геометрії виходять як слідства нерівності трикутника. Довжина будь-якої сторони трикутника менше суми довжин двох інших сторін. (Таким чином, для одного і того ж трикутника, наприклад, ABC - так ми будемо стандартно позначати трикутник - можна написати три різних нерівності трикутника: AB <AC + BC, AC <AB + BC, BC <AB + AC).Доведення:  Доведемо, наприклад, що AB <AC + BC. На продовженні сторони AC за точку C відкладемо (див. рис.) відрізок CB ', рівний по довжині CB. Тоді трикутник BB'C - рівнобедрений, тому в ньому рівні кути B'BC і BB'C при основі (на рис. Ці кути відмічені однією дужкою). Далі, кут BB'C = куту B'BC <кута ABC, тому що є його частиною. У трикутнику проти більшого кута лежить більша сторона (і, звичайно, проти більшої сторони лежить більший кут), тому в тр-нику ABB ' AB <AB'. Але AB '= AC + CB' = AC + BC, оскільки CB 'будувався, як відрізок, рівний по довжині BC. Звідси AB <AC + BC.Основні наслідки.1.  Довжина будь-якої сторони трикутника більше різниці довжин двох інших сторін (це означає, наприклад, AB> | AC-BC |, тобто різниця вважається за абсолютною величиною). Відповідно, для будь-яких трьох точок на площині вірно Нечитка нерівність виду AB> = | AC-BC |.Доводиться цей факт зовсім просто (наприклад, що AC> | AB-BC |): По нерівності трикутника, ми маємо AC + BC> AB. Перенесемо в іншу частину і отримаємо AC> AB-BC. Візьмемо інше нерівність трикутника: AB + AC> BC і так само одержимо AC> BC-AB. Так як | AB-BC | - це або AB-BC, або BC-AB (дивлячись, що більше: AB або BC), то воно в будь-якому випадку менше AC,2. Довжина будь-якої сторони трикутника менше його напівпериметра . Якщо ж трикутник може бути виродженим (це інша назва для того, що три вершини в дійсності не утворюють трикутник), то вірна нестрога нерівність - тільки периметр виродженого трикутника ми будемо вважати як суму AB + AC + BC.Тут арифметики трохи більше. До звичайного нерівності трикутника (наприклад, BC <AB + AC) додаємо ту сторону, яка менше суми інших. Виходить 2BC <AB + AC + BC - у правій частині стоїть якраз периметр трикутника (позначимо його буквою P). Тепер поділимо все на 2 і отримаємо саме BC <P / 2.. Доказ знову ж не змінюється для виродженого трикутника.3.  Найкоротший шлях між двома точками - це відрізок прямої.Нехай A і B - дві точки і вони з'єднані якоюсь ламаною AL 1 L 2 ... L n B. Доведемо, що ця ламана довше відрізка AB. Подивимося на трикутник AL 1 L2 - у ньому, за нерівністю трикутника, AL 2 <AL 1 + L 1 L 2 , тому ламанаAL 2 ... L nB (див. рис. що починається з пунктирною лінії ) буде коротшим вихідної (суцільні лінії на тому ж малюнку). Застосуємо до неї ту ж операцію - і отримаємо ще більш коротку ламану AL 3 ... L n B (див. лінію з точок на рис.). Багаторазово повторюючи цю операцію, прийдемо до ламаної AL n B. А вона, за нерівністю трикутника, довше відрізка AB .Важливо відзначити, що останні три твердження не просто наслідки нерівності трикутника, а його рівносильні переформулювання . Тобто, доказ цих тверджень можна проробити у зворотний бік.Алгебраїчна комбінація.Самий "дешевий і практичний" спосіб отримання геометричних нерівностей - це алгебраїчна комбінація декількох нерівностей трикутника: помножити / розділити нерівність на якесь число, скласти кілька таких нерівностей, підставити одне нерівність в інше і т.п. Геометричні міркування, навпаки, практично не використовуються (ну, іноді треба буває написати у формулі замість одного відрізка іншого - рівний, завідомо більший або заведомо менший, залежно від обставин). Типові задачі на алгебраїчну комбінацію - які-небудь красиво-симетричні, де фігурує периметр або сума довжин діагоналей багатокутника.[5]Задача 5.1.  Знайти точку всередині опуклого чотирикутника з мінімальною сумою відстаней до вершин.Розв’язання:  Нехай ABCD - чотирикутник, O - якась (довільна) точка всередині (див. рис). Тоді шукана точка - та, де досягається мінімум величини AO+BO+CO+DO. Тепер ми хочемо оцінити цю суму знизу (тобто знайти якусь свідомо не велику) за нерівністю трикутника, причому бажано так, щоб ця оцінка зверталася в рівність у якійсь відомій точці. Вирази виду AO+BO>= AB - явно не те, що потрібно, тому що з них звертається в рівність не більше двох відразу. Спробуємо скласти їх по-іншому: AO + CO> = AC, BO + DO> = BD. Перша нерівність звертається в рівність, якщо O лежить на діагоналі AC, друга - якщо O на діагоналі BD. AO + BO + CO + DO> = AC + BD - і рівність досягається, якщо O - точка перетину діагоналей. Відповідь: Шукана точка - це точка перетину діагоналей.Задача 5.2.  Доведіть, що сума довжин діагоналей опуклого чотирикутника менше його периметра.Розв’язання :  Тут нам треба застосувати нерівності трикутника, що оцінюють діагоналі чотирикутника зверху , а сторони - знизу (тобто сторони повинні стояти в тій частині нерівності, яка більше, а діагоналі - в тій, яка менше). Таких нерівностей ми можемо знайти 4 штуки (для наочності можна дивитися на рис. Вгорі): AC <AB + BC, AC <CD + AD, BD <BC + CD, BD <AD + AB. У лівих частинах цих нерівностей кожна діагональ зустрічається по 2 рази. У правих частинах - кожна сторона по 2 рази. Тому, якщо скласти всі нерівності і поділити суму на 2, то отримаємо ... AC+BD<AB + BC + CD + AD. [16]Геометричні перетворення.Ми вже виводили з нерівності трикутника, що найкоротший шлях між точками - це пряма. Але що робити, якщо ми шукаємо не просто найкоротший шлях, а найкоротший серед шляхів якогось спеціального виду, серед яких немає прямолінійного? Виявляється, і тут зазвичай виручає те, що ламана довше прямої. Треба шукати геометричне перетворення з наступними властивостями:1.) Воно не змінює довжин шляхів (або, як мінімум, переводить більш довгий шлях в більш довгий, а більш короткий - в більш короткий);2.) Після перетворення цікавить нас шлях може бути прямолінійним.Тепер треба знайти всі шляхи (їх може бути багато!), що переходять при перетворенні у відрізок прямої. Вони і будуть найкоротшими.В якості перетворень добре підходять рухи в  площині (симетрії, повороти, паралельні переноси), застосовувані часто вже не до всього шляху, а до якихось його шматках.Задача 5.3.  Диверсант виходить з лісу в заданій точці (A). Він повинен дійти до залізниці (прямолінійно), закласти там міну і повернутися в ліс в іншій заданій точці (B), по ту ж сторону від ж / д (див. рис.). Як йому зробити це, пройшовши по найкоротшому шляху?Розв’язання :  Нам треба шукати найкоротший шлях з точки A в точку B, що перетинає дану пряму. Якби ці точки лежали по одну сторону від прямої (а не так, як насправді), ми б просто з'єднали їх відрізком! Але "якщо не можна, але дуже хочеться, то можна": давайте відобразимо точку B відносно прямої в точку B '.Від A до B 'провести шлях по прямій вже можна. Тепер як перетворити шлях від A до B в дорогу від A до B 'тієї ж довжини? Та дуже просто - відобразити відносно прямої частину шляху після перетину з нею (точки C або C 'на рис.) - Адже симетрія не змінює відстаней. Тоді шлях ACB перейде в дорогу ACB 'тієї ж довжини, а шлях AC'B - у AC'B' (тут відповідність шляхів - взаємно-однозначна!). Шлях A'C'B ', що йде по прямій, коротше будь-якого іншого. Значить, початково найкоротшим був відповідний йому шлях AC'B.Задача 5.4.  AOB - прямий кут, C - точка всередині нього. Доведіть, що периметр тр-ника ABC менше 2OC.Розв’язання:  Прямий кут - це якось несиметрично, некрасиво. Давайте відобразимо картинку щодо обох сторін кута, як на рис. Тоді, раз симетрія зберігає відстані, AB=AB1=A1B=A1B1, AC=AC1=A1C2=A1C3 і BC=BC3=B1C1=B1C2.. ТомуP(ABC)=AB+AC+BC=CA+AB1+B1C2- це довжина ламаної з C в C2 . А 2OC=OC+ OC2 - це відстань між тими ж точками по прямій і воно, безумовно, коротше. [17]Точка Торрічеллі.  Тут вже говорилося про особливу точці всередині чотирикутника: сума відстаней від неї до вершин мінімальна. Усередині будь-якого трикутника теж є така точка - вона називається точкою Торрічеллі. Виявляється, з точки Торрічеллі всі сторони видно під кутом 120 градусів. Ця властивість визначає її однозначно і дозволяє побудувати точку Торрічеллі циркулем і лінійкою. Доводиться головна властивість точки Торрічеллі відомим нам методом - дещо перетворити і перетворити відрізки з точки в вершини трикутника в ламану, яка буває прямою , причому саме для точки Торрічеллі.Рухи площині: основні властивості.  Рухом  називається відображення площині (або простору) в себе, що зберігає відстані . Основні види рухів: паралельне перенесення , поворот , осьова і центральна симетрія. Насправді, осьова симетрія - це поворот на 180 градусів , і її правильніше вважати окремим випадком повороту. Крім того, різноманітність рухів не вичерпується цими чотирма типами.1.  Осьова симетрія (див. рис. ліворуч), тобто дзеркальне відображення, на відміну від інших рухів, змінює орієнтацію площині. Якщо (див. рис.) подивитися з A вздовж відрізка AB, то точка C буде праворуч, а якщо з A' вздовж відрізка A'B' - то C' буде вже ліворуч. Ця зміна і є зміна орієнтації. Множиною  нерухомих точок (тобто точок, що переходять в себе) при осьовій симетрії є пряма , щодо якої ми відображаємо, так звана вісь симетрії . Симетрія однозначно визначається своєю віссю2.  Поворот (див. рис. у центрі) і центральна симетрія, не змінюють орієнтацію площини. Множина  нерухомих точок повороту - це одна точка , навколо якої робиться поворот - центр повороту (або, відповідно центр симетрії ). Поворот однозначно визначається своїм центром і кутом повороту.3.  Паралельне перенесення (див. рис. праворуч) не змінює орієнтацію площини і не має нерухомих точок. Він однозначно визначається вектором , тобто спрямованим відрізком , на який зсуваються точки при перенесенні.Зауваження .  Рух переводить пряму в пряму, а окружність в коло.Доведення : Умова "три точки лежать на одній прямій" записується через відстані між ними: як рівність в нерівності трикутника. Рух зберігає відстань, отже, зберігає і рівність. Тоді три точки, що лежать (або не лежать) на одній прямій переходять в три точки, що лежать або не лежать на одній прямій відповідно. Тому прямі переходять у прямі.Затвердження.  Рух переводить трикутник у рівний йому трикутник.Доведення : Візьмемо трикутник ABC і точки A', B', C', в які його вершини переходять при русі. Ми знаємо, що точки A', B' і C 'теж утворюють трикутник, і сторони ABC переходять в сторони A'B'C'. Оскільки рух зберігає відстані, то сторони цих трикутників відповідно рівні, і тоді трикутники рівні. Наслідок.  Рух зберігає кути (тобто будь-який кут переходить у рівний йому)Затвердження.  Будь-який рух можна представити як композицію паралельного перенесення, повороту і осьової симетрії (якихось із цих складових може і не бути).Доведення :  Нехай рух переводить точку A в A', B у B' і C в C '(A, B і C не лежать в одній прямий!). Зробимо паралельне перенесення, що переводить A в A', і поворот, навколо A = A', який поєднує промені AB і A'B '. Так як довжини AB і A'B 'рівні, то після повороту B поєднується з B'. Тепер подивимося, де може виявитися C. Звичайно, на перетині двох кіл з центрами в A (A') і B (B') радіусів AC =A'C 'і BC = B'C'. У цих кіл дві точки перетину, симетричні щодо AB. Якщо C - одна з них, а C '- інша, то зробимо симетрію відносно прямої AB і переведемо C в C'. В іншому випадку вже C = C 'і симетрію робити не треба.Побудували композицію необхідного виду, що переводить A, B і C у A ', B' і C 'відповідно. Але, за попереднім твердженням, рух, що переводить A, B і C у A ', B' і C ', єдино. Значить, ця композиція і є вихідне рух.Задача 5.5.  Доведіть, що паралельне перенесення можна представити як композицію двох центральних симетрій.Розв'язання :  Відзначимо дві точки M і N такі, що перенесення проводиться в напрямку від M до N, але на довжину, вдвічі більшу MN (див. рис.). Зробимо центральну симетрію з центром M, а потім другу з центром N. P при першій симетрії переходить в N, при другій залишається на місці.M за першої симетрії залишається на місці, при другій переходить в Q. X при першій симетрії переходить в Z, при другій Z переходить в Y. Але вихідний паралельне перенесення теж переводить P в N, M в Q і X в Y. Значить, він збігається з композицією двох симетрій.Задача 5.6.  Доведіть, що у трикутника не буває рівно двох осей симетрії.Розв’язання : Нехай у трикутника ABC рівно дві осі симетрії. Ясно, що симетрія переводить вершину в вершину. Нехай перша симетрія переводить A в B (і, звичайно, B у A). C повинна теж перейти в якусь вершину, тому C переходить в себе (тобто вісь симетрії проходить через C). Симетрія - це рух, тому AC = BC. Друга симетрія, відмінна від першої, не може міняти місцями A і B. Нехай вона переводить A в C. Тоді, аналогічно, AB = BC. Звідси отримуємо AB=AC=BC, тобто трикутник рівносторонній. А в рівносторонньому трикутнику - вже не дві, а цілих три осі симетрії : його медіани, вони ж бісектриси, вони ж висоти.Зауваження.  У рівнобедреного, але не рівностороннього трикутника рівно одна вісь симетрії. У нерівнобедренного трикутника осей симетрії немає взагалі.Рахунок кутів - основа олімпіадної геометрії.  Більшість олімпіадних геометричних задач вирішуються досить нехитрою технікою: відзначаємо на зображенні два-три кути і виражаємо через них всі інші, користуючись простими властивостями:1.) Вертикальні кути рівні;2.) Суміжні кути дають у сумі 180 градусів;3.) Сума кутів трикутника завжди дорівнює 180 градусів, чотирикутника - 360 градусів, n-кутника - 180 * (n-2) градусів;4.) При перетині паралельних прямих січною навхрест лежачі і відповідні кути рівні, односторонні ж дають в сумі 180 градусів;5.) Вписаний (в коло) кут дорівнює половині дуги, на яку він спирається, тобто половині її центрального кута;6.) Вписані кути, які спираються на одну й ту ж дугу, рівні;7.) У чотирикутнику, вписаному в коло, протилежні кути дають у сумі 180 градусів;8.) Рух не міняє величин кутів.Ще одне міркування, яке дозволить швидко збільшувати число пар рівних кутів - критерії вписаності чотирикутника :1.) Чотирикутник вписаний тоді і тільки тоді , коли в ньому сума протилежних кутів дорівнює 180 градусів.2.) Чотирикутник вписаний тоді і тільки тоді , коли в ньому рівні два кути між стороною і діагоналлю, що спираються на одну дугу.Лема 1.  Кут між січними до кола дорівнює напівсумі висікаючих ними дуг (якщо вони перетинаються всередині кола), або напіврізниці цих дуг (якщо вони перетинаються зовні).   Доведення леми 1:  Доведемо, що в ситуації на рис. ліворуч ^ AXB = ^ CXD дорівнює напівсумі дуг AB і CD, а на рис. праворуч ^ AYB = ^ CYD - полуразность дуг AB і CD.Розглянемо трикутник ACX. У ньому ^ CAX + ^ AXC + ^ AXC = 180 градусів, тобто 180 - ^ AXC = ^ CAX + ^ ACX. Але, з одного боку, 180 - ^ AXC = ^ AXB (суміжні), а з іншого боку, ^ CAX = ^ CAD = CD / 2, ^ ACX = ^ ACB = AB / 2 (по теор. Про вписаний кут), тобто їх сума дорівнює (AB + CD) / 2 (маються на увазі дуги , а не відрізки AB і CD). Звідси ^ AXB = (AB + CD) / 2, ч.т.д.В іншому випадку, в трикутнику BCY, ^ BYC + ^ CBY + ^ BCY = 180 градусів і звідси ^ ACB = 180 - ^ BCY = ^ CBY + ^ BYC. Знову ж, за теоремою про вписаний кут, ^ ACB = AB / 2 і ^ CBY = ^ CBD = CD / 2. Тоді ^ BYC = ^ ACB-^ CBY = (AB-CD) / 2.Лема 2.  (обернена до теореми про вписаний кут). "Якщо кут дорівнює половині дуги, на яку він спирається, то він вписаний". Строго кажучи, якщо кут висікає на колі дугу і дорівнює половині цієї дуги, то його вершина лежить на колі.Доведення  леми 2:  Від супротивного: нехай кут AXB висікає на колі дугу AB, ^ AXB = AB / 2 (тут і далі під AB і CD будуть розумітися не відрізки, а дуги), але X не лежить на колі. Якщо X - усередині кола, то ми маємо ситуацію як на рис. до Леми 1 зліва. Тоді ^ AXB = (AB + CD) / 2> AB / 2 (по лемі 1). Якщо ж X - поза кола, то ситуація як на рис. до Леми 1 справа. Тут вже ^ AXB = (AB-CD) / 2 <AB / 2 (теж по лемі 1). В обох випадках - протиріччя.Задача 5.7.  У трикутник ABC з кутом 36 градусів при вершині A проведена бісектриса BK. Доведіть, що BK = BC.Розв’язання :  У трикутнику ABC кут A дорівнює 36 градусів, ^ B = ^ C, а сума всіх трьох, звичайно, 180 градусів. Тому ^ B = ^ C = 72, а ^ ABK = ^ B / 2 = 36 градусів. У трикутнику ABK: ^ AKB = 180 - ^ BAK-^ ABK = 180-36-36 = 108 градусів (знову із суми кутів трикутника). Суміжний з ним кут BKC дорівнює 72 градуси. Тоді в трикутнику BCK ^ BKC = ^ BCK = 72 і тому він рівнобедрений, тобто BK = BC, ч.т.д.Задача 5.8.  Два кола перетинаються в точках A і B. C і D - діаметрально протилежні A точки на першій і другій колах відповідні Доведіть, що B, C і D лежать на одній прямій.Розв’язання:  Кут ABC вписаний в перше коло і спирається на її діаметр, тому він прямий (діаметр обмежує дугу в 180 градусів). А кут ABD теж прямий, так як вписаний в друге коло і спирається на його діаметр. Тоді ^ CBD = ^ ABC + ^ ABD = 90 +90 = 180 градусів. Тому B, C і D лежать на одній прямій.Задача 5.9.  Дві хорди, AC і BD, кола S паралельні. Доведіть, що AC = BD.Розв’язання :  Чотирикутник ABDC вписаний, тому в ньому рівні пари кутів, що спираються на одну дугу. Наприклад, ^ BAD = ^ BCD і ^ ABC = ^ ADC. Оскільки AB і CD паралельні, то рівні навхрест лежачі кути при перетині їх січною: ^ BAD = ^ ADC і ^ ABC = ^ ADC. Тоді рівні всі чотири кута (на рис. Вони всі позначені однією дужкою). Тому трикутники ABX і CDX (X - точка перетину AD і BC) рівнобедрені, тобто AX = BX і CX = DX. Крім того, суміжні кути AXC і BXD рівні, звідки отримуємо рівність трикутників ACX і BDX по двох сторонах і куту між ними. А раз трикутники рівні, то AC = BD

Пролема вибору з точки зору теорії імовірності

Чтв, 14/07/2011 - 13:46 — Irina

Проблема Монті Холла, або проблема прийняття рішення поставала перед кожним із нас хоч раз у житті. Як збільшити свої шанси на успіх за допомогою теорії імовірності? Про це у відеосюжеті...

Детальніше:http://kirdey.com/prolema-viboru-z-tochki-zoru-teoriyi-imovirnos

Готуємося до олімпіад з фізики   

Збірник олімпіадних  задач з  фізики
Блог задач з фізики та астрономії 
Олімпіади з фізики (Гончаренко)

Фізика 7 клас 

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 7 клас 2005р. 

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 7 клас 2008р. 

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 7 клас 2010р. 

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 7 клас 2011р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 7 клас 2012р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 7 клас 2013р.

Фізика 8 клас

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 8 клас 2005р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 8 клас 2008р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 8 клас 2010р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 8 клас 2011р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 8 клас 2012р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 8 клас 2013р.

Фізика 9 клас

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 9 клас 2005р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 9 клас 2008р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 9 клас 2010р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 9 клас 2011р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 9 клас 2012р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 9 клас 2013р.

Фізика 10 клас

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 10 клас 2005р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 10 клас 2008р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 10 клас 2010р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 10 клас 2011р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 10 клас 2012р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 10 клас 2013р.

Астрономія 10 клас

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 10 клас 2010р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 10 клас 2011р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 10 клас 2012р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 10 клас 2013р.

Фізика 11 клас

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 11 клас 2005р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 11 клас 2008р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 11 клас 2010р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 11 клас 2011р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 11 клас 2012р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з фізики 11 клас 2013р.

Астрономія 11 клас

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 11 клас 2010р.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 11 клас 2011р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 11 клас 2012р.
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з астрономії 11 клас 2013р.