Факультатив 8-Б (математика)

 2 семестр 

11 травня

27 квітня 

Симетрія в ігрі (олімпіадні задачі)

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

Приклад 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 також є «послідовними»). Програє той, хто не може зробити черговий хід. Хто переможе у цій грі, якщо першим ходить Андрій та кожен намагається виграти? Відповідь обґрунтуйте.

13 квітня

Математичні ігри

      Розглянемо ще один клас олімпіадних задач, при розв'язуванні яких важливу роль відіграють інваріанти. Це задачі на ігри двох осіб. В кожній такій грі бере участь двоє гравців. Вони роблять ходи почергово. В задачі вимагається встановити, у котрого з гравців – того, що починає гру, чи його суперника, є виграшна стратегія  і в чому вона полягає. Повний перебір усіх можливих ходів та ходів-відповідей, як правило, здійснити не вдається. Тому при розв'язуванні таких задач доводиться шукати деяку властивість - інваріант, на основі якої можна побудувати виграшну стратегію.

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

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

 

Інваріанти

№1

У рівнянні  x³+… +x²+…+ x+…=0 двоє по черзі ставлять цілі коефіцієнти. Чи може перший гравець зробити так,щоб всі корені рівняння були цілі?

Розв'язання:

Якщо всі корені цілі (їх три) то рівняння можна записати так (x²-a²)(x-b)=0 , де x=-a; b – цілі корені.

Тоді,так як старший коефіцієнт = 1, то 1-й гравець при x коефіцієнт = -1. Тоді 2й гравець ставить будь-який коефіцієнт (k),а 1й гравець ставить коефіцієнт протилежний (-k)

Маємо x³-kx²-1x+k=(x³-x)-k(x²-1)=x(x²-1)-k(x²-1)=(x²-1)(x-k), де x=±1 і x=k; k є z (за умовою).

№2

У  рівнянні без коефіцієнтів …x³+…+x²+…+x+…=0 двоє по черзі  ставляють коефіцієнти (дійсні числа). Другий хоче,щоб один із коренів був цілим  чи може перший йому завадити?

Розв'язання:

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

, де aєZ , тобто ліву частину рівняння можна розкласти на множники виносячи спільну дужку за дужки. Це можливо. Нехай перші коефіцієнти  поставлені гравцями будуть будь-якими. Наприклад:  , тоді четвертий коефіцієнт (ставить ІІ гравець) повинен бути таким, щоб можна було б винести спільну дужку за дужки, тоді четвертий коефіцієнт повинен буде складатися із k, p i m.

Нехай це (k + p + m), тоді

  

  

 неможливо винести за дужки спільну дужку.

Тоді з протилежним знаком

  

. .

ІІ варіант 0

                

 ІІІ варіант 

                   

IV варіант

                   ) = 0.  В усіх варіантах можна спільну дужку винести за дужки і один із коренів буде цілим.

№3

 Петро і Василь записують 12-значне число, ставляючи цифри по черзі, починаючи зі старшого розряду. Починає Василь. Він виграє, якщо одержане число не ділиться на 9, в іншому випадку виграє Петро.

Розв'язання:

Виграє Петро. Одна із його можливих стратегій – доповнювати цифру, яку записав Василь до 9. Наприклад, Василь написав 3, Петро – 6; Василь – 0, Петро – 9 і т.д. Таким чином, після кожної пари ходів Василя і Петра сума цифр збільшиться на 9. Отже, записане 12-значне число матиме суму 9·(12:2)=54, тому отримане число буде завжди ділитися на 9.

 

№4

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

Розв'язання:

         Виграє Вовк, віднімаючи із заданого числа його останню цифру. Будь-яке число, яке отримає Вовк, повинно мати нуль на останньому місці. Наприклад, маємо число 107

 

Вовк 107 - 7 =100                                                                       99 - 9 = 90           81 -1 = 80           72 - 2 = 70           63 – 3 = 60           54 - 4 = 50           45 – 5 = 40           36 – 6 = 30           27 – 7 = 20           18 – 8 = 10            9 – 9 = 0

Заєць 100 – 1 = 99            90 – 9 = 81            80 – 8 = 72            70 – 7 = 63            60 – 6 = 54            50 – 5 = 45            40 – 4 = 36            30 – 3 = 27            20 – 2 = 18            10 – 1 = 9

 

№5

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

                                    

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

       Виграє перший гравець. Першим кроком він перекладе із однієї купки в іншу  1 цукерку і з’їсть 2 цукерки з купки де 10 цукерок , їх стане по 8 в обох купках.

       Виграшна  стратегія  коли в обох купках цукерок не залишиться , тобто  нуль  в

перший і нуль в другій (парна кількість), а парну кількість залишає перший гравець.

Незалежно  від ходу  другого  перший зможе отримати дві купки по 6 , 4 , 2 і 0 цукерок 

 

 

№6

В купі лежать 50 каменів. Двоє по черзі додають до неї від 1 до 10 каменів. Переможе той, хто доведе число каменів до 200. Хто це буде I-й чи II-й?

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

Щоб на фініші мати 200 каменів, потрібно перед цим залишити противнику 200 – 11 = 189 каменів ( за один хід противник не доведе число каменів до 200 ), а ще перед цим залишити противнику 189 - 11 = 178 каменів і т.д. ( противник не доведе одним ходом число каменів до 189 каменів). Отже, гравець, який хоче перемогти повинен залишати число каменів таке,  щоб ( 200-А ) було кратним 11, де А- число залишених каменів після ходів І-го і ІІ-го.      Маємо  200 – 50 = 150 – число каменів які потрібно докласти гравцям.

   Отже, перше число це 57 і ( 200 – 57 ) : 11. Так як I починає, він і покладе спочатку 7 каменів. Скільки б не поклав II-й, I-й покладе таку кількість, щоб разом з тими каменями, що поклав II-й  було 11, тоді в купі буде 68 каменів, знову скільки б не поклав II-й, I-й покладе таку кількість, щоб разом з тими каменями, що поклав II-й  було 11, і т. д. тож вони дійдуть до 178, потім до 189 і тоді II-й покладе від 1 до 10 каменів і не отримає 200, а I-й зможе докласти необхідну кількість.

 

№7

На дошці записані 10 одиниць і 10 двійок. За один хід дозволяється стирати будь-які дві цифри і, якщо вони були однаковими, записати двійку, а якщо різними – одиницю. Якщо остання цифра, що залишилася на дошці – одиниця, то виграє перший гравець. Якщо ж двійка, то другий. У кожного з гравців є виграшна стратегія?
                                                                   Розв'язання:

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

30 березня

Задачі на стратегію гри

Теорія

            У математичних іграх припускається, що грають двоє (інколи троє), ходи роблять по черзі (жоден із гравців не може пропустити хід), при чому гравці не роблять помилок. А тому в таких іграх на перед можна визначити кінцевий результат, тобто передбачити, який з гравців може забезпечити собі виграш. Для розв’язання задачі-гри необхідно сформулювати виграшну стратегію одного з гравців та довести, що така стратегія веде до виграшу.       Серед ігрових задач зустрічаються ігри-жарти, тобто ігри, результат яких не залежить від того, як грають суперники.                                                                         У багатьох ігрових задачах виграшна стратегія досягається за допомогою вдалого ходу-відповіді на будь-який хід суперника. Існування такого ходу може забезпечуватись симетрією, розбиттям на пари, доповненням до числа.                                                              Найбільш поширеними є симетричні й парні стратегії, а також стратегії, які будуються на основі аналізу ігрових позицій.                                                                             Симетричні стратегії – це виграшні стратегії, розроблені на основі симетрії стартової позиції гри. Аналіз розв’язування таких задач показує, що в іграх із симетричною стартовою позицією здебільшого виграє той, хто не порушує її симетрії, а порушену суперником симетрію стартової чи ігрової позиції може поновити. Цей простий висновок часто допомагає здобути перемогу в ігрових задачах з симетричною стартовою позицією.     Виграшні позиції що характеризується такими властивостями:      

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

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

Іноді пари, подібні симетричним парам, можна використовувати і в задачах,  стартова позиція яких не є симетричною. Виграшну стратегію, яка передбачає використання пар, називають парною стратегією. Зазначимо, що конкретних порад щодо вибору «пар» не існує. Кожного разу виділення «пар» здійснюється, виходячи з умови конкретної задачі.       Розглянемо спосіб побудови стратегії успіху, який базується на аналізі ігрових позицій. Ігрову позицію називають виграшною, якщо існує такий хід гравця, який забезпечує йому виграш. Ігрову позицію називають програшною, якщо з неї не можна виграти. Якість ігрової позиції визначається перед ходом гравця і не залежить від того, який хід виконуватиме гравець. Після виконання ходу виграшна позиція перетворюється у програшну, а програшна – у виграшну. Аналіз ігрових позицій здебільшого варто починати з фінальної частини гри. Аналізом ігрових позицій треба визначити, чи є стартова позиція виграшною, чи вона програшна. Гравець, який починає гру з виграшної позиції за правильної гри завжди виграє, а гравець, який починає гру з програшної позиції – програє за правильної гри свого суперника.

 

Приклади розв’язування задач.

Задача 1. Маємо три купи каменів: у першій - 1О,   у другій ­– 15,  у третій - 20. За хід дозволяється розділити будь-яку купу на дві менші; програє той, хто не може зробити хід.     .

 Розв'язання. Наприкінці гри, коли не можна зробити хід, маємо 45 куп по одному каменю. За будь-який хід кількість куп збільшується на одиницю, тому вся гра має тривати точно 45 - 3 = 42 ходи.

Отже, другий гравець з'авжди виграє.

Задача2. Двоє гравців по черзі виймають із двох ящиків кулі. За один хід кожен гравець може брати з будь-якого (тільки одно­го) ящика довільну кількість куль. Виграє той, хто бере останнім. Як має грати той гравець, що починає, щоб виграти, якщо в першому ящику 73 кулі, а в другому - 118 куль?

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

Задача 3. Оксана й Оленка обривають на ромашці пелюстки. За один раз можна зірвати будь-яку одну пелюстку або дві, які розташовані поруч. Виграє та дівчина, яка зірве останню пелюстку. Гру починає Оксанка. Хто виграє, якщо на ромашці: а) 24 пелюстки? б) 25 пелюсток.

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

         б) У цьому випадку стартова позиція гри має осьові симетрії. Їх усього 25 – стільки, скільки ромашка має пелюсток. Оксанка своїм першим ходом не порушить симетрії відносно однієї з цих осей. Але своїм першим ходом й Оленка може не порушити симетрії. Для цього їй треба так зірвати одну або дві пелюстки, щоб між зірваними пелюстками їх залишилось по 11. Другим ходом Оксана вже змушена порушити симетрію. Відповідаючи за кожний хід Оксанки, Оленка щоразу може поновлювати симетрію ігрових позицій, що врешті-решт забезпечить їй перемогу у грі.

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

Розв’язання. Для розв'язання задачі розглянемо прямокутну клітчату таблицю розміром 24х 33 клітинки. Клітинки пронумеруємо так, як показано на рисунку З.З. Тоді номери клітинок по горизонталі відпові­датимуть кількості цукерок у другій коробці, а по вертикалі – у першій. Поставимо на клітинку, що міститься в лівому нижньому кутку таблиці, тобто клітинку (23; 32), фішку. Таке положення фішки відповідатиме стартовій позиції гри. Якщо з першої коробки дівчинка бере одну цукерку, то фішка зміщується на одну клітинку по горизонталі праворуч, якщо одну цукерку взяти з другої коробки - фішка зміщу­ється на одну клітинку по вертикалі вгору, якщо ж взяти по одній цукерці з обох коробок, то фішка зміститься по діагоналі праворуч і вгору. Переміщення фішки по клітинках таблиці відповідає переміщенню короля по клітинках шахівниці (див. задачу 3.12). Гра завершиться, коли обидві коробки будуть порожні - фішка стоятиме на верхній правій  клітинці таблиці. Використовуючи результати аналізу ігрових позицій, проведеного в попередній задачі, доходимо висновку, що програшним позиціям гри відповідатимуть клітинки .таблиці з парними номерами. Отже, стартова позиція гри – виграшна позиція, а тому виграє дівчинка, яка починає гру. Для того щоб виграти, їй треба залишати після свого ходу в обох коробках парну кількість цукерок.

 

	0	1	2	3	4	5	6	7
0			*		*		*
1
2			*		*		*
3
4			*		*		*
5
6			*		*		*
7

 

Рис. 3.3

 

Насамкінець зауважимо, що далеко не всі ігрові задачі можна розв’язати, використовуючи описані способи вибору виграшної стратегії. Іноді для розв'язання задачі доводиться поєднувати відомі способи, іноді - розробляти оригінальні стратегії, притаманні одній-єдиній за­дачі. Розв’яжемо дві такі задачі.

Задача 5. У коробці знаходиться 60 сірників. За один хід можна взяти будь-яку кількість від 1 до 5 сірників. Програє той, хто не може зробити хід. Хто з гравців       (перший чи другий) може забезпечити собі виграш?

Розв'язання. Проаналізуємо кінцівку такої гри. Якщо кількість сірників менша за 5, то той гравець, чия черга ходити, закінчує гру. Якщо кількість сірників більша за 6, то гра закінчиться через два або більше ходи. Якщо ж кількість сірників дорівнює 6, то гравець, чий хід передував цій позиції, точно наступним своїм ходом закінчує гру (для цього він на хід суперника в k сірників бере 6 - k сірників). Тобто  така позиція є виграшною для цього гравця. Очевидно, що позиції 12, 18, 24 (і т. д.) сірників для нього також є виграшними, бо таким самим способом він від позиції "24 сірники" переходить до позиції" 18 cipників", від" 18 " до "12".

Oтже, початкова позиція виграшна для другого гравця, а його виграшною стратегією є доповнення ним ходів першого гравця до 6 cipників.

 

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

Задача 1 . На столі лежать 1978 сірників. Два хлопчики по черзі можуть брати один чи два сірники. Який хлопчик виграє і як він має грати для цього?

 Відповідь: Перший гравець. Перший хід – 1 сірник, виграшна стратегія –доповнення до 3.

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

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

Задача 3.  Ромашка має:а) 12 пелюсток; б) 11 пелюсток. За хід дозволяється відірвати або 1, або 2 пелюстки, що ростуть поруч. Програє той, хто не може зробити хід.

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

Задача 4. Двоє по черзі ставляють хрестики і нулики в клітини дошки 9×9. Перший гравець ставить хрестик, другий – нулик. Наприкінці гри треба підрахувати, скільки є рядочків і стовпчиків, у яких хрестиків більше, ніж нуликів – це є очки, набрані першим гравцем. Кількість рядків і стовпчиків, де нуликів більше – очки другого гравця. Перемагає той, у кого більше очок.

Відповідь: Перший гравець; перший хід він робить у центральну клітинку, потім робить симетричні ходи – відповіді.

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

 Відповідь: Виграшні позиції: 500, 250,125,62,31,15,7,3. Перший гравець.

 

Рекомендована література:

1.     Вороний О.М. Готуємось до олімпіад з математики. – Х.:вид. група «Основа»,2008. – 255, [1] с.

2.               Сарана О.А. Математичні олімпіади: просте і складне поруч: навч. посібн. – К.: Видавництво А.С.К., 2004.-344с.

 

26 січня

Задачі на розфарбування

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

Задача 1.На кожній клітині дошки розміром 2005х2005 сидить жук. За    свистком кожний жук переповзе в одну із сусідніх по  діагоналі клітин. При цьому в деяких клітинах можуть    виявитися по кілька жуків, а деякі клітини стануть    незайнятими. Знайдіть найменше число незайнятих    клітин.

Розв’язання. Пофарбуємо вертикалі дошки у білий та чорний кольори так, щоб сусідні вертикалі мали різний колір. Якщо перша зліва вертикаль – чорна, то у нас непарне число  к чорних та парне число n  білих клітин. Переповзаючи, кожний жук  змінює колір клітини, на якій він сидить. На чорні клітини можуть переповзти лише жуки з білих клітин. Тому не менше

k-n чорних клітин стануть вільними.     Відповідь: k-n клітин.

Запитання. В кожній клітині дошки 3*3 сидить жук. В деякий момент всі жуки переповзають на сусідні (по горизонталі або вертикалі) клітини. Чи обов’язково при цьому залишиться хоча   б вільна клітинка?

Вказівка.    Нехай клітини дошки пофарбовано у білий та чорний кольори    у шаховому порядку так, що чорних клітин 13 а білих 12. Оскільки   при переповзанні жук змінює колір клітини, на якій він розташований, одна чорна клітина обов’язково буде вільною.

Задача 2. Є квадратний лист паперу в клітину 100*100.Проведено кілька ламаних без самоперетинів, що йдуть по сторонах     клітинок та не мають спільних точок. Ці ламані лежать всередині     квадрата, лише їх кінці лежать на межі. Довести, що крім вершин     квадрата, знайдеться вузол (всередині або на межі ), який не належить жодній ламаній.

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

Запитання. Чи можна дві ламані перетнути в  трьох  точках одного кольору?

Запитання. В турнірі грають 2m команд. В першому турнірі  зустрілися між собою m пар команд і в другому турнірі зіграли  між собою m пар ( не обов’язково інші). Як довести, що тепер можна вибрати m команд, серед яких жодні дві не грали між собою?

Вказівка:

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

Запитання. Опуклий n – кутник розбитий на трикутники своїми  діагоналями, що не перетинаються, причому в кожній його вершині сходиться  непарна кількість трикутників. Чому n      кратне 3?

Обгрунтування. Якщо многокутник розбитий на частини діагоналями, що не перетинаються, то ці частини можна розфарбувати у білий та чорний кольори так, щоб частини із спільною стороною мали різний колір. Щоб обгрунтувати це, можемо спочатку вважати весь многокутник білим, а далі при  проведенні кожної діагоналі по один бік від неї змінювати кольори всіх частин, а по другий бік – зберігати     розфарбування. Оскільки в кожній вершині сходиться  непарна   кількість трикутників, всі сторони многокутника будуть лежати      трикутникам одного кольору, наприклад, чорного. А кожна проведена діагональ є одночасно стороною і чорного, і білого  трикутника. Тому n дорівнює кількості сторін чорних трикутників мінус кількість сторін білих. Обидві ці кількості, очевидно, діляться на 3, тому і n кратне 3.

Запитання 5. Площина розбита на однакові шестикутні кімнати. В деяких стінах зроблені двері так, що для будь-якої вершини, в  якій сходяться три стіни( сторони шестикутників) двері є точно в двох. Чому будь-який замкнений шлях цим лабіринтом завжди   проходить через парну кількість дверей.

Вказівка:

Всі кімнати можна пофарбувати у два кольори так, що з’єднан ні дверима кімнати мають різні кольори. Для доведення спочатку  якось пофарбуємо одну кімнату, потім за нашим правилом шість її    сусідніх, потім – сусідні з вже пофарбованим і т.д. Оскільки люди   не повертається в початкову кімнату,  вона парну кількість разів змінює колір кімнати.

Тепер наведемо завдання, розв’язанню  якого допомагає розфарбування не в два кольори, а в чотири кольори.

Запитання 6. Чому не можна шашкову дошку10*10 закласти плитками   1*4?

Вказівка: Використаємо діагональне розфарбування в 4 кольори,  плитка 1*4 покриває по одній клітинці кожного кольору.

Але на дошці 10*10 не однакова кількість клітин різних кольорів

12 січня

тема:      Ідея розфарбування при розв'язуванні задач логічного характеру

Розв’язування задач на розфарбування.

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

Розв'язання

  Розфарбуємо дошку так, як пофарбована шахова дошка. Тоді кожна клітинка матиме з сусідніми тільки іріітини, пофарбовані в протилежний колір. Оскільки всього клітинок 77, то матимемо 39 клітинок одного кольо­ру і 38 другого. Нехай для визначеності білих клітинок 39. Тоді 39 жуків, які сиділи на білих клітинках, мають переповзти у 38 чорних клітинок. Тому знайдеться клітинка, на якій будуть сидіти принаймні два жуки, а тому знайдеться і порожня клітинка.                           

 

+	+	─
─	+	+
+	─	+

8. Дано таблицю 3x3 (рис.). Дозволяється змінювати знак одночасно у всіх клітинках одного рядка або одного стовпчика. Чи можна дістати таблицю з самими плюсами?

Розв'язання

Замінимо плюси на 1, а мінуси — на -1. Тоді добуток чисел у чотирьох кутових клітинках дорівнює -1 і з кожною операцією не змінюється. Отримати таблицю з самими плюсами неможливо.

 

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

Розв'язання

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

 

10. Дно прямокутної коробки викладено плитками розміром 2x2 та 1x4. Плитки висипали із коробки і загубили одну плитку 2 х2. Замість неї дістади плитку 1x4. Доведіть, що викласти дно коробкй плитками тепер не вдасться.

Розв'язання

Пофарбуємо дно коробки в білий та чорний кольори, як  показано на рисунку. Тоді кожна плитка 2х2 покриває одну чорну клітку, а плитка 1x4 - 2 або 0. Парність кількості кліток 2x2 по­винна співпадати з парністю кількості чорних клітин. Тому викласти дно коробки тепер не вда­сться.

 

11.    Доведіть, що дошку 6x6 не можна покрити дев'ятьма плитками   4х1.

1	2	3	4	1	2
2	3	4	1	2	3
3	4	1	2	3	4
4	1	2	3	4	1
1	2	3	4	1	2
2	3	4	1	2	3

Розв'язання

 Розфарбуємо дошку в 4 кольори, як показано на рисунку. Які б клітинки не поіфивала плитка, вони матимуть різні кольори. Але тоді для того, щоб 9 плиток покрили всю дошку, клітинок кожного кольору теж повинно бути 9. Перевіркою встановлюємо, що це не так.

 

12.  Квадратне поле розбито на 100 однакових квадратних ділянок, 9 із яких заросли бур'янами. Будь-яка інша ділянка заростає бур'янами тоді й тільки тоді, коли в бур'янах опиняється принаймні дві сусідні (через межу) ділянки. Доведіть, що за таких умов все поле не зможе зарости бур'янами.

Розв'язання                     

Можливі 4 принципово різні розташування незабур'яненої ділянки А в оточенні не менше ніж двох забур'янених ділянок:

Межі ділянки А з її забур'яненими, сусідами позначені пунктирними лі­ніями. Якщо а — довжина сторони однієї ділянки, то сума периметрів забур'янених «сусідів» ділянки А відповідно дорівнюють 8а, 8а, 12а, 16а. Після забур'янення ділянки А периметр нової критичної площі не збіль­шується. На початку периметр дев'яти таких ділянок не перевищував 36а. А периметр усього поля дорівнює 40а. Отже, все поле зарости бур'яном не може.

 

13. У вершинах куба розставлені числа: 7 нулів і одна одиниця. За один хід дозволяється додати по одиниці до чисел у кінцях довільного ребра куба.

а) Чи можна за декілька ходів домоглися того, щоб усі числа стали рівними?

б) Чи можна домогтися того, щоб усі числа ділилися на З?

 

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

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

б) Пофарбуємо в білий колір вершину, де стоїть число 1 і ще три верши­ни так, щоб жодні дві білі вершини не були з'єднані ребром. Інші чотири вершини пофарбуємо в чорний колір. Тоді різниця сум чисел, записаних у білих вершинах, і сум чисел, записаних у чорних вершинах, дорівнює 1 і не буде змінюватись після кожного ходу. Якби всі числа ділилися на 3, то ця різниця була б кратною 3, а 1 на 3 не ділиться.

 

14.  На площині задано 2004 точки і коло з радіусом 1. Доведіть, що на колі знайдеться точка, сума відстаней від якої до заданих точок не менша за 2004.

 

Розв'язання

Розглянемо дві довільні діаметрально протилежні точки на колі. Відстань між ними дорівнює 2. Тому для довільної точки площини сума відстаней від 2004 точок до двох вибраних точок не менша за 2•2004. Отже, принаймні для однієї точки на колі сума відстаней не менша за 2004.