Принцип Діріхле.
Наведемо жартівливе формулювання принципу Діріхле.
ПРИНЦИП ДІРІХЛЕ. «Якщо по n ящикам розсадити більше n кроликів, то знайдеться ящик, в якому сидить більше одного кролика» або «Якщо в n ящиках більше nk кроликів, то принаймі в одному ящику більше k кроликів».
Принцип Діріхле використовують при розв’язуванні різних задач пов’язаних з проблемою існування. Розв’язання відбувається двома способами: або очевидно подаються в конкретній задачі «кролики» і «ящики», або доведення йдеться від супротивного.
УЗАГАЛЬНЕНИЙ ПРИНЦИП ДІРІХЛЕ. «Якщо в n ящиках сидить не менше nk+1 кроликів, то принаймі в одному ящику сидить більше k кроликів».
Задача 1. У школі 20 класів. В найближчому будинку живуть 23 учні цієї школи. Чи можна стверджувати, що серед них знайдуться хоча б двоє однокласників?
Розв’язання: оскільки класи утворюють n = 20 груп, а учнів 23 > n, то принаймі в одній групі буде не менше двох однокласників.
Задача 2. У ящику лежать 105 яблук чотирьох сортів. Довести, що серед них принаймі 27 яблук одного сорту.
Доведення: сорти яблук утворюють n = 4 групи. Якщо кожного сорту взяти по k = 26 яблук,
то nk = 4×26 = 104 < 105. Очевидно, що одного з сортів буде 27 яблук.
Задача 3. На 5 полках шафи стоять 160 книг. На одній з них – 3 книги. Доведіть, що знайдеться полка, на якій стоїть не менше 40 книг.
Доведення: (від супротивного) Якщо такої полки не має, тоді на 5 полках 3+4×39=159 книг, але це суперечить умові задачі, оскільки маємо 160 книг, тому на одній з полиць40 книг.
Задачі для розв’язування:
1. В коробці лежать 4 червоних і 2 зелених кульки. Яке найменше число кульок необхідно витягнути, щоб серед них виявилося: а) одна червона кулька; б) одна зелена кулька; в) одна червона і одна зелена кулька; г) дві кульки одного кольору.
2. В коробці лежать 100 різнокольорових кульок: 28 червоних, 20 зелених,12 жовтих, 20 синіх, 10 білих і 10 чорних. Яке найменше число кульок необхідно витягнути, щоб серед них виявилося 15 кульок одного кольору?
3. В одному районі 7 шкіл. На район виділили 20 комп’ютерів. Довести, що при будь-якому розподілі їх між школами знайдуться дві, які отримають однакову кількість комп’ютерів (можливо, жодного).
4. 34 пасажири їдуть в автобусі, який зупиняється на 9 зупинках, і ніякі нові пасажири на жодній з них не входять. Доведіть, що на двох зупинках вийде однакова кількість пасажирів.
5. Якій мінімальній кількості школярів можна роздати 200 цукерок, щоб серед них при будь-якому розподілі знайшлися двоє, які отримають однакову кількість цукерок (можливо, жодної).
6. 100 книг розподілили між деякими учнями. При якій мінімальній кількості учнів це можливо зробити таким чином, що всі вони отримають різну кількість книг?
7. Довести, що серед будь-яких 9 натуральних чисел знайдуться два таких числа, які при діленні на 8 дають однакові остачі.
8. Довести, що серед будь-яких n+1 натуральних чисел знайдуться два таких числа, різниця яких ділиться на n.
9. Чи дійсно, що серед будь-яких семи натуральних чисел знайдуться три, сума яких ділиться на три?
10. Доведіть, що серед будь-яких трьох цілих чисел можна знайти два, сума яких парна.
2. Комбінаторика.
КОМБІНАТОРИКОЮ називають галузь математики, яка вивчає питання пов’язані з визначення кількості різних комбінацій, за даних умов, з заданих об’єктів. Більшість задач розв’язуються за допомогою двох основних правил – правило суми та правило добутку.
ПРАВИЛО СУМИ. Якщо об’єкт А можна вибрати m способами, а об’єкт В – n способами, то об’єкт А або В можна вибрати m+n способами.
ПРАВИЛО ДОБУТКУ. Якщо об’єкт А можна вибрати m способами і після кожного такого вибору об’єкт В можна вибрати n способами, то пару об’єктів А і В можна вибрати m×n способами.
Задача 1. З міста А до міста Б ведуть дві дороги, з міста А в місто Г – чотири дороги, з Б в В – три дороги, з Г в В – п’ять. а) Скільки різних доріг ведуть з А в В через Б? б) Скільки взагалі різних доріг з А в В?
Розв’язання: а) за правилом добутку 2×3=6. б) Розглянемо два випадки: шлях проходить через Б і через Г. В першому випадку за правилом добутку маємо 2×3=6, в другому - 4×5=20доріг. За правилом суми 20+6=26 доріг.
Задача 2. Скількома способами можна вибрати чотирьох чергових з 30 учнів класу.
Розв’язання: першого чергового можна вибрати 30, другого – 29, третього – 28, четвертого – 27 способами.Отже, всього 30×29×28×27=657720 способів.
Задача 3. З трьох підручників алгебри, семи підручників геометрії і п’яти підручників фізики необхідно вибрати комплект з трьох підручників. Скількома способами це можна зробити?
Розв’язання: За правилом добутку:3×7×5=105 способів.
Задача 4. В магазині є 6 примірників олімпіадних задач з математики, 3 з фізики і 4 з біології. Крім того, є 5 комбінованих примірників з математики і фізики і 7 – з фізики і біології. Скількома способами можна придбати примірник, який містить задачі з одного предмету.
Розв’язання: Можна придбати або примірник з кожного предмету або примірник з двох предметів і примірник з одного. За правилами добутку і суми отримаємо 6×3×4+5×4+7×6=134 способи.
Задачі для розв’язування:
1. Скількома способами можна вибрати одну голосну і одну приголосну зі слова а) «місто»; б) «молоко»; в) «математика»?
2. На вершину гори ведуть п’ять доріг. Скількома способами турист може піднятися на гору і спуститися з неї? А якщо спуск і підйом відбуваються різними шляхами?
3.Скільки серед натуральних чисел від 10 до 1000 таких, що
а)в запису зустрічаються рівно три однакові цифри? б)кожна наступна цифра більша за попередню? в)сума цифр дорівнює 9?
4.Скільки існує двозначних чисел, у яких: а)серед цифр є хоча б одна п’ятірка? б)цифра десятків менша за цифру одиниць? в)цифра десятків більша цифри одиниць?
5. З 12 слів чоловічого роду, 9 жіночого, 10 середнього роду необхідно вибрати по одному слову кожного роду. Скількома способами можна це зробити?
6. На канікулах 75% учнів відпочивали на морі, 57% - відпочивали у горах. Відомо, що кожен був або на морі або у горах. Скільки відсотків учнів були і на морі і у горах?
7. У класі 32 учні. В хореографічному гуртку займаються 28 учнів, хоровим співом – 14, не відвідують жодного гуртка 3 учні. Скільки дітей займаються і в хореографічному гуртку, і хоровим співом?
8. Одного разу на канікулах Андрійко не зміг вийти на вулицю, тому що на вулиці 70% часу йшов дощ. Він вирішив пограти зі своїм молодшим братиком, приблизно 55% часу, а також у кімнаті працював телевізор – 80% всього часу. Яку найменшу частину часу це відбувалося одночасно?
9. На клумбі розквітли 18 троянд. Скількома способами можна скласти букет із трьох троянд?
10. Скількома способами із 7 членів комісії можна обрати голову та його заступника?
Переливання.
Задачі на переливання допоможуть розвивати логічне мислення, просторову уяву, витримку, наполегливість у знаходженні оптимального розв’язку. Пропоную розглянути розв’язання деяких задач.
Задача 1. Як за допомогою 3-літрового і 5-літрового відер набрати 1 літер води? У нашому розпорядженні є водопровідний кран і раковина, куди можна виливати воду.
Розв’язання: Розв’язання цієї задачі можна записати у вигляді таблиці. Спочатку обидва відра порожні. Наповнюємо 3-літрове відро і виливаємо воду з нього у 5-літрове. Знову наповнюємо 3-літрове відро і виливаємо її у 5-літрове, поки воно не наповниться. У
3-літровому відрі залишиться 1 літр води.
| 3 літри | |||||
| 5 літрів |
Задача 2. Маємо дві ємності 5 і 7 л. Як за допомогою ємностей відміряти 6 л води з крана?
Розв’язання: Складемо таблицю розв’язання:
| 7 л | ||||||||||
| 5 л |
Задача 3. Маємо три ємності: 9 л, 5 л, 3 л. Перша наповнена водою,а інші дві порожні. Як за допомогою цих ємностей відміряти 1 л води? Як відміряти 4 л води?
Розв’язання:
| 3 л | ||||
| 5 л | ||||
| 9 л |
Задача 4. У трьох купках лежать 22, 14 і 12 горіхів. За допомогою трьох перекладань зрівняйте кількість горіхів у купках.
Розв’язання: Оскільки горіхів всього 48, то в кожній купці повинно опинитися по 16. Перекладати з однієї купки в іншу можна стільки горіхів, скільки їх є в купці в яку перекладають. Схематично перекладання можна показати так:
(22,14,12) — (8,28,12) — (8,16,24) — (16,16,16).
Задачі для розв’язування:
1. В бочці міститься не менше 13 відер пального. Як відлити з неї 8 відер за допомогою 9-відерної і 5-відерної бочок?
2. В бочці не менше 10 л бензину. Як відлити з неї 6 л за допомогою дев’ятилітрового відра і п’ятилітрового бідона?
3. Бідон ємністю 10 л наповнений молоком. Необхідно перелити з цього бідона 5 л у семилітровий, використовуючи при цьому бідон місткістю 3 л. Як це зробити?
4. В трьох купках лежать 11, 7, 6 сірників відповідно. Дозволено перекладати з однієї купи до іншої стільки сірників, скільки там вже є. Як за три перекладання зрівняти кількість сірників у всіх купах?
5. Є два піщаних годинника: на 7 хвилин і на 11 хвилин. Яйце повинно варитися 15 хвилин. Як зварити яйце, перевертаючи годинники мінімальну кількість разів?
6. В одній склянці налито 5 ложок чаю, а в другій 5 ложок молока. Ложку молока перелили з другого стакана в перший, потім старанно розмішали і ложку чаю з молоком перелили знову в другий стакан. Чого тепер більше: чаю в другій склянці чи молока в першій? Як зміниться відповідь, якщо таке переливання виконати 10 разів?
7. Дехто з повної склянки кофе випив половину і долив стільки ж молока. Потім випив третю частину отриманого кофе з молоком і долив стільки ж молока. Нарешті, відпив шосту частину отриманого напою і долив стільки ж молока. Тільки після цього він випив все до кінця. Чого випито більше: кофе чи молока?
Зважування.
Умови наступних запропонованих задач легко змінювати (монети на камінці, пакети, каміння і т.д), отримуючі нові, що допомагає вчителю закріпити у учнів розуміння ідеї розв’язання.
Задача 1. Маємо n однакових монет, з яких одна фальшива (легша за вагою). Як за допомогою шальових терезів без гир знайти фальшиву монету за найменшу кількість зважувань, якщо
a) n=3; б) n=9; в) n=27; г) n- довільне число.
Розв’язання: г) При кожному зважуванні монети ділять на 3 групи, з яких 2 кладуть на терези і визначають в якій з груп знаходиться фальшива монета. Процес повторюють в залежності від кількості монет.
Задача 2. Серед чотирьох монет є одна фальшива, як знайти її за 2 зважування на шальових терезах без гир? Чи можна при цьому з’ясувати легша вона чи важча?
Розв’язання: Позначимо монети a, b, c, d. Першим зважуванням порівнюємо вагу a і b. Нехай
a ≠b (наприклад, a < b). Тоді c і d – справжні, а фальшива a чи b. Для визначення порівнюємо
a і с. Якщо a = с, то b фальшива і важча, оскільки a < b. Якщо a ≠ с, то фальшива a, при чому одразу з’ясовуємо, важча вона чи легша. Аналогічно поступаємо, якщо a = b.
Задача 3. Маємо 6 однакових за виглядом монет, чотири з них справжні, а дві фальшиві: обидві легші за справжні, але їх маса різна. За три зважування на шальових терезах без гир знайдіть обидві фальшиві монети.
Розв’язання: Позначимо вагу монет a 1 ,… a 6. Першим зважуванням порівнюємо a 1 і a 2 .
Випадок 1 a 1= a 2. Тоді a 1 і a 2 справжні. Порівнюємо a 3 і a 4, якщо a 3 = a 4, тоді a 5 і a 6 – фальшиві. Якщо a 3 < a 4, то одна з фальшивих a 3, а друга знаходиться серед 4, 5 і 6 (вона визначається порівнянням a 4 і a 5 ). Випадок a 3 > a 4 аналогічний.
Випадок 2 a 1 < a 2 – монета а1 фальшива. Друга фальшива монета визначається порівнянням монет 1 і 3 та монет 4 і 5 (якщо при одному зважуванні нерівність, то легша монета фальшива. Інакше фальшива монета - 6). Випадок а1 > a2 подібний до випадку 2.
Задачі для розв’язування:
1. Маємо чотири камінці різної маси. За яку найменшу кількість зважувань на терезах без гир можна знайти найважчий і найлегший камінь?
2. Маємо чотири пакети різної маси і правильні шальових терези без гир. Як за п’ять зважувань розкласти пакети в порядку зростання їх маси?
3. З 21 монети 10 справжніх і 11 фальшивих, причому кожна фальшива на 1 гр легша за справжню. Взяли одну з монет, як за одне зважування на терезах зі стрілкою визначити чи фальшива монета?
4. Маємо 6 однакових за виглядом монет, чотири з них справжні, по 4 г кожна, а дві - фальшиві: вагою 5 г і 3 г. За чотири зважування на шальових терезах без гир знайдіть обидві фальшиві монети.
5. Серед 18 монет одна фальшива, причому фальшива відрізняється за масою від справжніх. За яку найменшу кількість зважувань на правильних шальових терезах без гир можна визначити легша чи важча від справжніх фальшива монета?
6. Як зважити груз на шальових терезах з гирями,якщо гирі правильні, а терези не правильні.
7. а) Маємо 4 камені різної маси. За яку найменшу кількість зважувань можна знайти найлегший і найважчий камінь?
б) Розв’язати задачу для 6-ти каменів.
5. Подільність чисел.
Розв’язання наступних задач ґрунтується на основній теоремі арифметики: кожне натуральне число, крім одиниці, розкладається добуток простих множників, причому єдиним чином.
Задача 1. Чи ділеться 29 ∙ 3 на 6?
Розв’язання: Так, тому що 6 = 2 ∙ 3, а числа 2 і 3 ходять розкладання числа 6 на прості множники.
Задача 2. Чи дійсно, що якщо натуральне число ділиться на 4 і на 3, то воно ділиться на 12?
Розв’язання: Так. В розкладанні на прості множники числа, що ділиться на 4, двійка входить двічі
Задача 3. Чи дійсно, що якщо натуральне число ділиться на 4 і на 6, то воно ділиться на 24?
Розв’язання: Ні. Наприклад, число 12. Якщо число ділиться на 4, то в його розклад двійка входить двічі; з подільності на 6 – в його розкладі числа 2 і 3. Таким чином, однозначно можна стверджувати, що в розкладі даного числа є дві двійки і трійка, тобто число ділиться на 12.
Задача 4. Число А – парне. Чи ділиться число 3А на 6?
Розв’язання: Так. Оскільки число А парне, в його розклад входить число 2. Тому до розкладу числа 3А входять числа 2 і 3.
Задача 5. Число 15А ділиться на 6. Чи ділиться число А на 6?
Розв’язання: Ні. Наприклад А=2. Трійка, яка входить до розкладу числа 6, входить і до розкладу числа 15. Тому можна стверджувати лише, що до розкладу числа А входить число 2.
Задачі для розв’язування:
1. Довести, що добуток трьох послідовних натуральних чисел ділиться на 6.
2. Довести, що добуток п’яти послідовних натуральних чисел ділиться: а) на 30; б) на 120.
3. Позначимо через ab число з цифрами a і b. Довести, що число ab+ba ділиться на 11.
4. Миколка і Сашко купили однакові м’ячі. Скільки коштує один м’яч, якщо Миколка сплатив три- гривневими купюрами, а Сашко – п’яти-гривневими купюрами, а всього вони віддали в касу менше 10 купюр?
5. Знайти чотири таких натуральних числа, що добуток будь-яких трьох з них доданий до одиниці, ділився на четверте.
6. Знайти чотири різних цілих числа таких, що сума будь-яких трьох з них ділиться на четверте.
7. Довести, що число ababab ділиться на 7, 13, 37.
8. Щоб дізнатися, чи є число 1601 простим, його стали послідовно ділити на 2, 3, 5 і т.д. На якому простому числі можна зупинити випробування?
9. а) a+1 ділиться на 3. Довести, що число 4+7a ділиться на 3.
б) 2+a і 35-b ділиться на 11. Довести, що a+b ділиться на 11.
Стратегії. Ігри двох осіб.
Математичні ігри відрізняються від звичайних тим, що в них завчасно можна визначити результат гри. В подібних задачах зазвичай одне і те саме запитання: хто і я к переможе,при найкращий стратегії обох сторін. Для доведення перемоги або нічиїй використовуються наступні ідеї:
Відповідність. Наявність вдалого відповідного ходу (може забезпечуватися симетрією,розбиттям на пари, доповненням числа).
Розв’язання з кінця. Послідовно визначаються позиції перемоги та поразки для починаючого. Наступна позиція є переможною, якщо з неї можна отримати завчасно визначену позицію поразки і є поразкою, якщо будь-який хід з неї веде до завчасно визначеної позиції перемоги.
Передача ходу. Якщо ми можемо скористуватися стратегією супротивника, то наші справи не гірші,ніж у нього. Наприклад, перемога (або нічия) забезпечується, коли можна за своїм бажанням потрапити в деяку позицію, або примусити супротивника потрапити до неї.
В деяких задачах стратегію гри не вказують, оскільки результат гри не залежить від гри супротивників.
Задача 1. Двоє грають в наступну гру. Є 3 купки камінців: в першій – 10,в другій – 15, в третій -20. За хід дозволяється розбити будь-яку купку на 2 менші. Програє той, хто не зможе зробити хід.
Розв’язання: Після кожного ходу кількість купок збільшується на одну. Спочатку їх було 3, в кінці – 45. Таким чином, всього буде зроблено 42 хода. Останній, 42-й, хід зробить 2-ий гравець.
Задача 2. На дошці написані 10 одиниць і 10 двійок. За хід можна витерти дві будь-які цифри і, якщо вони були однакові, написати 2, якщо різні – 1. Якщо остання цифра що залишилася на дошці – 1, то перемагає перший гравець, якщо - 2, то другий.
Розв’язання: Парність числа одиниць на дошці після кожного ходу не змінюється. Оскільки спочатку одиниць була парна кількість, то після останнього ходу не може залишатися одна (не парна кількість) одиниця. Виграє другий гравець.
Задача 3. Двоє гравців по черзі розставляють між числами від 1 до 20, записаних в рядок, «+» і «-». Після того як всі місця заповнені обчислюють результат. Якщо отримають парне число, то виграє перший гравець, якщо не парне, то другий.
Розв’язання: Парність результату не залежить від розташування знаків, а від кількості непарних чисел в початковому наборі. Оскільки в даному випадку їх 10 (тобто парне число), то перемагає перший гравець.
Задача 4. Миколка і Сашко виписують дванадцятицифрове число, ставлячи цифри по черзі, починаючи зі старшого розряду. Довести що, які б цифри не писав Миколка, Сашко завжди зможе домогтися, щоб отримане число ділилося на 4.
Розв’язання: Якщо Миколка на 11-му ходу ставить парне число, то Сашко ставить 4, а якщо Миколка пише не парне число, то Сашко ставить 2.
Задача 5. В одному ящику лежать 15 синіх кульок, а в другому 12 білих. За один хід дозволяється взяти 3 синіх кульки або 2 білі. Перемагає той, хто бере останні кульки.
Розв’язання: Зрозуміло, що сині кульки можна рахувати трійками, а білі двійками. Задача зведена до наступної: У ящику лежать 15: 3 + 12: 2 = 11 кубиків. За один хід дозволено брати один кубик. Хто візьме останній? Розв’язання очевидне – це гра, в якій нічого не залежить від гравців.
Задачі для розв’язування
1. Двоє по черзі ламають шоколадку 6x8. За хід дозволено зробити прямолінійний розлом будь-якого з кусків. Програє той, хто не зможе зробити хід.
2. а)В рядок написані 10 одиниць. Миколка і Сашко по черзі записують між будь-якими сусідніми числами знак «+» або «-». Коли між всіма сусідніми числами записані знаки, обчислюється результат. Якщо отримане число парне, то перемагає Миколка, якщо непарне, то Сашко.
б) А якщо хлопці ставитимуть між числами «+» або «x»? (при обчислені результату спочатку виконують множення, а потім додавання).
3. Двоє записують шестизначне число починаючи зі старшого розряду. Якщо отримане число ділиться націло на 7, то виграє той, хто зробив останній хід, інакше починаючий.
4. Двоє по черзі ставлять коней в клітинках шахівниці так, щоб вони не били один одного. Програє той хто не може зробити хід.
5. Дана клітчаста дошка 10x10. За хід дозволяється закрити 2 сусідні клітинки (прямокутником 1x2). Програє той, хто не може зробити хід.
6. Маємо 3 купки камінців, кількість камінців в кожній купці однакова. Двоє гравців беруть по черзі будь-яку кількість камінців з будь-якої купки, але тільки з одної. Перемагає той хто бере останні камінці.
7. Маемо 2 купки камінців: в першій – 30, в другій – 20. За хід можна взяти будь-яку кількість камінців, але тільки з однієї купки. Програє той, хто не зможе взяти камінці.
8. Двоє, А і В грають в гру: по черзі називають цілі додатні числа, при чому гравець А називає число не більше 10, гравець В називає число, більше за назване число гравцем А, але не більше ніж на 10 і т.д. Перемагає той, хто назве число 100.
