олімпіадна математика

Теорія графів (підрахунок кількості ребер)

shahist — Sun, 30 Oct 2016 18:29:48 GMT

Графіки з модулями

shahist — Tue, 12 May 2015 09:01:11 GMT

Рівняння з модулями

shahist — Wed, 18 Mar 2015 19:56:10 GMT

модулі рівняння from shahist

Теорія ігор (симетрія)

shahist — Wed, 04 Mar 2015 19:57:48 GMT

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

Приклад 1.

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

Розв’язання.

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

Примітка 1.

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

Примітка 2.

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

Приклад 2.

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

Розв’язання.

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

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

Приклад 3.

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

Розв’язання.

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

Задачі для самостійного розв’язання.

1. Дана шахова дошка. За один хід дозволяється покрити будь-які дві не покриті раніше клітинки доміношкою 1х2. Програє той, хто не може зробити хід.

2. На столі лежать дві купки монет: в одній із них 30 монет, а в другій – 20. За хід дозволяється взяти будь-яку кількість монет із однієї купки. Програє той, хто не зможе зробити хід. Хто із гравців виграє при правильній грі?

3. Два гросмейстери по черзі ставлять на шахову дошку тури (за один хід – одну туру) так, щоб вони не били одна одну. Той, хто не зможе поставити туру, програє. Хто виграє при правильній грі?

4. У ромашки а) 12 пелюсток, б) 11 пелюсток. За один хід дозволяється зірвати або одну пелюстку, або дві пелюстки, що ростуть поруч. Програє гравець, який не може зробити хід. Як слід грати другому гравцю, щоб виграти незалежно від ходу першого гравця?

5. Є дві купки камінців – по 7 в кожній. За хід дозволяється взяти будь-яку кількість камінців із однієї купки. Програє той, хто не зможе зробити хід. Хто із гравців виграє при правильній грі?

6. Двоє ставлять королів у клітинки дошки 9х9 так, щоб королі не били один одного. Програє той, хто не може зробити хід.

7. Двоє по черзі ламають шоколадку 5х10. За хід дозволяється зробити прямолінійний розлом будь-якого одного наявного шматка вздовж заглиблення. Виграє той, хто першим відламає шматочок 1х1.

8. Тарасик і Оксана по черзі зафарбовують клітинки таблиці розміром 2000х 2000. За один хід дозволяється зафарбувати будь-які дві не зафарбовані раніше клітинки, що мають спільну сторону. Починає гру Тарасик, а переможцем вважається той, після ходу якого вже не можна продовжити гру. Як слід грати Оксані, щоб завжди перемагати в цій грі?

9. Хлопчик і дівчинка проводять діагоналі в правильному 2006-кутнику так, щоб вони не перетиналися. Той, хто проведе таку діагональ останнім, виграє. Як повинна грати дівчинка, що починає гру, щоб виграти?

10. Двоє по черзі відривають пелюстки ромашки. Можна за один раз зірвати будь-яку одну або дві пелюстки, що ростуть поруч. Виграє той, хто зриває останню пелюстку. Хто виграє, якщо на ромашці 23 пелюстки?

11. Хлопчик і дівчинка по черзі зафарбовують клітинки таблиці розміром 2015х2015. За один хід дозволяється зафарбувати будь-яку одну не зафарбовану клітинку або будь-які дві не зафарбовані раніше клітинки, котрі мають спільну сторону. Починає гру хлопчик, а програє той, хто не може зробити хід. Хто?

12. По колу рівномірно розкладені 2015 цукерок, які за рухом годинникової стрілки перенумеровані числами від 1 до 2015. Андрій та Олеся грають у таку гру – вони по черзі беруть розкладені цукерки. За один хід можна взяти 2 чи 3 цукерки, номера яких є послідовними числами (вважаємо, що 1 та 2015 також є «послідовними»). Програє той, хто не може зробити черговий хід. Хто переможе у цій грі, якщо першим ходить Андрій та кожен намагається виграти? Відповідь обґрунтуйте.

Заняття підготував вчитель математики Крутівської ЗОШ Монько І.О.

Ознаки подільності

shahist — Wed, 18 Feb 2015 18:12:18 GMT

Простим називається число, яке не має інших дільників, крім 1 і самого цього числа.

Натуральне число ділиться на 3 тоді і тільки тоді, коли сума його цифр ділиться на 3.

Натуральне число ділиться на 9 тоді і тільки тоді, коли сума його цифр ділиться на 9.

Натуральне число ділиться на 2 тоді і тільки тоді, коли його остання цифра парна або 0.

Натуральне число ділиться на 5 тоді і тільки тоді, коли його остання цифра 5 або 0.

Натуральне число ділиться на 4 тоді і тільки тоді, коли число, утворене двома його останніми цифрами (в тому ж порядку) ділиться на 4.

Натуральне число ділиться на 8 тоді і тільки тоді, коли число, утворене трьома його останніми цифрами (в тому ж порядку) ділиться на 8.

Приклад 1.

Хлопчик написав у зошиті число 65349*0712 як приклад числа, що ділиться: а) на 9; б) на 3. (на місці зірочки стояла цифра, яку випадково витерли). Допоможіть відновити пропущену цифру. Вкажіть усі можливі варіанти.

Розв’язання.

Сума відомих цифр числа дорівнює 37.

а) Щоб число ділилось на 9, потрібно, щоб сума його цифр ділилась на 9. Це можливо тільки тоді, коли на місці зірочки стоїть цифра 8.

б) Щоб число ділилось на 3, потрібно, щоб сума його цифр ділилась на 3. Це можливо тільки тоді, коли на місці зірочки стоїть одна із цифр 2, 5, 8.

Приклад 2.

Чи ділиться число 32561698 на 12?

Розв’язання.

1 спосіб.

Число 32561698 закінчується на 98, а 98 за ознакою подільності на 4 не ділиться на 4. Але будь-яке число, яке ділиться на 12, повинно ділитись і на 4.

2 спосіб.

Сума цифр числа 32561698 дорівнює 40, а 40 не ділиться на 3. Тому за ознакою подільності на 3 число не ділиться на 3. Але будь-яке число, яке ділиться на 12, повинно ділитись і на 3.

Задачі для самостійного розв’язання.

1. Запишемо підряд цифри від 0 до 9, отримаємо число 123456789. Просте воно чи складне? Чи зміниться відповідь, якщо якимось чином переставити цифри в числі?

2. Даринка і Тетянка по черзі записують на дошці цифри шестизначного числа. Спочатку Даринка записує першу цифру, потім Тетянка – другу, і так далі. Тетянка хоче, щоб отримане число ділилось на 3, а Даринка хоче їй завадити. Хто з них може досягти бажаного результату незалежно від ходу суперника?

3. Щоб відкрити сейф, потрібно ввести код – семизначне число, яке складається з двійок і трійок. Сейф відкриється, якщо двійок в коді більше, ніж трійок, а сам код ділиться і на 3, і на 4. Який код може відкрити сейф?

4. Доведіть, що добуток двох послідовних парних чисел завжди ділиться на 8.

5. Чи може добуток чотирьох послідовних чисел закінчуватись на 116?

6. Доведіть, що 2015-цифрове число не є простим. Відповідь обґрунтуйте.

7. Замініть зірочки в записі числа 72*4* цифрами так, щоб число ділилось на 45. Вкажіть усі можливі варіанти.

Основна теорема арифметики: кожне натуральне число n, більше за 1, може бути представлене у вигляді добутку простих множників, причому єдиним, із точністю до перестановки множників, способом n=р₁^а1·р₂^а2·…·р_k^а^k.

Приклад 3.

Чи існують два натуральних числа, у записі яких немає нулів і добуток яких дорівнює 1000000?

Розв’язання.

1000000=10⁶=(2·5)⁶=2⁶·5⁶. У записі чисел 2⁶ та 5⁶ немає жодного нуля (оскільки для того щоб в записі числа був 0 потрібно, щоб число ділилось на 10, тобто в розкладі його на прості множники повинні бути і 2, і 5) і їх добуток рівний 1000000.

Задачі для самостійного розв’язання.

8. p i q – різні прості числа. Скільки дільників у числа pq?

9. p i q – різні прості числа. Скільки дільників у числа pⁿ?

10. p i q – різні прості числа. Скільки дільників у числа p²q?

11. p i q – різні прості числа. Скільки дільників у числа p²q²?

12. p i q – різні прості числа. Скільки дільників у числа p^mqⁿ?

13. Скільки різних дільників має число:

а) 3⁵;

б) 3⁵·5;

в) 2·3·5·7·11;

г) 2²·3³·5⁵···7⁷·11¹¹;

д) 2²·3³·4⁴·5⁵?

Основи комбінаторики

shahist — Fri, 13 Feb 2015 15:18:44 GMT

При розв’язуванні задач зручно користуватися правилами суми та добутку.

Правило суми: якщо деякий об’єкт А можна вибрати m способами, а інший об’єкт В можна вибрати n способами, то вибір "Або А, або В" можна здійснити m+n способами.

При використанні правила суми потрібно слідкувати, щоб жоден із способів вибору об’єкта А не співпадав із жодним способом вибору об’єкта В.

Приклад 1.

У вазі лежать чотири яблука та три груші. Скількома способами можна обрати один фрукт?

Розв’язання.

Якщо у вазі лежать 4 яблука, то одне яблуко можна обрати чотирма способами (можемо взяти одне із 4 яблук). Якщо у вазі лежать 3 груші, то одну грушу можна обрати трьома способами (можемо взяти одну із трьох груш). А обрати один фрукт можна 4+3=7 способами.

Правило добутку: якщо деякий об’єкт А можна вибрати m способами і після кожного такого вибору інший об’єкт В можна вибрати n способами, то вибір пари (А; В) у вказаному порядку можна здійснити mn способами.

Приклад 2.

Скількома способами можна вибрати голосну та приголосну літери зі слова "приклад"?

Розв’язання.

Голосну літеру можна вибрати 2 способами (можна взяти одну з літер "а" або "и"). Приголосну літеру можна вибрати 5 способами (можна взяти одну із літер "п", "р","к", "л", "д"). Для кожного з 2 способів вибору голосної літери є 5 способів вибору приголосної літери. Тому пару із голосної та приголосної літер можна вибрати 2·5=10 способів.

При розв’язуванні більш складних задач часто доводиться комбінувати правило суми і правило добутку.

Приклад 3.

Скільки чисел від 0 до 99 не містять у своєму записі цифру 5?

Розв’язання.

Спочатку порахуємо однозначні числа. Таких чисел може бути 8. А саме: 1, 2, 3, 4, 6, 7, 8, 9. Тепер порахуємо двозначні числа. Їх можна утворити, приписавши до будь-якого однозначного числа праворуч будь-яку із 9 можливих цифр (0, 1, 2, 3, 4, 6, 7, 8, 9). За правилом добутку таких двозначних чисел можна утворити 8·9=72. А разом однозначних та двозначних чисел, які задовольняють умову задачі, буде (за правилом суми) 72+8=90.

Часто один і той же об’єкт вибирають кілька разів. Тоді для отримання правильного результату потрібно відкинути повторні вибори.

Приклад 4.

Скількома способами із 28 кісток доміно можна обрати дві кістки так, що їх можна було прикласти одну до одної (тобто щоб деяка кількість очок була на обох кістках).

Розв’язання.

Спочатку оберемо одну кістку. Це можна зробити 28 способами. При цьому в 7 випадках обрана кістка виявиться дублем, тобто кісткою виду 0/0, 1/1, 2/2, 3/3, 4/4, 5/5, 6/6, а у 21 випадку – кісткою з різною кількістю очок (наприклад 0/2 або 3/5). У першому випадку другу кістку можна обрати 6 способами (наприклад, якщо на першому кроці була обрана кістка 1/1, то на другому кроці можна взяти одну із кісток 1/0, 1/2, 1/3, 1/4, 1/5, 1/6). У другому випадку другу кістку можна обрати 12 способами (для кістки 3/5 підійдуть як кістки 3/0, 3/1, 3/2, 3/3, 3/4, 3/6, так і 5/0, 5/1, 5/2, 5/4, 5/5, 5/6). За правилом добутку в першому випадку отримаємо 7·6=42 вибори, а в другому 21·12=252 вибори. Отже, за правилом суми отримуємо 42+252=294 способи вибору пари. У наведених міркуваннях враховувався порядок, у якому обирались кістки. Тому кожна пара була порахована двічі (наприклад, у першому випадку 1/1 та 1/6, а в другому – 1/6 і 1/1). Відповідно отриману кількість виборів потрібно поділити на 2. 294/2=147.

Задачі для самостійного розв’язання.

1. Скільки всього існує чотиризначних чисел?

2. Скільки тризначних чисел містять у своєму записі рівно одну цифру 3?

3. Скільки тризначних чисел містять у своєму записі хоча б одну цифру 3?

4. Учень виписав підряд всі тризначні числа. Скільки разів він написав цифру 3?

5. Скількома способами можна вказати на кубі дві сусідні грані?

6. Скільки існує різних прямокутників із цілими сторонами й периметром рівним 2014?

7. Скільки всього існує семизначних чисел, які складаються із 4 одиниць та 3 нулів?

8. Скільки всього існує семизначних чисел, цифри в запису яких розташовані в порядку зростання?

9. Скільки всього існує семизначних чисел, цифри в запису яких розташовані в порядку спадання?

10. На двох паралельних прямих розташовані точки (точки не співпадають): на одній – 3 точки, на другій – 6 точок. Скільки існує трикутників із вершинами в цих точках?

11. Скільки існує різних трикутників із цілими сторонами від 11 до 20?

12. Скількома способами можна набрати намисто із 7 червоних та 3 синіх бусинок?

13. Скількома способами можна набрати намисто із 7 червоних та 3 синіх бусинок так, щоб поруч не було синіх бусинок?

Принцип Діріхле

shahist — Sun, 01 Feb 2015 14:11:01 GMT

Принцип Діріхле найпростіше зрозуміти, використавши таку його жартівливу форму: "Якщо в N клітках сидять не менше N+1 кроликів, то у якійсь із кліток сидить не менше двох кроликів". Звернемо увагу на невизначеність висновків – "у якійсь із кліток", "не менше". Ця невизначеність часто призводить до цікавих висновків на основі, здавалось би, недостатніх даних. Часто при розв’язуванні задач на принцип Діріхле точне доведення міркувань можна дати за допомогою доведення від супротивного.

Приклад 1.

У мішку лежать кульки двох кольорів: чорного та білого. Яку найменшу кількість кульок потрібно дістати з мішка наосліп, щоб серед них точно виявились дві кульки одного кольору?

Розв’язання.

Зрозуміло, що двох кульок може не вистачити: може виявитись, що вони різних кольорів. Тому слід взяти не менше 3 кульок. Доведемо, що 3 кульок досить. Припустимо протилежне – 3 кульок не досить (тобто серед трьох кульок може і не знайтись двох кульок одного кольору). Якщо всі три кульки різного кольору, то вони пофарбовані у три кольори. Але за умовою задачі у мішку є кульки тільки двох кольорів. Ця суперечність означає, що наше припущення неправильне. А отже, серед трьох кульок завжди знайдуться дві кульки одного кольору. Зрозуміло, що кроликами в цій задачі є кульки, а клітками – кольори: чорний і білий.

Приклад 2.

Довести, що серед n+1 цілого числа можна вибрати два, різниця яких ділиться на n.

Розв’язання.

При діленні на n будь-яке ціле число дає в остачі одне з чисел 0, 1, 2, … , n-1, тобто всього існує n різних остач. Тому серед n+1 чисел знайдуться 2 такі, що дають однакові остачі при діленні на n. Різниця цих чисел і ділитиметься на n.

Узагальнений принцип Діріхле: "Якщо в N клітках сидять не менше kN+1 кроликів, то у якійсь із кліток сидить не менше k+1 кроликів".

Приклад 3.

У магазин привезли 25 ящиків із яблуками трьох сортів, причому в кожному ящику лежать яблука якогось одного сорту. Чи можна знайти 9 ящиків із яблуками одного сорту?

Розв’язання.

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

Зрозуміло, що кроликами в даному випадку будуть ящики, а клітками – сорти яблук. Тоді N=3, а kN+1=25. Отже k=8. Тому, за принципом Діріхле, знайдеться сорт яблук (клітка), якій відповідає не менше k+1=9 ящиків (кроликів).

Задачі.

1. 100 зайців розсадили в 99 кліток. Доведіть, що знайдеться клітка, в якій сидять не менше 2 зайців.

2. Яке найбільше число тур можна розставити на шахівниці так, щоб жодна з них не била іншу?

3. В темній шафі зберігаються шкарпетки 7 різних кольорів. Яку найменшу кількість шкарпеток слід взяти наосліп, щоб із них можна було утворити пару?

4. На планеті Айсберг живуть п’ятирукі інопланетяни. На базі Айсберг-17 зберігаються рукавички 8 видів. Одного дня на базі вимкнулась електроенергія. Яку найменшу кількість рукавичок має взяти кожен інопланетянин наосліп, щоб після виходу на світло він міг гарантовано одягти на кожну із своїх рук однакові рукавички?

5. У класі 41 учень. В диктанті Григорій зробив 13 помилок, а решта менше. Довести, що принаймні 4 учні зробили однакову кількість помилок.

6. Хлопчик протягом трьох днів купив 100 марок. Довести, що в один із цих днів він купив не менше 34 марок.

Часто при розв’язування задач зручно користуватися такою теоремою:

"Якщо в N клітках сидить менше N*(N-1)/2 кроликів, то знайдуться принаймні 2 клітки, у яких сидить однакова кількість кроликів (можливо жодного)".

Приклад 4.

У місті 14 шкіл. Для міста виділили 90 комп’ютерів. Довести, що як би не розподіляли комп’ютери між школами, знайдуться 2 школи, які отримали однакову кількість комп’ютерів (можливо жодного).

Розв’язання.

Припустимо, що усі школи отримали різну кількість комп’ютерів. Порахуємо найменшу кількість комп’ютерів, потрібних для цього. Нехай одна зі шкіл отримала 0 комп’ютерів, друга – 1, третя – 2, і т.д., чотирнадцята – 13 комп’ютерів. Тоді всього комп’ютерів потрібно 0+1+2+3+…+13=91. А їх всього 90. Протиріччя. Отже, знайдеться принаймні 2 школи, які отримали однакову кількість комп’ютерів. В цій задачі кроликами будуть комп’ютери, а клітками – школи. N=14. Тоді N*(N-1)/2=14*(14-1)/2=91. Отже, щоб всі школи отримали різну кількість комп’ютерів, потрібен 91 комп’ютер.

7. 15 хлопчиків зібрали 100 горіхів. Довести, що як би вони їх не ділили, знайдуться 2 хлопчики, які отримають порівну горіхів.

8. До свята 10 хлопчиків надули 44 кульки, серед них 11 червоних, а решта – інших кольорів. Довести, що 1) знайдеться хлопчик, який надув принаймні 2 червоні кульки, 2) знайдеться хлопчик, який надув принаймні 5 кульок, 3) знайдуться два хлопчики, які надули однакову кількість кульок (можливо, жодної).

9. Чи можна розкласти 44 кубики на 9 купок так, щоб кількість кубиків в усіх купках була різною?

10. Кілька футбольних команд проводять турнір в одне коло. Доведіть, що в будь-який момент турніру знайдуться дві команди, що зіграли однакову кількість разів.

Приклад 5.

Довести, що серед 6 будь-яких цілих чисел знайдуться 2, різниця яких ділиться на 5.

Розв’язання.

Ця задача зводиться до принципу Діріхле простим твердженням: різниця двох чисел ділиться на 5, якщо вони мають однакові остачі при ділення на 5. Отже, нам досить довести, що серед шести чисел завжди знайдуться два, які мають однакові остачі при ділення на 5. Оскільки можливих остач всього 5: 0, 1, 2, 3, 4, а чисел 6, то за принципом Діріхле знайдуться два, які мають однакові остачі при ділення на 5. У цій задачі кроликами будуть числа, а клітками – остачі від ділення на 5.

11. Довести, що серед будь-яких трьох цілих чисел можна знайти 2, сума яких ділиться на 2.

12. Довести, що серед будь-яких восьми натуральних чисел знайдуться 2, різниця яких ділиться на 7.

13. Чи можна знайти такі два різні степені числа 4, у яких 1) остання цифра однакова, 2) дві останні цифри однакові, 3) три останні цифри однакові?

14. У клітинках таблиці 3×3 розставили числа -1; 0; 1. Після цього обчислили суми чисел в кожній стрічці, в кожному стовпчику і в кожній діагоналі. Доведіть, що серед обчислених сум знайдуться дві однакові.

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

16. Площина довільним чином розфарбована у два кольори. Довести, що знайдуться дві точки одного кольору на відстані 1 м одна від одної.

Заняття підготував вчитель математики Крутівської ЗОШ Монько І.О.