ІНВАРІАНТИ. РОЗФАРБУВАННЯ На дошці записано 11 чисел 6 нулів і 5 одиниць. Дозволяється 10 раз виконати таку операцію: закреслити будь-які два числа і якщо

ІНВАРІАНТИ. РОЗФАРБУВАННЯ На дошці записано 11 чисел — 6 нулів і 5 одиниць. Дозволяється 10 раз виконати таку операцію: закреслити будь-які два числа і якщо вони будуть однакові, то дописати до тих чисел, що залишились, один нуль, а якщо різні — одиницю. Яке число залишиться на дошці? Розв'язання Після кожної операції сума всіх дописаних чисел змінюється на 0 або на 2, тому її парність не змінюється. Оскільки на початку сума була непар­ною, то й останнє число, що змінюється на дошці, має бути непарним, тобто 1. Дано таблицю 3x3 (рис). Дозволяється змінювати знак одночасно у всіх клітинках одного рядка або одного стовпчика. Чи можна дістати таблицю з самими плюсами? Розв'язання Замінимо плюси на 1, а мінуси — на -1. Тоді добуток чисел у чотирьох кутових клітинках дорівнює -1 і з кожною операцією не змінюється. Отримати таблицю з самими плюсами неможливо. Автомат розмінює одну монету на п'ять інших. Чи можна за його допомогою розміняти металеву гривню на 26 монет? Розв'язання Після кожного розміну кількість монет зменшується на 4. Тому щора­зу остача від ділення кількості наявних монет на 4 не змінюється і дорівнює 1. Але остача від ділення 26 на 4 дорівнює 2. Тому такий розмін неможливий. У Змія-Горинича 2004 голови. Ілля Муромець одним ударом меча може відрубати точно 1, 15, 31 або 45 голів, але при цьому у Змія виростає 10, 33, 4 або 0 голів. Чи зможе богатир перемогти Змія-Горинича? Розв'язання Щоразу після удару меча кількість голів у Змія буде змінюватись на число, кратне 9. Тому щоразу остача від ділення числа голів на 9 не зміню­ватиметься і буде дорівнювати 6. Отже, число голів Змія не зможе дорів­нювати 0, оскільки 0 ділиться на 9 без остачі. Тому перемогти Змія-Гори­нича неможливо. На дошці написано числа 1, 2, 3, ..., 19, 20. Дозволяється стерти будь-які два числа а і b і замість них написати число а + b – 1. Яке число може залишитись на дошці після 19 таких операцій? Розв'язання Щоразу після кожної операції сума всіх чисел на дошці зменшується на 1. Тому після 19 таких операцій на дошці буде число 1 + 2 +...+ 20 – 19 = 191. Дано три числа , 2, . Дозволяється будь-які два з них замінити її сумою та різницею, поділеними на . Чи можна після декількох таких операцій отримати числа 1, , 1+? Розв'язання Позначимо через a, b, c трійку чисел, що дістали після якоїсь операції. Тоді після наступної операції можемо дістати , , с. Оскільки то після кожної операції сума квадратів трьох чисел не змінюється, тобто є інваріантом. Тому відповідь на питання задачі негативна. На дошці написане число 8n. У нього обчислюється сума цифр, у обчисленого числа знову обчислюється сума цифр, і так далі, до того моменту, поки не дістанемо однозначне число. Що це за число, якщо: а) n = 2004; б) n = 2005? Розв'язання Скористаємось тим, що в сумі цифр остача від ділення на 9 та сама, що й у самого числа. Якщо п — непарне, то остача від ділення 8n на 9 дорівнює 8, якщо п — парне, то остача дорівнює 1. Тому у випадку а) дістанемо число 1, а у випадку б) — число 8. Пару чисел одним елементарним перетворенням дозволя­ється замінити на одну із пар , , , причому скорочення у здобутих дробах не допускаються. Чи можна таким спосо­бом із пари дістати пару ? Розв'язання Ні, не можна, бо якщо пара вигляду переходить у пару , то в кожному з трьох можливих випадків справджується рівність . Але . На координатній площині є чотири точки з цілими координатами. Дозволяється замінити будь-яку з цих точок на точку, симетричну їй відносно будь-якої іншої з цих точок. Чи можна за декілька операцій перейти від точок (0; 0), (0; 1), (1; 0), (1; 1) до точок з координатами (0; 0), (1;1), (3;0), (2;-1)? Розв'язання Очевидно, що можливість переходу від першої четвірки точок до другої рівносильна можливості переходу від другої четвірки точок до першої. У другої четвірки різниця координат кожної точки дорівнює 0 або З, тобто ділиться на 3. Якщо точка М2 (х2; у2) симетрична точці М1 (х1; у1) відносно точки М0 (х0; у0), то їхні координати зв'язані рівностями , звідки дістаємо: х2 = 2хо – х1, у2 = 2уо – у1, х2 – у2 = 2(х0 – у0) - (х1 – у1). Звідси видно, що коли різниці координат х – у якихось двох точок діляться на 3, то й різниця координат третьої теж ділиться на 3. Тому, виходячи з другої четвірки точок, не можна дістати точки (0; 1), (1; 0). На столі лежить купа із 2004 каменів. Хід полягає в тому, що з якої-небудь купи, що містить більше ніж один камінь, один викидають, а потім купу ділять на дві. Чи можна через декілька ходів залишити на столі тільки купи, що складаються з трьох каменів? Розв'язання Будемо розглядати величину S, що дорівнює сумі кількості наявних каменів і кількості куп. Очевидно, що вона не змінюється після кожного ходу і S =2005. Якщо припустити, що на столі можуть залишитися тільки к куп по 3 камені, то тоді S = 3k + k = 4k, отже, S повинно ділитися на 4, але 2005 не ділиться на 4, тому відповідь на питання задачі негативна. У кожній клітинці клітчатої дошки 7x11 сидить жук. У певний мо­мент усі жуки переповзають в одну із сусідніх клітинок, що мають з ними спільну сторону. Доведіть, що після цього якась клітинка буде порожньою. Розв'язання Розфарбуємо дошку так, як пофарбована шахова дошка. Тоді кожна клітинка матиме з сусідніми тільки клітини, пофарбовані в протилежний колір. Оскільки всього клітинок 77, то матимемо 39 клітинок одного кольо­ру і 38 другого. Нехай для визначеності білих клітинок 39. Тоді 39 жуків, які сиділи на білих клітинках, мають переповзти у 38 чорних клітинок. Тому знайдеться клітинка, на якій будуть сидіти принаймні два жуки, а тому знайдеться і порожня клітинка. Куб розбито на 27 однакових кубиків. У початковий момент жук знаходиться в центральному кубику. З кожного кубика жук може перехо­дити до сусіднього, що має з ним спільну грань. Чи зможе жук обійти всі кубики, побувавши в кожному по одному разу? Розв'язання Перефарбуємо всі кубики в білий та чорний кольори в шаховому по­рядку так, щоб центральний кубик був білим. Тоді білих кубиків 13, а чорних 14. Під час переходу жук змінює колір кубика на протилежний. Тому, починаючи з білого, він має закінчити обхід теж у білому, тобто побувати в білих кубиках 14 раз. Отже, відповідь на запитання задачі не­гативна. Дно прямокутної коробки викладено плитками розміром 2x2 та 1x4. Плитки висипали із коробки і загубили одну плитку 2x2. Замість неї дістали плитку 1x4. Доведіть, що викласти дно коробки плитками тепер не вдасться. Розв'язання Пофарбуємо дно коробки в білий та чорний кольори, як показано на рисунку. Тоді кожна плитка 2x2 покриває одну чорну клітку, а плитка 1x4 — 2 або 0. Парність кількості кліток 2x2 по­винна співпадати з парністю кількості чорних клітин. Тому викласти дно коробки тепер не вда­сться. Доведіть, що дошку 6x6 не можна покрити дев'ятьма плитка­ми 4x1. Розв'язання Розфарбуємо дошку в 4 кольори, як показано на рисунку. Які б клітинки не покривала плитка, вони матимуть різні кольори. Але тоді для того, щоб 9 плиток покрили всю дошку, клітинок кожного кольору теж повинно бути 9. Перевіркою встановлюємо, що це не так. Квадратне поле розбито на 100 однакових квадратних ділянок, 9 із яких заросли бур'янами. Будь-яка інша ділянка заростає бур'янами тоді й тільки тоді, коли в бур'янах опиняється принаймні дві сусідні (через межу) ділянки. Доведіть, що за таких умов все поле не зможе зарости бур'янами. Розв'язання Можливі 4 принципово різні розташування незабур'яненої ділянки А в оточенні не менше ніж двох забур'янених ділянок: Межі ділянки А з її забур'яненими сусідами позначені пунктирними лі­ніями. Якщо а — довжина сторони однієї ділянки, то сума периметрів забур'янених «сусідів» ділянки А відповідно дорівнюють 8а, 8а, 12а, 16а. Після забур'янення ділянки А периметр нової критичної площі не збіль­шується. На початку периметр дев'яти таких ділянок не перевищував 36а. А периметр усього поля дорівнює 40а. Отже, все поле зарости бур'яном не може. У вершинах куба розставлені числа: 7 нулів і одна одиниця. За один хід дозволяється додати по одиниці до чисел у кінцях довільного ребра куба. а) Чи можна за декілька ходів домогтися того, щоб усі числа стали рівними? б) Чи можна домогтися того, щоб усі числа ділилися на З? Розв'язання а) Не можна, бо на кожному кроці до загальної суми додається чис­ло 2. Тому сума всіх записаних чисел залишається непарною, а число всіх вершин куба парне. б) Пофарбуємо в білий колір вершину, де стоїть число 1 і ще три верши­ни так, щоб жодні дві білі вершини не були з'єднані ребром. Інші чотири вершини пофарбуємо в чорний колір. Тоді різниця сум чисел, записаних у білих вершинах, і сум чисел, записаних у чорних вершинах, дорівнює 1 і не буде змінюватись після кожного ходу. Якби всі числа ділилися на 3, то ця різниця була б кратною 3, а 1 на 3 не ділиться. У вершинах куба записані певні числа. Кожне з чисел замінили се­реднім арифметичним трьох сусідніх (через спільні ребра), причому всі заміни проводяться одночасно. Після 2004 таких операцій у кожній вер­шині виявилось початкове число. Чи обов'язково всі початкові числа були рівні між собою? Розв'язання Пофарбуємо вершини куба в білий та чорний кольори так, щоб кожне ребро куба мало різнокольорові кінці. Запишемо в білих вершинах деяке число а, а в чорних b ≠ а. При цьому для кожного числа а сусідніми будуть b, а для b сусідніми будуть а. Тоді після кожного ходу всі числа а та b будуть мінятися одне на одне. Тоді після кожного парного ходу в кожній вершині куба знову буде початкове число. Отже, початкові числа не обов'язково повинні бути рівними між собою. Правильний трикутник зі стороною п розбито прямими, паралельни­ми сторонам трикутника на п2 правильних трикутників зі стороною 1. По сторонах здобутих трикутників проведена незамкнена ламана, що проходить через усі вершини трикутників точно по одному разу. Доведіть, що не менше ніж п пар сусідніх ланок ламаної утворюють між собою гострий кут. Розв'язання Розфарбуємо трикутни­ки в чорний та білий коль­ори, як показано на рисун­ку. Кожна ланка ламаної проходить по стороні чор­ного трикутника. Маємо вершин, тому ламана має ланок. Усього чорних трикутників , тому не менше ніж п з них містять по парі ланок. Ці пари ланок утворюють гострий кут 60°. На площині задано 2004 точки і коло з радіусом 1. Доведіть, що на колі знайдеться точка, сума відстаней від якої до заданих точок не менша за 2004. Розв'язання Розглянемо дві довільні діаметрально протилежні точки на колі. Відстань між ними дорівнює 2. Тому для довільної точки площини сума відстаней від 2004 точок до двох вибраних точок не менша за 2∙2004. Отже, принаймні для однієї точки на колі сума відстаней не менша за 2004. Задачі для самостійного розв'язування Хулігани Василько і Андрійко порвали стінгазету, причому Ва­силько кожен шматок розривав на 8 частин, а Андрійко — на 15 частин. Під час спроби зібрати стінгазету знайшли 2004 обривки. Доведіть, що знайшли не всі обривки. В алфавіті племені УАУ всього дві літери: У та А. Два слова вважаються однаковими, якщо одне з них можна одержати з іншого за допомогою таких операцій: а) вилучення сполучення УА з будь-якого місця слова; б) вставлення сполучення АУ або УУАА на будь-яке місце. Чи є однакови­ми слова УАА та АУУ? Петрику подарували набір «Юний паркетник» із 12 прямокутників 1x3. Хуліган Сергійко замінив один з прямокутників на кутик з трьох кліток. Чи зможе Петрик скласти квадрат 6x6? Для числа 19971997 підрахували суму його цифр. У здобутому числі знову підрахували суму цифр і т. д. аж поки не дістали одноцифрове чис­ло. Знайдіть це число. На дошці записано числа 1, 2, ..., 20. Дозволяється стерти будь-які два числа а і b і замінити їх на число ab+a+b. Яке число може залишитись на дошці після 19 таких операцій? У пробірці знаходяться марсіанські амеби трьох типів: А, В, С. Дві амеби будь-яких двох різних типів можуть злитися в одну амебу третього типу. Після певної кількості таких зливань в пробірці виявилась одна аме­ба. Який її тип, якщо відомо, що спочатку амеб типу А було 20, типу В – 1 та типу С – 22? На кожному з 44 дерев, що розміщені по колу, сидить один горо­бець. Час від часу якісь два горобці перелітають на сусіднє дерево — один за годинниковою стрілкою, а другий — проти. Чи зможуть усі горобці зібратися на одному дереві? Чи можна прямокутник 8х9 розрізати на прямокутники 1х6? Десять шашок розмістили в ряд. Чи можна розташувати їх у зво­ротному порядку, якщо дозволяється міняти місцями будь-які дві шашки, які стоять через дві? У трьох вершинах квадрата сидять коники. Вони починають грати в довгу лозу, перестрибуючи один через другого, причому на таку ж відстань, яка була між ними до стрибка. Чи може один з коників опини­тись у четвертій вершині квадрата? Круг розбитий на 6 секторів, в які поставлені числа 0, 0, 1, 0, 1, 0. Дозволяється за раз додати по одиниці до чисел, які стоять у двох сусідніх секторах. Чи можна за кілька таких операцій зробити всі числа в усіх сек­торах рівними? Кожне число від 1 до 1 000 000 замінюють числом, що дорівнює сумі його цифр. Над знайденими числами виконують ту саму операцію і так далі, поки всі числа не стануть однозначними. Яких чисел утвориться в результаті більше: одиниць чи двійок? На дошці записано 100 одиниць. За один крок дозволяється за­мість будь-яких двох записаних чисел х та у записати число . Після 99 кроків залишилось одне число. Доведіть, що воно не менше за . У колі проведено два діаметри АВ і CD. Нехай М — довільна точка кола, яка не збігається з жодною із точок А, В, С, D, а М, і М2 — проекції точки М відповідно на діаметри АВ і CD. Доведіть, що довжина відрізка М1М2 не залежить від точки М. Король обійшов дошку 9x9, побувавши точно один раз на полі. Маршрут короля не замкнений і, можливо, самоперетинається. Яка найбільша можлива довжина такого маршруту, якщо довжина ходу по діагоналі дорівнює , по вертикалі або горизонталі — 1?

Схожі: