понеділок, 6 лютого 2017 р.

Метод інваріантів

"Не будемо сперечатися, 
дослідимо істину." 
Г. В. Лейбніц.
Метод інваріантів

В деяких олімпіадних задач з математики зустрічається така ситуація. Деяка динамічна система послідовно переходе з одного стану в другий. І треба з’ясувати про деяку властивість цієї  систему в кінцевому стані. Однак повністю прослідкувати за усіма переходами виявляється складно, проте відповісти на це питання допомогає  обчислення деякої величини, яка характерна для всіх станів  системи, тобто ця величина зберігається постійною(інваріантною). Зрозуміло, що набагато легше перевірити значення інваріанту у початковому стані системи і у кінцевому кінцевому, аби дати відповідь на запитання задачі.
На практиці метод інваріантів зводиться до того, що деяка величина обчислюється двома способами: спочатку вона просто обраховується в початковому та кінцевому положенні, а потім прослідкувати її зміну при послідовних переходах системи.
Найчастіше вживаний інваріант – це парність числа. Проте інваріантом може бути також і остача від ділення не тільки на 2, а на довільне натуральне число.
В задачах, де потрібно з'ясувати, чи можна за допомогою заданих операцій перейти від одного об'єкта до другого, часто корисно знайти "інваріант" - числову характеристику об'єктів (або функцію з якимись іншими значеннями на множині об'єктів), - яка не змінюється при вказаних операціях. Якщо при цьому значення інваріанта на двох об'єктах різні, то перетворити один в інший неможна. В цілочиеельних та інших "дискретних*1 задачах інваріантом часто може бути остача від ділення на 2 (парність) або на інший натуральний дільник.
Інваріант –  це величина, яка не змінюється в результаті деяких операцій (наприклад, розрізання і перестановка частин фігур не міняє сумарної площі). Якщо інваріант розрізняє два положення, то від одного не можна перейти до іншого. Як інваріант може використовуватися парність або розфарбовування. У завданнях про суму цифр використовуються залишки від ділення на 3 або 9.
 Напівінваріант – величина, що змінюється тільки в один бік (тобто яка може тільки збільшуватися або тільки зменшуватися). Поняття напівінваріанта часто використовується при доведеннях зупинки процесів.
Якщо всі задані операції оборотні, то вся множина об'єктів, над якими вони виконуються, розбивається на класи еквівалентності (два об'єкти еквівалентні, якщо один з них може бути одержаний з другого за допомогою даної операції (операцій)).
В задачах, де потрібно оцінити кількість операцій чи довести, що їх не можна виконувати безліч разів (наприклад, впевнитись у відсутності "циклу"), іноді буває корисно придумати функцію, яка після кожної дії (операції) монотонно зростає (чи спадає).
В задачах, де потрібно з'ясувати, чи можна за допомогою заданих операцій перейти від одного об'єкта до другого, часто корисно знайти "інваріант" - числову характеристику об'єктів (або функцію з якимись іншими значеннями на множині об'єктів),-яка не змінюється при вказаних операціях. Якщо при цьому значення інваріанта на двох об'єктах різні, то перетворити один в інший неможна. В цілочиеельних та інших "дискретних*  задачах інваріантом часто може бути остача від ділення на 2 (парність) або на інший натуральний дільник.
Якщо всі задані операції оборотні, то вся множина об'єктів, над якими вони виконуються, розбивається на класи еквівалентності (два об'єкти еквівалентні, якщо один з них може бути одержаний з другого за допомогою даної операції (операцій)).
В задачах, де потрібно оцінити кількість операцій чи довести, що їх не можна виконувати безліч разів (наприклад, впевнитись у відсутності "циклу"), іноді буває корисно придумати функцію, яка після кожної дії (операції) монотонно зростає (чи спадає).
1. Було 5 аркушів паперу. Деякі з них розрізали на 5 кусків кожний, Потім деякі з одержаних кусків знову розрізали на 5 кусків і так зробили декілька разів. Чи могло в результаті виконання таких дій одержатись 1975 кусків?( інваріантна властивість: кількість кусків після розрізання на п’ять кусків збільшується на чотири. 5+ 4n не рівно1975).
2. На дошці написано числа 1, 2, 3, ..., 19, 20. До­зволяється стерти будь-які два числа а і b і замість них написати чис­ло (a + b - 1). Яке число може залишитись на дошці після 19 таких операцій?
3. На дошці записано числа 1,2, ..., 20. Дозволяєть­ся стерти будь-які два числа а і b і замінити їх на число аb + а + b. Яке число може залишитись на дошці після 19 таких операцій?
4. На дошці написано числа 1, 2, 3, ...,1989. Дозво­ляється стерти будь-які два числа і написати замість них різницю. Чи можна досягти того, щоб на дошці всі числа дорівнювали нулю?
      5. В одній вершині куба написали число 1, в інших нулі. Можна додавати по 1 до чисел, які записані на кінцях довільного ребра. Чи можна добитися того, щоб всі числа ділились на 3 ?
6. В кутку квадрата 3x3 стоїть знак мінус, в усіх інших - плюси. Можна змінити всі знаки в довільному рядку чи довільному стовпчику на протилежні. Чи можна одержати таблицю лише з одних плюсів?
7. Круг поділили на 6 секторів, в кожному лежить по цукерці. За один хід одну цукерку можна перемістити в сусідній сектор. Чи можна зібрати всі цукерки в одному секторі рівно за 20 ходів?

8. На дошці записано числа від 1 до 20. За один крок дозволяється пару чисел х, у замінити на число х + у + 5ху. Чи можна наприкінці отримати число 20002002?

Завдання для вироблення умінь та навичок використовувати властивості інавіанту.
1.  Було 4 аркуші паперу. Деякі з них розрізали на 8 частин, потім деякі з цих частин розрізали знову на 8 частин і т. д. Коли підрахували загальну кількість аркушів, то виявилось, що їх всього 1986. Довести, що підрахунок був неправильний.
2.  На дошці записано числа від 1 до 20. За один крок дозволяється пару чисел х, у замінити на число х + у + 5ху. Чи можна наприкінці отримати число 20002002?
3.  Матч між двома футбольними командами за­кінчився з рахунком 7 : 4. Довести, що був момент, коли перша ко­манда забила стільки м'ячів, скільки другій залишалось забити.
4.  Число х замінили на х2 - 210, з одержаним числом зробили те саме і так 100 разів. Одержали знову число х. Знайти число х.
5.  В трьох вершинах квадрата знаходяться три коники. Вони грають в «чехарду». При цьому коли коник А стрибає через коника В, то після стрибання від попадає в точку, яка симетрична точці А відносно точки В. Чи зможе після декількох стрибків один з коників попасти в четверту вершину даного квадрата?
6.  На доійці записані числа від 1 до 20. Можна довільну пару чисел (х;у) замінити на число х + у + 5ху. Чи можна наприкінці одержати число 19901989?
7.  Фігура ходить по діагоналі прямокутника Іхп (наприклад, для коня це 1x2). При якому п вона зможе попасти з будь-якої клітинки на необмеженій шаховій дошці?
8.  На дошці записані числа від 1 до 20. Можна пару чисел (х;у) замінити на х + у + ху. Яке число залишиться після 19 операцій?
9.  В шести секторах круга лежить по "снікерсу". Можна одночасно пересунути два "снікерси" в сусідні сектори, рухаючи їх в протилежних напрямках. Чи можна одержати таке їх розташування: 5,1,0,0,0,0 ?

10.  В квадраті 8x8 стоять цілі числа. Можна додавати по одиниці до всіх чисел довільного квадрата 3x3 або 4x4. Чи завжди можна добитись того, що всі числа в таблиці ділилися на 3 ?

 Зразки задач на знаходження інваріантних властивостей.
Блок 1. Парність і непарність
Задача 11. Чи можна розміняти 25 карбованців за допомогою десяти купюр вартістю 1, 3 та 5 карбованців?
Розв'язання цієї задачі грунтується на простому спостереженні:   сума парної кількості непарних чисел є парною. Узагальнення цього факту виглядає так: парність суми кількох чисел залежить лише від парності числа непарних доданків: якщо кількість непарних доданків є (не)парна, то і сума також є (не)парною.
Задача 12. Чи можливо шахівницю розміру 8х8 обійти конем, почавши обхід з поля h8, закінчивши його на полі а1 так, щоб на кожному полі побувати рівно один раз.
 Розв’язання: За 63 ходи кінь опиниться в чорній клітинці а1, але непарні ходи коня  завжди закінчуються на білій клітинці. Протиріччя доводить неможливість.
Відповідь: не можна.
Задача 13. Петро купив загальний зошит на 96 аркушів і пронумеру­вав всі його сторінки по порядку числами від 1 до 192. Василь вирвав з цього зошита 25 аркушів і додав всі 50 чисел, що на них були написані. Чи міг він дістати 1990?
Задача 14. В ряд записано числа від 1 до 10. Чи можна розставити між ними знаки "+" та "-" так, щоб значення отриманого виразу дорівнювало нулю?
Зауваження. Врахуйте, що від'ємні числа також бувають парними та непарними.
Задача 15. Коник-стрибунець стрибає вздовж прямої, причому пер­шого разу він стрибнув на 1 см в якийсь бік, другого — на 2 см і так далі. Доведіть, що після 1985 стрибків він не може зупинитися там, де починав.
Задача 16. На дошці виписано числа 1,2,3,..., 1984, 1985. Дозволя­ється стерти з дошки будь-які два числа і замість них записати модуль їх різниці. Врешті-решт на дошці залишається одне число. Чи може воно дорівнювати нулю?

Блок 2. Олімпіадні задачі на інваріант.

Задача 1. Дана шахова дошка. Дозволяється перефарбувати в другий колір одразу всі клітинки якої-небудь горизонталі чи вертикалі. Чи може при цьому утворитися дошка, у якої рівно одна чорна клітинка?
Розв’язання. При перефарбуванні горизонталі чи вертикалі, яка містить  к  чорних та 8-к білих клітинок, отримаємо 8-к чорних та к білих клітинок. При цьому кількість чорних клітинок зміниться на парне число, тобто (8-к)- к = 8-2к = 2(4-к). Так як парність чорних клітинок зберігається, із початкових 32 чорних клітинок ми не можемо отримати одну чорну клітинку. Відповідь: не можна.
Задача 2. Було 5 аркушів паперу. Деякі з них розрізали на 5 кусків кожний, Потім деякі з одержаних кусків знову розрізали на 5 кусків і так зробили декілька разів. Чи можна в результаті виконання таких дій отримати 1975 кусків паперу?
Розв’язання. Під час розрізання одного куска кількість кусків збільшується на 4. Тому остача від ділення кількості всіх кусків на 4 не змінюється. Але 5 при ділення на 4 дає остачу 1, а 1975 остачу 3.
Відповідь: не можна
Задача 3. В одній вершині куба написали число 1, в інших нулі. Можна  додавати по 1 до чисел, які записані на кінцях довільного ребра. Чи можна добитися того, щоб всі числа ділились на 3 ?
Розв’язання. Пофарбуємо вершини в шаховому порядку. Після цього сума чисел в білих вершинах завжди буде відрізнятись на 1 від суми цифр в чорних вершинах, бо до тих і других кожен раз додається 1.
Відповідь: не можна.
Задача 4. 1989 чоловік вишикувані в шеренгу. Чи завжди їх можна вишукувати по росту, якщо дозволяється міняти місцями двох людей, які стоять через одного?
Розв’язання. При перестановках зберігається парність номера місця. Тому, коли самий високий стоїть на парному місці, він ніколи не стане першим.
Відповідь: не завжди
Задача 5. В кутку квадрата 3x3 стоїть знак мінус, в усіх інших - плюси. Можна змінити всі знаки в довільному рядку чи довільному стовпчику на протилежні. Чи можна одержати таблицю лише з одних плюсів?
Розв’язання. Кількість мінусів у кутовому квадраті 2x2 завжди буде непарною. Відповідь: не можна
Задача 6. Круг поділили на 6 секторів, в кожному лежить по цукерці. За один хід одну цукерку можна перемістити в сусідній сектор. Чи можна зібрати всі цукерки в одному секторі рівно за 19 ходів?
Розв’язання. Пофарбуємо сектори в  шаховому порядку. Різниця цукерок, що лежать у різнокольорових секторах непарна після  непарного ходу.  Відповідь: не можна
Блок 3.  Цікаві задачі на інваріант.

Приклад 1. На чудо-дереві ростуть банани і ананаси. За один раз дозволяється зірвати з неї два плоди. Якщо зірвати два банани або два ананаси, то виросте ще один ананас, а якщо зірвати один банан і один ананас, то виросте один банан. У результаті залишився один  плід. Який це плід, якщо відомо, скільки бананів і ананасів росло спочатку?
Розв’язання. Парність числа бананів не міняється, тому, якщо число бананів було парним, то плід, що залишився, –  ананас, якщо число бананів було непарним, то – банан.
Приклад 2. У одній клітці квадратної таблиці 4x4  стоїть знак мінус, а в інших стоять плюси. Дозволяється одночасно міняти знак у всіх клітках, розташованих в одному рядку або в одному стовпці. Доведіть, що, скільки б ми не проводили таких змін знаку, нам не вдасться отримати таблицю з одних плюсів.
Розв’язання. Замінимо знак «+» на число 1 і знак «—» на число  – 1. Відмітимо, що добуток всіх чисел в таблиці не міняється при зміні знаку у всіх чисел стовпця або рядка. У початковому положенні цей добуток рівний - 1, а в таблиці з одних плюсів добуток рівний  +1, чим і доведена неможливість переходу.
Приклад 3. На прямій розташовано дві фішки: зліва червона, справа синя. Дозволяється проводити будь-яку з двох операцій: вставку - двох фішок одного кольору підряд (між фішками або з краю) і видалення пари сусідніх одноколірних фішок (між якими немає інших фішок). Чи можна за допомогою таких операції залишити на прямій рівно дві фішки: зліва синю, а справа червону?
Розв’язання. Розглянемо число різноколірних пар (не тільки сусідніх), де ліва фішка червона, і відмітимо, що парність цього показника не міняється. Але в початковій ситуації наш показник рівний 1, а в бажаній ситуації –  нулю. Тому перейти до бажаної  ситуації неможливо.
Приклад 4. На острові Сіробуромалін живуть хамелеони: 13 сірих. 15 бурих і 17 малинових. Якщо два хамелеони різних кольорів зустрічаються, то вони обидва змінюють свій колір на третій. Чи може трапитися, що в деякий момент всі хамелеони на острові стануть одного кольору?
Розв’язання. Позначимо кількості хамелеонів кожного кольору С, Б і М відповідно. Доведіть, що залишки від ділення на 3 різниць  Б-С, С-М і М - В не міняються.
Приклад 5. На 44 деревах, розташованих по кругу, сиділи по одному веселому чижеві. Час від часу якісь два чижі перелітають один за годинниковою стрілкою, а інший проти,  кожен – на сусіднє дерево. Чи можуть всі чижі зібратися на одному дереві?
Розв’язання. Пронумеруємо дерева по кругу від 1 до 44. Сума номерів дерев, на яких сидять чижі, або не міняється, або зменшується на 44. або збільшується на 44. Тим самим, залишок від ділення цієї суми номерів на 44 не міняється. Спочатку цей залишок рівний 22, а якщо всі чижі всядуться на одне дерево, то він буде рівний нулю. Тому чижі не зможуть зібратися на одному дереві.
Приклад 6. Чи можна круг розрізати на декілька частин, з яких скласти квадрат? (Розрізи – це ділянки прямих і дуги кіл.)
Розв’язання. Розглянемо інваріант: (різниця сум довжин увігнутих і опуклих розрізаних дуг всіх частин. Ця величина не змінюється при розрізанні однієї частини на дві і при складанні однієї частини з двох. Для одиничного круга цей інваріант рівний; два помножити на число «пі», а для квадрата – нулю( немає опуклих і випуклих частин). Тому квадратура круга  неможлива.

Задачі початкового рівня на інваріант для самостійного осмислення ІНВАРІАНТА.
1. Було 5 аркушів паперу. Деякі з них розрізали на 5 кусків кожний, Потім деякі з одержаних кусків знову розрізали на 5 кусків і так зробили декілька разів. Чи могло в результаті виконання таких дій одержатись 1975 кусків?( інваріантна властивість: кількість кусків після розрізання на п’ять кусків збільшується на чотири. 5+ 4n не рівно1975).
2. На дошці написано числа 1, 2, 3, ..., 19, 20. До­зволяється стерти будь-які два числа а і b і замість них написати чис­ло (a + b - 1). Яке число може залишитись на дошці після 19 таких операцій?
3. На дошці записано числа 1,2, ..., 20. Дозволяєть­ся стерти будь-які два числа а і b і замінити їх на число аb + а + b. Яке число може залишитись на дошці після 19 таких операцій?
4. На дошці написано числа 1, 2, 3, ...,1989. Дозво­ляється стерти будь-які два числа і написати замість них різницю. Чи можна досягти того, щоб на дошці всі числа дорівнювали нулю?
      5. В одній вершині куба написали число 1, в інших нулі. Можна додавати по 1 до чисел, які записані на кінцях довільного ребра. Чи можна добитися того, щоб всі числа ділились на 3 ?
6. В кутку квадрата 3x3 стоїть знак мінус, в усіх інших - плюси. Можна змінити всі знаки в довільному рядку чи довільному стовпчику на протилежні. Чи можна одержати таблицю лише з одних плюсів?
7. Круг поділили на 6 секторів, в кожному лежить по цукерці. За один хід одну цукерку можна перемістити в сусідній сектор. Чи можна зібрати всі цукерки в одному секторі рівно за 20 ходів?
8. На дошці записано числа від 1 до 20. За один крок дозволяється пару чисел х, у замінити на число х + у + 5ху. Чи можна наприкінці отримати число 20002002?
  
Практична частина заняття.
Завдання для вироблення умінь та навичок використовувати властивості інавіанту.
1.  Було 4 аркуші паперу. Деякі з них розрізали на 8 частин, потім деякі з цих частин розрізали знову на 8 частин і т. д. Коли підрахували загальну кількість аркушів, то виявилось, що їх всього 1986. Довести, що підрахунок був неправильний.
2.  На дошці записано числа від 1 до 20. За один крок дозволяється пару чисел х, у замінити на число х + у + 5ху. Чи можна наприкінці отримати число 20002002?
3.  Матч між двома футбольними командами за­кінчився з рахунком 7 : 4. Довести, що був момент, коли перша ко­манда забила стільки м'ячів, скільки другій залишалось забити.
4.  Число х замінили на х2 - 210, з одержаним числом зробили те саме і так 100 разів. Одержали знову число х. Знайти число х.
5.  В трьох вершинах квадрата знаходяться три коники. Вони грають в «чехарду». При цьому коли коник А стрибає через коника В, то після стрибання від попадає в точку, яка симетрична точці А відносно точки В. Чи зможе після декількох стрибків один з коників попасти в четверту вершину даного квадрата?
6.  На доійці записані числа від 1 до 20. Можна довільну пару чисел (х;у) замінити на число х + у + 5ху. Чи можна наприкінці одержати число 19901989?
7.  Фігура ходить по діагоналі прямокутника 1хп (наприклад, для коня це 1x2). При якому п вона зможе попасти з будь-якої клітинки на необмеженій шаховій дошці?
8.  На дошці записані числа від 1 до 20. Можна пару чисел (х;у) замінити на х + у + ху. Яке число залишиться після 19 операцій?
9.  В шести секторах круга лежить по "снікерсу". Можна одночасно пересунути два "снікерси" в сусідні сектори, рухаючи їх в протилежних напрямках. Чи можна одержати таке їх розташування: 5,1,0,0,0,0 ?
10.  В квадраті 8x8 стоять цілі числа. Можна додавати по одиниці до всіх чисел довільного квадрата 3x3 або 4x4. Чи завжди можна добитись того, що всі числа в таблиці ділилися на 3?
Задачі підвищеної складності для самостійного розв'язування
Задача 1. (7-8). На дошці написано числа 1, 2, 3, ..., 23, 24. До­зволяється стерти будь-які два числа а і b і замість них написати чис­ло (a + b - 1). Яке число може залишитись на дошці після 23 таких операцій?
Задача 2. (7-9). На дошці записано числа 1,2, ..., 24. Дозволяєть­ся стерти будь-які два числа а і b і замінити їх на число аb + а + b. Яке число може залишитись на дошці після 23 таких операцій?
Задача 3. (7-8). На дошці написано числа 1, 2, 3, ...,1989. Дозво­ляється стерти будь-які два числа і написати замість них різницю. Чи можна досягти того, щоб на дошці всі числа дорівнювали нулю?
Задача 4. (7-8). Обмінний автомат міняє одну монету на п'ять інших. Чи можна за його допомогою розміняти металеву гривню на 26 монет?
Задача 5. (7-8). У вершинах куба розставлено такі числа: 7 ну­лів і одна одиниця. За один хід дозволяється додавати по одиниці до чисел в кінцях будь-якого ребра куба. Чи можна досягти того, щоб усі числа стали рівними між собою? А чи можна досягти того, щоб усі числа ділились на 3?
Задача 6. (7-9). У кожній клітинці таблиці 8x8 записано по одиниці. Дозволяється за один хід додати по одиниці до всіх чисел будь-якого квадрата 3x3 . Чи можна за допомогою скінченої кілько­сті таких ходів отримати у вершинах деякого квадрата 4x4 суму чи­сел, що дорівнює 2001?
Задача 7. (8-9). На столі лежить купа з 1001 каменя. Хід поля­гає в тому, що з якоїсь купи, що містить більше одного каменя, вики­дають камінь, а потім одну з цих куп ділять на дві. Чи можна через кілька ходів залишити на столі лише купки, що складаються з трьох камінців?
Задача 8. (8-9). Було 4 аркуші паперу. Деякі з них розрізали на 8 частин, потім деякі з цих частин розрізали знову на 8 частин і т. д. Коли підрахували загальну кількість аркушів, то виявилось, що їх всього 1986. Довести, що підрахунок був неправильний.
Задача 9. (9-11). На дошці записано числа від 1 до 20. За один крок дозволяється пару чисел х, у замінити на число х + у + 5ху. Чи можна наприкінці отримати число 20002002?
Задача 10. (7-8). Матч між двома футбольними командами за­кінчився з рахунком 7 : 4. Довести, що був момент, коли перша ко­манда забила стільки м'ячів, скільки другій залишалось забити.


Теореми  про інваріантні  остачі при діленні степенів на натуральні числа.

Варто мати на увазі, що квадрати цілих чисел при діленні на 3 або 4 можуть давати остачі лише 0 та 1, куби при діленні на 9 - лише 0,  1 та 8. (Перевірте це са­мостійно). Подібні факти в поєднанні з вдалим вибором числа, остачі при діленні на яке ми розглядаємо, часто допомагають розв'язуванню. З допомогою такого вдалого вибору можна доводити, що число не є простим, можна розв'язувати рівняння в цілих числах.

Квадратні лишки
Остачі при діленні квадратів на натуральні числа.

Якщо квадрат натурального числа, тобто,  m2 = m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1
4, то отримаємо остачі 0, 1;
5, то отримаємо остачі 0, 1, 4;
6, то отримаємо остачі 0, 1, 3, 4;
7, то отримаємо остачі  0, 1, 2, 4;
8, то отримаємо остачі  0, 1, 4;
9, то отримаємо остачі 0, 1, 4, 7;
10, то отримаємо остачі 0, 1, 4, 5, 6, 9;
11, то отримаємо остачі 0, 1, 3, 4, 5, 9;
12, то отримаємо остачі 0, 1, 4, 9;
13, то отримаємо остачі 0, 1, 3, 4, 9, 10, 12;
14, то отримаємо остачі 0, 1, 2, 4, 8, 9;
15, то отримаємо остачі 0, 1,4, 6,  9, 10;
16, то отримаємо остачі 0, 1, 4, 9;
17, то отримаємо остачі 0, 1, 4, 8, 9,15.



Кубічні лишки
Остачі при діленні кубів на натуральні числа.

Якщо куб натурального числа, тобто,  m3 = m∙m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1, 2;
4, то отримаємо остачі 0, 1, 3;
5, то отримаємо остачі 0, 1, 2, 3, 4;
6, то отримаємо остачі 0, 1, 2, 3, 4, 5;
7, то отримаємо остачі  0, 1, 6;
8, то отримаємо остачі  0, 1, 3, 5, 7;
9, то отримаємо остачі  0, 1, 8;
10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9
Таблиця остач при діленні кубів на цифри
1
2
3
4
5
6
7
8
9
1
0
1
1
1
1
1
1
1
1
23
0
0
2
0
3
2
1
0
8
33
0
1
0
3
2
3
6
3
0
43
0
0
1
0
4
4
1
0
1
53
0
1
2
1
0
5
6
5
8
63
0
0
0
0
1
0
6
0
0
73
0
1
1
3
3
1
0
7
1
83
0
0
2
0
2
2
1
0
8
93
0
1
0
1
0
3
1
1
0

Четвіркові лишки
Остачі при діленні четвертих степенів на натуральні числа.

Якщо четверту степінь натурального числа, тобто,  m4 = m∙m∙m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1
4, то отримаємо остачі 0, 1;
5, то отримаємо остачі 0, 1;
6, то отримаємо остачі 0, 1, 3, 4;
7, то отримаємо остачі  0, 1, 2, 4;
8, то отримаємо остачі  0, 1;
9, то отримаємо остачі 0, 1, 4, 7;
10, то отримаємо остачі 0, 1, 5, 6;

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

Якщо п’яту степінь натурального числа, тобто,  m5 = m∙m∙m∙m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1, 2;
4, то отримаємо остачі 0, 1, 3;
5, то отримаємо остачі 0, 1, 2, 3, 4;
6, то отримаємо остачі 0, 1, 2, 3, 4, 5;
7, то отримаємо остачі  0, 1, 2, 3, 4, 5, 6;
8, то отримаємо остачі  0, 1, 3, 5, 7;
9, то отримаємо остачі  0, 1, 2, 4, 5, 7, 8;
10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.

Розв’язування числових задач

n
n2
n3
n4
n4k
nk
...1
1
1
1
1
1
2
4
8
6
6
2,4,8,6
3
9
7
1
1
3,9,7,1
4
6
4
6
6
4,6
5
5
5
5
5
5
6
6
6
6
6
6
7
9
3
1
1
7,9,3,1
8
4
2
6
6
8,4,2,6
9
1
9
1
1
9,1
0
0
0
0
0
0
 У цій таблиці наведено останні цифри натуральних чисел, квадратів, кубів, четвертих степенів і так далі.
Використовуємо цю таблицю для розв’язування задач.
Задача 1. Знайти остачу від ділення квадрата цілого числа на 5.
Розв’язання:
Квадрати натуральних чисел закінчуються цифрами: 0; 1; 4; 5; 6; 9.(колонка 2) то при їх діленні  на 5 одержуємо 0, 1 або 4.
Задача 2. Чи може число виду 1k+5m+6n, де k, m, n – довільні натуральні числа, бути довільним квадратом.
Розв’язання: Кожний доданок закінчується відповідно цифрами: 1, 5 і 6 (колонка 6) і тому їх сума закінчується цифрою 2, а таке число не може бути точним квадратом.
Задача 3. Довести, що число 5353- 3333 ділиться на 10.
Розв’язання: При виділенні показників степенів 53 і 33 на 4 в остачі одержуємо в кожному випадку 1. Отже, остання цифра числа 5553 така сама, як числа 3333, бо 534∙13+1 і 334∙8+1, отже, остання цифра різниці 0, і ця різниця ділиться на 10.
 Задача 4. Які остачі можуть мати точні квадрати при діленні на 3?
Відповідь: 0; 1; (3k±1)2=9k2±6k+1.    (3k)2=9k.
Задача 5. Які остачі не можуть мати точні квадрати при діленні на 4?
(2k)2=4k2
(2k+1)2=4k2+4k+1
Відповідь: 2; 3.
Задача 6. Які остачі не можуть мати точні квадрати при діленні на 5?
Відповідь:2 і 3. (5k)2=25k2+0
(5k±1)2=25k2±10k+1
(5k±2)2=25k2±20k+4
Задача 7. Довести, що при будь-якому цілому n число n(n-3)(n2-3n+14) ділиться на 24?
Доведення:
n (n-3)(n2-n-2n+2+12)=n(n-3)(n(n-1)-2(n-1)+12=n(n-3)(n-1)(n-2)+12n(n-3). Це число ділиться на 24, бо:
1.      n(n-1)(n-2)(n-3) ділиться на 3і 8 Þділиться на 24.
2.      12n(n-3) ділиться на 12 і 2, бо n(n-3)- просте число, отже, ділиться на 24.
3.       
Властивості квадратних лишків

Теорема 1. Завжди знайдеться натуральний дільник  n, більшого 1,  для  довільного степеня натурального числа mk, який при ділення степеня на цей дільник n дає остачу 1, (або завжди можна знайти такі  натуральні числа, що (mk– 1):n – натуральне число).
Тобто рівняння з двома невідомими завжди має  розв’язки в натуральних числах
mk - 1º0(mod m-1). 
Теорема 2. Завжди знайдеться натуральний дільник n, більший 5, для  довільного квадрату натурального числа, який при ділення квадрата на цей дільник дає остачу 4.
Тобто, рівняння з двома невідомими завжди має  розв’язки в натуральних числах
m2 º4(mod m+2) або m2 º4(mod m-2)  .
Теорема 3. Завжди знайдеться такий натуральний дільник n для  довільного квадрату натурального числа, який при ділення на цей натуральний дільник дає остачу 0.
Тобто рівняння з двома невідомими m i n завжди має  розв’язки в натуральних числах
m2 º 0(mod n).
Теорема 4. Завжди знайдеться такий натуральний дільник n, більший 9,  для  довільного квадрату натурального числа, який при ділення на цей натуральний дільник n дає остачу 0.
Тобто рівняння з двома невідомими завжди має  розв’язки в натуральних числах
m2 º9(mod n).
Тобто рівняння з двома невідомими m i n завжди має  розв’язки в натуральних числах
m2 º9(mod m+3) або m2 º9(mod m-3).


Розглянемо де­кілька прикладів.
Задача. Чи існують чотири  натуральних числа,  що йдуть підряд, кожне з яких можна подати у вигляді суми двох квадратів?
Розв'язання.
Ні, не існують. Розглянемо остачі при діленні на 4. Квадрат може дати остачу 0 або 1, сума двох квадратів - 0, 1 або 2. серед чотирьох підряд чисел знай­деться таке, що має остачу 3. Воно на суму двох квадратів не розкладається.
Задача. Знайти всі такі р, що числа р, р + 10 та р + 14 прості.
Розв'язання.
Єдина відповідь p=3. Якщо p не ділиться на 3, то при p=3k + 1 число p+14 ділиться на 3, при p=3k+2 число p+10 ділиться на 3.


Задачі для самостійного осмислення

1. Рівняння з двома невідомими
m2 º 3(mod n).
 має  розв’язки в цифрах тільки один розв’язок  m = 3, n = 6.
(Умова задачі на це рівняння. Знайти двоцифрове число, у якого квадрат цифри десятків при діленні на цифру одиниць дає остачу, що дорівнює половині цифри  одиниць. Відповідь: 36.)
2. Рівняння з двома невідомими
m2 º2(mod n).
 має  розв’язки в цифрах тільки два розв’язки:  m = 3, n = 7. m = 4, n = 7.
(Умова задачі на це рівняння.  Знайти двоцифрові число, у яких  квадрат цифри десятків при діленні на цифру одиниць дає остачу 2. Відповідь: 37 та 47.)
3. Чи існує магічний квадрат 3х3 , складений з натуральних чисел так, щоб виконувалася умова на парність чисел? (У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).

2n
2k-1
2r
2d-1
2t-1
2m-1
2c
2a-1
2k

Відповідь: існує, це магічний квадрат 3х3, з цифр 1, 2, 3, 4, 5, 6, 7, 8, 9.
4. Чи існує магічний квадрат 3х3, складений з натуральних чисел так, щоб виконувалася умова на парність чисел?(У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).

2n
2k-1
2r
2d-1
2t
2m-1
2c
2a-1
2k
 Відповідь: не існує.
4.Чи існує така цифра, більша 1, яка ділиться на число вигляду m2 – 8. Відповідь: не існує.
5. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 5. Відповідь: 58, 56.
6. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 12, 32, 52, 72, 92. 23, 53, 83, 34, 74, 45, 56, 57, 78,  29, 89, 59.
7. Знайти двоцифрові числа, у яких куб цифри десятків  при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків. Відповідь: 12, 23, 34, 45, 56, 67, 78, 89.
8. (Теорема: m3 = m(mod m +1) та m3 = m(mod m -1), де m >1 )Доведіть, що всі двоцифрові числа, у яких цифри розташовані послідовно у порядку зростання, володіють такою властивістю: «куб цифри десятків  при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків.»
9.   Знайти  усі двоцифрові числа, у яких куб цифри десятків  ділиться на цифру одиниць без остачі. Відповідь: 22,  42,  62,  82,  33,  44, 63,  93,  84,  64, 55,  66, 77, 88, 28, 48, 68,39, 69, 99.

10.               Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 6, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 57, 67.
Опубліковано о

Немає коментарів:

Дописати коментар

Підписатися на: Дописати коментарі (Atom)