Дистанційне навчання

Тема. У ЧОМУ ПОЛЯГАЄ ПРИНЦИП ДІРІХЛЕ?

У кожній сукупності з n множин, де загальна кількість елементів перевищує n, є принаймні одна множина, в якій міститься не менше ніж два елементи.  За традицією в популярній літературі принцип Діріхле пояснюють на прикладі «кроликів і кліток»: Якщо N кроликів сидять у п клітках і N> п, то хоча би в одній клітці сидить більше ніж один кролик. Часто застосовують узагальнення   принципу Діріхле: якщо кроликів N> пk, то хоча би в одній клітці сидять більше  ніж k кроликів. На цій ідеї побудовано доведення того, що під час перетворення звичайного дробу p/q (p<q, q>0) у десятковий одержуємо або скінчений, або нескінченний  періодичний десятковий, причому довжина періоду не перевищує q-1. Будемо ділити р на q «куточком» і стежити за остачами. Якщо на якому небудь  кроці остача буде нульовою, то дістанемо скінченний дріб. Якщо всі остачі  будуть відмінні від нуля, то не пізніше ніж на (q - 1 )- му кроці будуть   повторюватися остачі, а отже, і цифри у частці. Дев'ять кліток містять 10 голубів. За принципом Діріхле принаймні в одній клітці  сидить більш ніж один голуб. Дев'ять кліток містять сім голубів. За принципом   Діріхле принаймні  дві клітки вільні.

Тема. Подільність на m  Умова

На 2  Остання цифра числа ділиться на 2 (парна)

На 5  Остання цифра числа 0 або 5

На 10k Число закінчується на k нулів

На 4  Число, виражене двома останніми цифрами даного числа, ділиться на 4

На 8  Число, виражене трьома останніми цифрами даного числа, ділиться на 8

На 3  Сума цифр ділиться на 3

На 9  Сума цифр ділиться на 9

На 11  Різниця між сумою цифр, що стоять на непарних місцях (рахуючи справа наліво), і сумою цифр, що стоять на парних місцях, ділиться на 11.

Умова. Іван і Федір зробили по 5 пострілів по мішені, і влучили по 1 разу в круги 5, 8, 11, 12 і по двічі у круги 7, 9, 10. Відомо, що вони обидва влучили у круг 10.  Іван останніми 4-ма пострілами набрав у 7 разів більше очок, ніж першим. Хто з них влучив в круг 12?

Розв'язання. Припустимо, що Іван першим пострілом поцілив у круг 10. Тоді на останні 4 постріли припадає

            10 ∙ 7 = 70 > 41 = 12 + 11 + 9 + 9. Тут і далі праворуч від знаку нерівності вказано максимальну суму, яку залишається на останні 4 постріли при зробленому припущенні. Отримана суперечність свідчить про хибність припущення.

Аналогічно розглянемо гіпотези про влучення Іваном при першому пострілі у круги 12, 11, 9, 8, 7:

     12 ∙ 7 = 84 > 39 =11 + 10 + 9 + 9;

     11 ∙ 7 = 77 > 41 =12 + 10 + 9 + 9;

      9  ∙ 7 = 63 > 42 =12 + 11 + 10 + 9;

      8 ∙ 7 = 56 > 42 =12 + 11 + 10 + 9;

      7 ∙ 7 = 49 > 42 =12 + 11 + 10 + 9.

            Всі з перелічених варіантів суперечать умові задачі. Отже, Іван першим пострілом влучив у круг 5: 7 ∙ 5 = 35 = 10 + 25

            25 можна подати сумою трьох чисел з набору  8, 11, 12, 7,  7,  9,  9 лише 2-ма способами:

            25 = 11 + 7 + 7 = 9 + 9 + 7.

            Число 12 таке подання не містить.

Приклад 1. Задача ЛьюЇса Керрола. У жорстокому бою 70 зі 100 піратів запорошили око; 75 – оцарапали  вухо; 80 – порізали палець, а 85 – підвернули ногу. Яке найменше і яке найбільше число могло бути тих, хто дістав одночасно усі чотири ушкодження?

Око і ухо принаймні 70 + 75 – 100 = 45

Палець принаймні  45 + 80 – 100 = 25

Одночасно усі чотири «поранення» мають принаймні 25 + 85 – 100 = 10.

Максимальна кількість 70.

Відповідь: найменше число – 10, найбільше – 70.

 Тема. Цікаві задачі та конструкції

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

Серед таких задач є й такі, в яких потрібно доводити неможливіть потрібної конструкції. Це робиться, як правило, методом від супротивного. Є й такі задачі, в яких потрібно побудувати «найкращу» конструкції данного виду. Тут потрібно не тільки запропонувати конструкцію, я й довести, що «покращити» її не можна.

1. Як відміряти 15 хвилин, щоб зварити яйця, за допомогою пісочних годинників, які відмірюють 7 хвилин та 11 хвилин? Так. Назвемо пісочний годинник, який відміряє 11 хв, годинником А, а 7 хв – годинником В. Кладемо одночасно годинники А і В. Коли мине 7 хв (годинник В), ставимо кастрюлю на вогонь. Годиннику А залишилось «йти» 4 хв, після цього його превертаємо і через 11 хв знімаємо кастрюлю. 

Тема. ЗАДАЧІ НА ПАРНІСТЬ. ЧЕРГУВАННЯ. РОЗБИТТЯ НА ПАРИ 

1.      Кінь вийшов з поля а1 і через декілька ходів повернувся на нього.
Доведіть, що він зробив парну кількість ходів.

Розв'язання

З кожним ходом коня міняється колір поля, на якому стоїть кінь, тоб­то має місце чергування кольорів — білого і чорного. Після першого ходу кінь стоятиме на білому полі, а після останнього — на чорному полі а1. Отже, кінь має зробити парну кількість ходів.

2.      На площині розміщені 11 зубчатих коліс, з'єднаних у вигляді замк­нутого ланцюжка. Чи зможуть вони всі обертатись одночасно?

Розв'язання

Пронумеруємо всі колеса в порядку обходу їх уздовж ланцюжка числа­ми від 1 до 11. Нехай перше колесо обертається за годинниковою стрілкою. Тоді всі колеса з непарними номерами будуть обертатися за годинниковою стрілкою, а всі колеса з парними номерами — проти годинникової стрілки. Зауважимо, що будь-які два сусідні колеса повинні обертатися в протилеж­них напрямках. Але перше й одинадцяте колеса — сусідні, обертаються в одному напрямку. Протиріччя показує, що всі зубчаті колесі обертатись одночасно не можуть.

3.      Чи може пряма, що містить вершини замкненої 11-ланкової лама­ної, перетинати всі її ланки?

Розв'язання

Будемо обходити контур ламаної, переходячи з кожної вершини в наступну. При цьому кожного разу, коли будемо перетинати пряму, ми попадатимемо в іншу півплощину відносно цієї прямої. Отже, має місце чергування. Тому, щоб обійти контур ламаної і повернутися в початкову вершину, треба перетнути парну кількість ланок, але їх кількість непарна. Тому відповідь на питання задачі негативна.

4.      Катруся та її друзі стали в коло. Виявилось, що обидва сусіди в кож­ної дитини однієї статі. Хлопчиків серед Катрусиних друзів п'ять. А скіль­ки дівчаток?

Розв'язання

Якщо в когось із Катрусиних друзів сусіди – тієї ж статі, то очевидно, що всі, хто стоїть у колі, однієї статі. Тому хлопчики та дівчатка чергуються і, отже, дівчаток у колі стоїть стільки ж, скільки й хлопчиків: по п'ять. Отже, серед Катрусиних друзів є чотири дівчинки.

5.      Дано осьосиметричний опуклий 101-кутник. Доведіть, що вісь си­метрії проходить через одну з його вершин.

Розв'язання

Якщо вісь симетрії не проходить через вершину, то дані 101 точка по­винні розбиватися на пари симетричних, що неможливо.

6.      Чи можна опуклий 13-кутник розрізати на паралелограми?

Розв'язання

Якщо опуклий многокутник можна розрізати на паралелограми, то його сторони обов'язково розбиваються на пари паралельних. Але 13 сто­рін не можна розбити на пари. Тому таке розрізання неможливе.

Тема. математична індукція

1. Повна і неповна індукція

В основі всякого математичного дослідження лежать дедуктивний і індуктивний методи. Дедуктивний метод міркувань – це міркування від загального до частинного, тобто міркування, вихідним моментом якого є загальний результат, а заключним моментом – частинний результат. У математиці застосовуємо дедуктивний метод, проводячи міркування такого типу: дана фігура – прямокутник, а в кожного прямокутника діагоналі рівні, отже, і в даного прямокутника діагоналі рівні.

По своєму первісному змісті слово «індукція» застосовується до міркувань, за допомогою яких одержують загальні висновки, спираючи на ряд частинних тверджень. Найпростішим методом міркувань такого роду є повна індукція. От приклад подібного міркування.

Нехай потрібно установити, що кожне парне натуральне число n у межах 4£n£20 можна представити у виді суми двох простих чисел. Для цього візьмемо всі такі числа і випишемо відповідні розклади:

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5; 14=7+7; 16=11+5; 18=11+7; 20=13+7.

Ці 9 рівностей показують, що кожне чисел, що нас цікавлять, дійсно представляється у виді суми двох простих.

Таким чином, повна індукція полягає в тому, що загальне твердження доводиться по окремості в кожному з кінцевого числа можливих випадків.

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

Нехай, наприклад, потрібно знайти суму перших n послідовних непарних чисел. Розглянемо окремі випадки:

1=1=1²;

1+3=4=2²;

1+3+5=9=3²;

1+3+5+7=16=4²;

1+3+5+7+9=25=5².

Після розгляду цих деяких окремих випадків напрошується наступний загальний висновок:

1+3+5+...+(2n-1)=n²,

тобто сума n перших послідовних непарних чисел дорівнює n².

Зрозуміло, зроблене спостереження ще не може бути доказом справедливості приведеної формули. Далі ми познайомимося з методом, користаючись яким, можна довести, що ця формула вірна.

2. Помилки в індуктивних міркуваннях

Наведемо приклади того, як індуктивні міркування призводять до помилкових висновків.

1. Різниця двозначного числа і числа, записаного тими ж цифрами, але в зворотному порядку, ділиться націло на 9. Різниця тризначного числа і числа, записаного тими ж цифрами, але в зворотному порядку, ділиться на 99. Виникає припущення про те, що різниця чотиризначного числа і числа, записаного тими ж цифрам, але в зворотному порядку, розділиться на 999. Це, однак, невірно, наприклад, 2231-1322 = 909, але 909 не поділяється на 999.

2. Розглядаючи числа виду 2² +1, французький математик П. Ферма помітив, що при n=1, 2, 3, 4 виходять прості числа. Він припустив, що всі числа такого виду – прості. Однак Л. Эйлер знайшов, що вже при n=5 це невірно: число 2³²+1 не є простим - воно ділиться на 641.

3. Розглянемо ще один приклад. Підставляючи в квадратний тричлен P(x)=x²+x+41 замість x натуральні числа 1, 2, 3, 4, 5, знайдемо: P(1)=43, P(2)=47, P(3)=53, P(4)=61, P(5)=71. Всі отримані значення даного тричлена є простими числами. Підставляючи замість x числа 0, -1, -2, -3, -4, одержимо: P(0)=41, P(-1)=41, P(-2)=43, P(-3)=47, P(-4)=53. Значення даного тричлена при зазначених значеннях змінної x також є простими числами. Виникає гіпотеза, що значення тричлена P(x) є простим числом при будь-якому цілому значенні x. Але висловлена гіпотеза помилкова, тому що, наприклад, P(41)=41²+41+41=41· 43.

4. Знаменитий німецький математик XVII ст., один із творців вищої математики, Г.В. Лейбніц довів, що при всякому цілому додатному n число n³-n ділиться на 3, число n⁵-n ділиться на 5, число n⁷-n ділиться на 7. На підставі цього він припустив, що при всякому непарному k і будь-якому натуральному n число n^k-n ділиться на k, але незабаром сам помітив, що 2⁹-2=510 не ділиться на 9.

5. Потрібно з'ясувати, чи існує таке натуральне число n, що число виду 991n²+1 є точним квадратом. Розглядаючи часткові випадки при n = 1, 2, 3, 4, ..., ми будемо одержувати числа, що не є точними квадратами. Якби ми робили обчислення для послідовних натуральних чисел, то щораз одержували би числа, що не є точними квадратами. Цілком природно припустити, що при всіх натуральних n числа виду 991n²+1 не є точними квадратами. Однак це невірно: за допомогою обчислювальної машини було знайдено 29-значне число m таке, що число 991m²+1 виявилося точним квадратом.

Розглянуті приклади дозволяють зробити простий і в той же час важливий висновок: неповна індукція може привести до помилки. Однак важливо підкреслити, що вона іноді приводить до істини, хоча можливість помилки виключати не можна. Твердження може бути справедливим у цілому ряді окремих випадків і в той же час несправедливим узагалі.

3. Принцип математичної індукції

Повна індукція має в математиці лише обмежене застосування. Багато цікавих математичних тверджень охоплюють нескінченне число окремих випадків, а провести перевірку для нескінченного числа випадків людина не може (прикладом такого твердження може служити будь-як твердження, що відноситься до всіх натуральних чисел). Неповна ж індукція, як ми бачили, часто приводить до помилкових результатів.

У багатьох випадках вихід з такого роду утруднень полягає в звертанні до особливого методу міркувань, що називають методом математичної індукції. Він полягає в наступному.

Нехай потрібно довести справедливість деякого твердження для будь-якого натурального числа n (наприклад, потрібно довести, що сума перших n непарних чисел дорівнює n²). Безпосередня перевірка цього твердження для кожного n неможлива, оскільки множина натуральних чисел нескінчена. Щоб довести це твердження, перевіряють спочатку його справедливість для n=1. Потім доводять, що при будь-якому натуральному значенні k зі справедливості розглянутого  твердження при n=k випливає його справедливість і при n=k+1. Тоді твердження вважається доведеним для всіх n. Справді, твердження справедливе при n=1. Але тоді воно справедливо і для наступного числа n=1+1=2. Зі справедливості твердження для n=2 його справедливість для n=2+1=3. Звідси, у свою чергу, випливає справедливість твердження для n=4 і т.д. Ясно, що зрештою ми дійдемо до будь-якого натурального числа n. Виходить, твердження вірне для будь-якого n.

Узагальнюючи сказане, сформулюємо загальний принцип.

Принцип математично ї індукції. Якщо речення А (n), що залежить від натурального числа n, істинно для n=1 з того, що воно істинно для n=k (де k - будь-яке натуральне число), випливає, що воно істинно і для наступного числа n=k+1, то А (n) істинно для будь-якого натурального числа n.

4. Узагальнення принципу математичної індукції

 У ряді випадків буває потрібно довести справедливість деякого твердження не для всіх натуральних чисел, а лише для n ³ p, де p - фіксованої натуральне число. У цьому випадку принцип математичної індукції формулюється в такий спосіб.

Якщо речення А (n) істинно при n=р і якщо А (k)ÞА (k+1)для будь-якого k³р, то А (n) істинно для будь-якого n³р.

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

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

 Доведення по методу математичної індукції проводитися в такий спосіб. З початку доказуване твердження перевіряється для n=1, тобто встановлюється істинність висловлення А (1). Цю частину доведення називають початком або базисом індукції. Потім йде частина доведення, що називається індукційним кроком. У цій частині доводять справедливість твердження для n=k+1 у припущенні справедливості твердження для n=k (припущення індукції), тобто доводять, що А (k)ÞА (k+1). Уперше такий спосіб запропонували Б. Паскаль і Я. Бернуллі.

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

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

6. Приклад доведення методом математичної індукції

1. Доведіть, що число, яке складається з 243 одиниць, ділиться на 243.

Розв’язування:

Помітимо, що 243 = 3⁵. Спробуємо довести більш загальне твердження, що число, складене з 3ⁿ одиниць, поділяється на Зⁿ. Виявляється, це простіше. Для n = 1 твердження вірне (111 поділяється на 3). Помітимо, що 111111111 = 111 • 1001001, і взагалі число з 3ⁿ одиниць розкладається на множники:

I ... 1  = 1 ... 1 *10...010... 01

причому, другий множник ділиться на 3 (по ознаці подільності на 3).

 Отже, у послідовності чисел 111,  111111111, ..., «3ⁿ одиниць» кожне наступне дорівнює попередньому, помноженому на число, кратне трьом. Тому, якщо 1...1  ділиться на  3^n-1, то і 1...1 ділиться на 3ⁿ. 

Тема. ЗАДАЧІ НА ФАРБУВАННЯ

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

Є задачі в яких розфарбування вже задано. А  є задачі,  умова яких не містить фарбування, проте ідея певного розфарбування допомагає розв’язати задачу.

                              1.  Чи може кінь пройти з поля А-1 шахівниці на поле Н-8, побувавши по дорозі на кожному з решти полів по одному разу?     

Розв`язання

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

Тоді після 63-ого кроку маємо білу клітинку, а Н-8 – чорна. Отже,  він не зможе опинитись на у клітинці  Н-8.

Відповідь : ні.

                         2.  У кожній клітинці дошки 5х5 сидить жабенятко. По команді жабеняти плигають на сусідні клітинки. При тому сусідніми вважаються клітинки, що мають спільну сторону. Доведіть, що при цьому принаймні одна клітинка залишиться порожньою .

Доведення.

Розмалюємо дошку 5х5 в шаховому порядку.  Нехай в результаті цього отримали 13 клітинок чорного та 12 білого кольору.

Коли жабенята плигають – вони змінюють колір клітинки. Тому 12 жабенят, які знаходилися спочатку в клітинках білого кольору, не зможуть зайняти всі 13 клітинок чорного кольору.                

3. У кожній клітинці дошки 5х5 сидить жабенятко. По команді жабеняти плигають на сусідні клітинки. При тому сусідніми вважаються клітинки, що мають спільну вершину. Доведіть, що при цьому завжди залишаться порожні клітинки. Скільки  клітинок обов’язково залишаться вільними?

  Доведення.

Розмалюємо дошку 5х5 рядочками. Маємо 15 чорних і 10 білих клітинок. Тому 10 жабенят, які знаходилися спочатку в клітинках білого кольору, не зможуть зайняти всі 15 клітинок чорного кольору. Хоча б 5 клітинок залишаться вільними.                  

4. Мишка гризе куб сиру, складений із 27 одиничних кубиків. З`ївши один кубик, вона переходить до сусіднього з ним через спільну грань. Чи може мишка з`їсти в такий спосіб увесь куб, окрім центрального кубика?

Розв`язання

Розмалюємо кубики у два кольори так, щоб кожні два сусідні кубики, що мають спільну грань, були різного кольору. Кубиків, колір яких співпадає із кольором центрального кубика, буде 13, а кубиків другого кольору – 14.

Дотримуючись умови задачі, мишка почергово мінятиме кольори з`їдених кубиків, а тому серед 26 таких кубиків буде по 13 кубиків кожного кольору. Тому центральний кубик залишитися не може.

Відповідь : ні.

5.       Дно коробки розміром 10х10 вимощене плитками розміром 1х4 та 2х2. Одну з цих плиток розміром 1х4 загубили, але в запасі є плитка розміром 2х2. Чи можна наявними плитками знову вимостити дно коробки?

Розв`язання

         Розіб`ємо дно коробки на квадрати  та зафарбуємо деякі клітинки так, як показано на малюнку

Тоді кожна плитка 2х2 покриває рівно одну зафарбовану , а кожна плитка 1х4 покриває дві або жодної з пофарбованих клітинок. Оскільки зафарбованих клітинок 25, то для вимощення дна коробки потрібно непарну кількість плиток 2х2. Тому нове вимощення дна коробки неможливе.

         Відповідь: ні.

6. Кожну грань кубика поділили на 4 квадрати, кожний з отриманих квадратів  пофарбували в один з кольорів - червоний, синій, зелений – так, щоб квадратики, що мають спільну сторону, були пофарбовані в різні кольори. Доведіть, що при цьому обов’язково буде 8 синіх, 8 червоних і 8 зелених квадратиків.

Доведення

Розглянемо 8 квадратиків, що мають за спільну вершину – вершину кубика. За умовою всі вони повинні бути різних кольорів. Звідси випливає твердження задачі.