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.

Подстраницы (1): методи розвязання олімпіадних задач

Комментарии

У вас нет прав для добавления комментариев.

Войти|Последняя активность сайта|Пожаловаться|Печать страницы|На основе Google С методи розвязання олімпіадних задач

2.1. Доказ від супротивного.

Один з часто використовуваних методів у доведенні. Його принцип полягає в тому, що доведення судження (тези) здійснюється через спростування суперечних йому суджень (антитези). Спростування антитези досягається встановленням факту того, що він не сумісний з якимось вже свідомо істинним судженням.

Доведення істинності твердження A проводиться наступним чином. Спочатку приймають, що судження A - помилкове. Потім доводять, що в такому випадку, деяке твердження B було б вірне (хоча воно свідомо невірне). Отримане протиріччя показує, що вихідне припущення було невірне (припущення, що А - помилкове). А тому твердження А - істинно за законом подвійного заперечення (¬ (¬ А) рівносильно А).

Приклад:

Довести, що - Ірраціональне число.

Доведення : Доведемо твердження від супротивного. Припустимо число

- раціональне. Тоді за визначенням раціонального числа, його можна представити у вигляді нескоротного дробу m/n, , де M ∈ Z , N ∈ N .

= m/n. . Піднесемо до квадрату:

3 = m2/n2.

m2 = 3n2.

m2 ділиться на 3, а значить і m ділиться на 3. Тоді m2 ділиться на 9. Раз так, то й n2 ділиться на 3, а тому і n ділиться на 3. Виходить - що дріб m/n скоротний. Ми прийшли до протиріччя вихідного судження (що число раціональне). Тому число - Ірраціональне.

2.2. Принцип Діріхле (комбінаторика)

У комбінаториці принцип - твердження, сформульоване німецьким математиком Діріхле в 1834 , що встановлює зв'язок між об'єктами («кроликами») і контейнерами («клітинами») при виконанні певних умов. У англійській та деяких інших мовах твердження відоме як «принцип голубів і ящиків», коли об'єктами є голуби, а контейнерами - пакети.

Принцип Діріхле застосовується, зокрема, в теорії діофантових наближень при аналізі систем лінійних нерівностей. [15]

Очевидний, простий у розумінні, але в той же час, досить потужний метод розв’язання завдань полягає в наступному: якщо A елементів розбиті на a групи, причому A > a , то хоча б в одній групі буде знаходиться більше одного елемента (A,а∈N). Даний принцип, що є однією з форм методу від супротивного і часто формулюється так: Якщо в n клітках сидить m зайців і m > n , то хоча б в одній клітці сидять більше одного зайця.

Головна мета у розв’язанні такого роду завдань - визначення "зайців" і "кліток" в даній конкретній задачі. Найчастіше - це найважчий етап у розвязанні, так як вибір не завжди очевидний.

Дуже цінним є те, що даний метод дає неконструктивне доведення (адже ми точно не можемо вказати, в якій саме клітці знаходяться більше одного зайця); на відміну від конструктивного, коли потрібно йти шляхом повної побудови або явно вказувати шуканий об'єкт, що часто призводить до значних труднощів і витрат часу.

Приклад:

Задача 1.1. Дано 7 різних натуральних чисел. Довести, що з них можна вибрати два числа, щоб їх різниця ділилася на 6.

Доведення : При розподілі на 6 існує шість різних залишків: 0, 1, 2, 3, 4, 5. Застосуємо принцип Діріхле. У даному випадку "клітками" будуть залишки, а "зайцями" - числа. Зайців 7, а чисел 6. Тому як мінімум два числа мають однакові залишки.

Нехай ці числа x і y ( x,Y∈N)

Тоді x = 6 p + r , а y = 6 q + r . А значить x - y = 6 ( p - q ).

Що і потрібно було довести.

Приклади

9 кліток містять 7 голубів, за принципом Діріхле хоча б одна клітина містить не більше 7/9 голуба (т.е нуль)

2.3. Метод розмальовки

Сенс даного методу полягає в наступному. Розфарбувавши деякі ключові елементи, які фігурують в задачі в кілька кольорів, досліджувати, що відбуватиметься, якщо виконувати умови задачі. Колір дозволяє значно спростити розуміння процесу, що фігурує в умові, і часто призводить до розв’язання . Цей метод дозволяє ефективно розв’язувати ряд задач, зокрема, ігрові та шахові задачі.

Приклад:

Задача 3.1 Дано квадрат паперу у клітинку розміром 8 x 8, з якого вирізані дві крайні діагональні клітки (верхня-права і нижня-ліва). Чи можна отриману фігуру покрити прямокутниками розміром 1 x 2?

Розв'язання: Розфарбуємо наш обрізаний квадрат за допомогою двох кольорів в шахову забарвлення. Зауважимо, що відрізані діагональні клітки будуть одного кольору. Відзначимо також, що в нашому розфарбованому квадраті будь-які сусідні дві клітини (що мають спільну сторону) будуть різного кольору. Це означає, що будь-який прямокутник розміром 1 x 2, яким ми будемо намагатися покрити обрізаний квадрат буде покривати клітини обох кольорів. І якщо ми зможемо покрити обрізаний квадрат прямокутниками 1 x 2, то буде покрито однакову кількість клітин з різними кольорами; тобто фігура повинна містити однакову кількість клітин обох кольорів. Але так як ми відрізали діагональні клітини одного кольору, то їх кількість в обрізаному квадраті на дві менше. Це означає, що ми не зможемо польностью покрити вказаний обрізаний квадрат прямокутниками 1 x 2.

2.4. Метод математичної індукції

Математична індукція - один з методів математичного ддоведення, використовується щоб довести істинність деякого твердження для всіх натуральних чисел . Для цього спочатку перевіряється істинність твердження з номером 1 - база (базис) індукції, а потім доводиться, що, якщо вірне твердження з номером n , то вірне і наступне твердження з номером n + 1 - крок індукції, або індукційний перехід . [1]

доведення по індукції наочно може бути представлено у вигляді так званого принципу доміно . Нехай яке завгодно число кісточок доміно виставлено в ряд таким чином, що кожна кісточка, падаючи, обов'язково перекидає наступну за нею кісточку (в цьому полягає індукційний перехід). Тоді, якщо ми штовхни першу кісточку (це база індукції), то всі кісточки в ряду впадуть. [2]

Сенс його полягає в наступному. Припустимо у нас є послідовність тверджень A1, A2, ... , An, An+1, ...,де n ∈ N. Всі твердження будуть істинними, якщо:

1) Буде доведена база індукції , тобто істинність твердження A1 ;

2) Буде доведений перехід , тобто для будь-якого n буде доведено, що якщо твердження An - вірне, то вірне і твердження An+1.

Приклад:

Задача 4.1.Довести, що якщо k ∈ N, то число k2 - k - парне.

Розв’язання : розв’яжемо задачу за допомогою методу математичної індукції.

Перевіримо базу індукції - при k = 1, k2 - k = 0 - число парне.

Доведемо перехід. Припустимо при деякому k = n , число n2 - n - парне. Доведемо, що k = n +1 число ( n + 1) 2 - ( n + 1) - теж парне. Але (n + 1)2 - (n + 1) = n2 + 2n + 1 - n - 1 = n2 + n = n2 - n + 2n. Число n2 - n - парне, згідно з припущенням і 2 n - парне. Сума парних чисел - парна. Перехід доведений.

Тому при будь-якому k ∈ N число k2 - k - парне.

Існують і інші варіації методу математичної індукції. Наприклад, є послідовність тверджень B1, B2, ... , Bn, Bn+1, ..., где n ∈ N. Всі твердження будуть істинними, якщо:

1) Буде доведена істинність твердження B1 ;

2) Для будь-якого n буде доведено, що якщо твердження B1, ... , Bn - вірні, то вірне і твердження Bn+1.

2.5. Контрприклад

Контрприклад - приклад, який спростовує вірність деякого твердження.

Побудова контрприклада - звичайний спосіб спростування гіпотез . Якщо є твердження типу «Для будь-якого X з множини M виконується властивість A», то контрприкладом для цього твердження буде:« Існує об'єкт X0 з множини M , для якого властивість A не виконується ».

Часто знайти контрприклад вручну дуже складно. У таких випадках можна скористатися комп'ютером . Програма для знаходження контрприклада може просто перебирати елементи множини M і перевіряти виконання властивості A . Більш складний, але і більш ефективний, підхід полягає в побудові контрприклада «по частинах». При цьому при виборі чергової «частини» відразу відкидаються варіанти, які свідомо не ведуть до спростування аналізованого твердження. Це дозволяє значно прискорити роботу, часто на порядки. [6]

Необхідно пам'ятати, що відсутність контрприклада не є доведенням гіпотези. Доведення такого роду можна будувати, тільки якщо розглянута множина скінченна. У цьому випадку, досить перебрати всі його елементи, і, якщо контрприклада серед них немає, то твердження буде доведено. [11]

2.6. Рекурсія

Візуальна форма рекурсії ( ефект Дросте )

Рекурсивне зображення екрану

Рекурсія - процес повторення елементів самоподібним чином. Наприклад, якщо два дзеркала встановити один навпроти одного, то виникають у них вкладені відображення суть одна з форм нескінченної рекурсії.

Термін « рекурсія »використовується в різних спеціальних галузях знань - від лінгвістики до логіки , але найбільш широке застосування знаходить в математиці і інформатиці . У математиці і інформатиці рекурсія має відношення до методу визначення функцій: рекурсивно задана функція у своєму визначенні містить себе, зокрема, рекурсивною є функція, задана рекуррентной формулою . Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через самого себе з використанням раніше заданих приватних визначень.

З рекурсією тісно пов'язана математична індукція: вона є природним способом доведення властивостей функцій на натуральних числах, рекурсивно заданих через свої менші значення.

У математиці

Треугольник Серпинского

2.7. Метод Гауса

Метод Гауса-Жордана для розв’язання систем лінійних алгебраїчних рівнянь є рекурсивним.

Приклад:

1.Факторіал цілого невід’ємного числа n(n!)визначається так:

при и при

2. Числа Фібоначчі визначаються за допомогою рекурентного співвідношення

Перше і друге числа Фібоначчі дорівнюють 1

Для , - є число Фібоначчі яке дорівнює сумі -го і -го чисел Фібоначчі.

Комментарии

Войти|Последняя активность сайта|Пожаловаться|Печать страницы|На основе Gайтов