Матеріали до уроку "Інваріанти"

Про матеріал

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

Перегляд файлу

Інваріанти

Вступна інформація

Інваріа́нт (рос. инвариант, англ. invariant, нім. Invariante) — термін, що використовується в математиці та фізиці, а також в програмуванні. Ін - внутрішнє, варіант - взятий за ознаками (критеріями, значеннями, властивостями чи сумою властивостей) параметризований, маркований параметр, чи сукупність параметрів, що означає щось незмінне в полі (діапазоні, просторі, масиві, множині, послідовності) значень. За звичай це статистичний максимум чи константа в полі значень. Наприклад нуль за Цельсієм чи Фаренгейтом, одна атмосфера в умовах планети Земля. Це міра природніх калібрів чи статистичних оцінок взятих за маркери описання чи обрахунків у фізиці чи математиці. Складає основу метрології, як методологія каліброваних та відносних мір. Характерна особливість - позначення в шкалах каліброваних значень для екстраполяції на інші діапазони. Тому інваріант є саме визначення стабільна характеристика, показник, значення в послідовності чи на шкалі визнаний константою, тобто оптимум в варіабельності значень (станів, характеристик, сукупності властивостей, тощо). Саме тому при моделюванні і математичних обрахунках інваріанти є базовими константами (мірою, маркерами) розрахунків та перетворень.

Інваріант – число, вираз тощо, які пов’язані з деяким математичним об'єктом і не змінюються при певних перетвореннях. Наприклад, віддаль між двома точками площини є інваріантом при перенесенні або повертанні системи координат; площа будь-якої фігури, кут між двома прямими — інваріанти руху. Похідний термін — інваріантність — властивість системи не змінювати своїх характеристик при перетвореннях.

Мета та завдання:

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

Рекомендації до вивчення теми.

Використання.

Електричне і магнітне поле, створені зарядами і струмами, для спостерігачів у різних системах відліку суть різні. Це неважко зрозуміти, розглянувши поле, створене зарядом. Для спостерігача в тій системі відліку, відносно якої заряд непорушний, це поле чисто електричне, а спостерігач, який рухається відносно заряду, зафіксує як електричне, так і магнітне поле, оскільки в його системі відліку заряд рухається, створюючи струм.

Однак, із напруг електричного та магнітного полів можна сформувати певні вирази, які будуть однаковими в будь-якій системі відліку. Ці вирази називаються інваріантами електромагнітного поля.

Існує два інваріанти:

F_ikF^ik = inv

e^iklmF_ikF_lm = inv,

де F^ik — 4-тензор електромагнітного поля, , e^iklm — одиничний антисиметричний тензор.

В звичніших позначеннях ці інваріанти переписуються як

$Описание: \mathbf{E}^2 - \mathbf{H}^2 = \text{inv}$

$Описание: \mathbf{E} \cdot \mathbf{H} = \text{inv}$

де $Описание: \mathbf{E}$ — напруженість електричного поля, $Описание: \mathbf{H}$ — напруженість магнітного поля.

Наслідки:

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

Якщо в якійсь системі відліку E > H, то це залишатиметься справедливим у будь-якій системі відліку. Якщо між векторами $Описание: \mathbf{E}$ та $Описание: \mathbf{H}$ гострий або тупий кут в одній системі відліку, то це справедливо для будь-якої іншої системи.

Зразки для розв’язування завдань.

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

Розв’язок: Слон завжди залишиться на полях одного кольору (це і є інваріант даного завдання). Тому якщо тура кожним своїм ходом зупинятиметься на полі іншого кольору, її неможливо буде побити.

Завдання: Дитя опанувало всього лише два звуки: "У" і "А", причому два слова в лексиконі цього дитяти означають одне і те ж, якщо одне виходить з іншого за допомогою наступних перетворень: виключення тих, що йдуть підряд звуків "УА" або "ААУУ" і додавання в будь-яке місце поєднання "АУУА". Доведіть, що слова "ААУАААУУА" і "ААУУААА" означають одне і те ж.

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

Завдання. Було 4 аркуші паперу. Деякі з них розірвали на 4 частини, потім деякі з четвертинок знову розірвали на 4 частинки і т.д. Коли полічили загальну отриману кількість клаптиків, то виявилося, що їх 2010. Чи правильно полічили?

Розв’язок. Якщо постійно рахувати отриману кількість клаптиків після розірвання чергового аркуша, то їх стає: 7, 10, 13, 16, ..., тобто після кожного чергового збільшення клаптиків їх кількість зростає на 3. Але як прив’язати 2010 до цього зростання? Остача від ділення всіх цих чисел на 3 дорівнює 1 і залишається незмінною, тобто інваріантом. Оскільки остача від ділення 2010 на 3 дорівнює 0, тобто полічили неправильно.

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

Що є інваріантом. «Магічні квадрати», як графічний приклад інваріантів

Інваріант - число, вираз тощо, які пов'язані з деяким математичним об'єктом і не змінюються при певних перетвореннях. Наприклад, віддаль між двома точками площини є інваріантом при перенесенні або повертанні системи координат; площа будь-якої фігури, кут між двома прямими - інваріанти руху. Похідний термін - інваріантність - властивість системи не змінювати своїх характеристик при перетвореннях.
Задачі на інваріанти - це великий шар задач олімпіадної тематики. Розв'язування таких задач - доволі складний процес, для вдалого виконання якого людина повинна вміти думати, аналізувати. Необхідно також досконале знання фактичного матеріалу, володіння загальними підходами до розв'язування задач, досвід в дослідженні нестандартних задач.
Не можна не погодитися з висловом відомого американського математика Д. Пойа: «Якщо учень заповнить відведений йому навчальний час тільки стандартними вправами, то він загубить інтерес, загальмує свій розумовий розвиток та втратить свої можливості».
Формуванню досвіду під час розв’язування нестандартних задач на інваріанти присвячені наступні розділи роботи.
«Магічні квадрати» - це перший інваріант, що зустрічається в позакласних заняттях математикою. Проте слід зазначити, що теорія магічних квадратів ще далека до завершення. Скажемо, що ще не знайдено відповіді на запитання - скільки різних заповнень має квадрат четвертого порядку натуральними числами від 1 до 16 ( не говорячи про заповнення іншими довільними 16 числами).

Загальна задача «магічних» квадратів: дані числа розставити у клітинках квадрата так, щоб у рядках, стовпцях, діагоналях утворилися однакові суми. Ми не будемо розглядати утворення похідних «магічних» квадратів четвертого порядку переміщенням стовпців, рядків та поворотом квадрата навколо центра. Дамо вичерпну відповідь на запитання, як заповнити квадрат третього порядку. Умову задачі в загальному вигляді сформулюємо так: «За трьома заданими числами (назвемо їх базовими) у клітинках квадрата заповнити квадрат так, щоб у рядках, стовпцях, діагоналях утворилися однакові суми. Числа в клітинках квадрата можуть повторюватися( а також можуть бути дробовими чи від’ємними). Якщо базові числа задано по діагоналі, то задача вимагає дослідження, а саме: має задача безліч розв’язків чи не має жодного. Отже, треба однозначно відповісти на запитання, коли заповнення квадрата єдине, коли має безліч заповнень, а коли заповнення неможливе.

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

КЛАСИФІКАЦІЯ ЗАДАЧ НА ІНВАРІАНТИ

Серед розмаїття математичних задач є такі, які можна об'єднати під рубрикою «Задачі на відображення». Їх загальна постановка формулюється так: «Є множина А елементів a, b, c,... довільної природи і множина Х споріднених елементів x. y. z... а також відображення, яке перетворює елементи множини А у подібні їм елементи. Чи можна, вдаючись до неодноразового перетворення елементів множини А за допомогою відображення , одержати той чи інший елемент з множини Х? Відповідь у цих задачах коротка – « так» або «ні» Звісно, задача вважається розв’язаною, якщо відповідь обґрунтована. Для обґрунтування заперечення часто використовують інваріанти: величини, співвідношення, відповідності тощо - все те, що не змінюється у процесі виконання заданих у задачі перетворень. Текстові задачі на інваріанти. Якщо заданий елемент або елементи з множини Х не відповідають цим величинам, не володіють співвідношеннями, не справджують відповідності, то ці елементи не можна дістати в результаті перетворення заданих елементів множини А. Збереження інваріантності є лише необхідною умовою досягнення позитивного результату. Інваріанти дають підставу тільки для негативної відповіді. Визначивши інваріант деякого процесу в багатьох випадках можна з’ясувати питання про можливість певного результату цього процесу. При цьому рівність інваріанта на початку та наприкінці процесу ще не забезпечує цієї можливості. Тому, як правило, в таких задачах відповідь на це запитання негативна. У ролі інваріанта може застосовуватись парність, залишок від ділення на деяке число та інше. Поняття інваріантів, їх вибір та застосування розглянемо під час розв'язування задач.

Завдання для самостійної роботи.

1. Є квадратна таблиця 10х10, в клітини якої в послідовному порядку вписані натуральні числа від 1 до 100: у перший рядок - числа від 1 до 10, в другу - від 11 до 20 і т. д. Доведіть, що сума S будь-яких 10 чисел таблиці , з яких ніякі два не стоять в одному рядку і ніякі два не стоять в одному стовпці, постійна. Знайдіть цю суму.

Розв’язок. Позначимо доданок вихідної суми S з першого рядка через а1, з другої - через 10 + а2, з третьої - через 20 + а3 і т. д., нарешті, з десятої - через 90 + А10. Тут кожне з натуральних чисел а1, а2, ..., А10 укладено в межах від 1 до 10, причому ці числа попарно різні, оскільки, якщо б, наприклад, а1 = а2, то числа а1 і 10 + а2 стояли б в одному стовпці таблиці. Отримуємо: S = а1 + (10 + а2) + (20 + а3) + ... + (90 + А10) = = (10 + 20 + ... + 90) + (а1 + а2 + ... + А10) = 450 + (а1 + а2 + ... + А10). Оскільки числа а1, а2, ..., А10 попарно різні і приймають всі цілі значення від 1 до 10, то кожне з натуральних чисел від 1 до 10 входить в суму а1 + а2 + ... + А10 як доданка рівно один раз. Отже, а1 + а2 + ... + А10 = 1 + 2 +3 + ... + 10 = 55, S = 450 + 55 = 505. Сума S і є інваріантом: якщо в ній одні складові замінити іншими, але так, щоб всі складові нової суми стояли в таблиці в різних рядках і в різних стовпцях, сума візьме, теж саме значення. Відповідь: 505.

2. Аркуш паперу розірвали на 5 шматків, деякі з цих шматків розірвали на 5 частин, а деякі з цих нових частин розірвали ще на 5 частин і т. д. Чи можна таким шляхом отримати 1994 шматка паперу? А 1997?

Розв’язок. При кожному розриванні листа або одного шматка паперу на 5 частин загальне число шматків збільшується на 4. Тому число шматків паперу на кожному кроці може мати тільки вид 4k + 1 (k-натуральне число). Цей вислів і є інваріантом.

3. . Кожне натуральне число від 1 до 50000 замінюють числом рівним сумі його цифр. З отриманими цифрами проробляють ту ж операцію, і так надходять до тих пір, поки всі числа не стануть однозначними. Скільки разів серед цих однозначних чисел зустрінеться кожне з цілих чисел від 0 до 8?

Розв’язок. Зазначені однозначні числа в послідовному порядку такі: 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2,3, 4, 5, 6, 7, 8, 0, .... Ця закономірність зберігається і далі. Справді, при заміні натурального числа сумою його цифр залишок від ділення числа на 9 залишається незмінним, тому при переході від кожного натурального числа до наступного залишок від ділення числа на 9 збільшується на 1 або перескакує від 8 до 0. Для того щоб дізнатися, скільки таких груп цифр по 9 цифр у кожній, розділимо 50000 на 9 із залишком: 50000 = вересня 5555 + 5. Отже, таких груп 5555. Ще одну, неповну групу утворюють останні 5 цифр: 1, 2, 3, 4, 5. Відповідь: 1, 2, 3, 4, 5 - по 5556 раз, 6, 7, 8, 0 - 5555 разів.

4.Круг розбитий на 6 рівних секторів, в яких розставлені цифри 0, 1, 2, 0, 2, 1 (у зазначеному порядку). Дозволяється за один хід одночасно додавати одне і те ж число до двох що стоять поруч числам. Чи можна за кілька таких ходів домогтися того, щоб всі 6 чисел, що стоять в секторах були рівні?

Розв’язок. Нехай на деякому кроку в секторах опинилися в послідовному порядку числа а1, а2, а3, а4, а5, А6. Складемо таку суму: S = а1 - а2 + а3 - а4 + а5 - а6. Після кожного ходу вона не змінюється, оскільки кожна з різновидів а1 - а2, а3 - а4, а5 - А6 при збільшенні зменшуваного і від'ємника на одне і те ж число зберігає своє значення, отже, вона є інваріантом. Але в початковому положенні S = 0 - 1 + 2 - 0 + 2 - 1 = 2, а в кінцевому, коли кожне з шести чисел дорівнює одному й тому числу, S = 0. Тому зробити рівними всі шість чисел не можна.

Відповідь: не можна.

5. На диво-яблуні ростуть банани та ананаси. За один раз дозволяється зірвати з неї два плоди. Якщо зірвати два банани або два ананаса, то виросте ще один ананас, а якщо зірвати один банан і один ананас, то виросте один банан. У результаті залишився один плід. Який це плід, якщо відомо, скільки бананів і ананасів росло спочатку?

Розв’язок. Парність числа бананів не змінюється, якщо число бананів було парних, то залишився плід ананас, якщо число бананів було непарним, то - банан.

6. На прямій стоять дві фішки: зліва червона, праворуч синя. Дозволяється проводити будь-яку з двох операцій: вставку двох фішок одного кольору поспіль (між фішками або з краю) і видалення пари сусідніх одноколірних фішок (між якими немає інших фішок). Чи можна за допомогою таких операцій залишити на прямий рівно дві фішки: зліва синю, а справа червону?

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

7. Доведіть, що у грі «15» не можна поміняти місцями фішки «15» і «14», залишивши інші на місці.

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

8. На 44 деревах, розташованих по колу, сиділи по веселому Чижу. Час від часу якісь два чижа перелітають на сусіднє дерево - один за годинниковою стрілкою, а інший - проти. Чи можуть все чижі зібратися на одному дереві?

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

9. Дано 20 карток. На двох картках написана цифра 0, на двох - цифра 1, ... , На двох останніх - цифра 9. Чи можна розташувати ці картки в ряд так, щоб картки з 0 лежали поряд, між картками з 1 лежала рівно одна картка, ... , Між кар ¬ точками з 9 лежало рівно 9 карток?

Розв’язок. Це завдання можна вирішити без всяких інваріантів. Однак для нас вона цікава тим, що у неї є два принципово різних Є квадратна таблиця 10х10, в клітини якої в послідовному порядку вписані натуральні числа від 1 до 100: у перший рядок - числа від 1 до 10, в другу - від 11 до 20 і т. д. Доведіть, що сума S будь-яких 10 чисел таблиці , з яких ніякі два не стоять в одному рядку і ніякі два не стоять в одному стовпці, постійна. Знайдіть цю суму.

Аркуш паперу розірвали на 5 шматків, деякі з цих шматків розірвали на 5 частин, а деякі з цих нових частин розірвали ще на 5 частин і т. д. Чи можна таким шляхом отримати 1994 шматка паперу? А 1997?

11. Кожне натуральне число від 1 до 50000 замінюють числом рівним сумі його цифр. З отриманими цифрами проробляють ту ж операцію, і так надходять до тих пір, поки всі числа не стануть однозначними. Скільки разів серед цих однозначних чисел зустрінеться кожне з цілих чисел від 0 до 8?
Розв’язок. Зазначені однозначні числа в послідовному порядку такі: 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2,3, 4, 5, 6, 7, 8, 0, .... Ця закономірність зберігається і далі. Справді, при заміні натурального числа сумою його цифр залишок від ділення числа на 9 залишається незмінним, тому при переході від кожного натурального числа до наступного залишок від ділення числа на 9 збільшується на 1 або перескакує від 8 до 0. Для того щоб дізнатися, скільки таких груп цифр по 9 цифр у кожній, розділимо 50000 на 9 із залишком: 50000 = вересня 5555 + 5. Отже, таких груп 5555. Ще одну, неповну групу утворюють останні 5 цифр: 1, 2, 3, 4, 5. Відповідь: 1, 2, 3, 4, 5 - по 5556 раз, 6, 7, 8, 0 - 5555 разів.

12.Круг розбитий на 6 рівних секторів, в яких розставлені цифри 0, 1, 2, 0, 2, 1 (у зазначеному порядку). Дозволяється за один хід одночасно додавати одне і те ж число до двох що стоять поруч числам. Чи можна за кілька таких ходів домогтися того, щоб всі 6 чисел, що стоять в секторах були рівні?

Розв’язок. Нехай на деякому кроку в секторах опинилися в послідовному порядку числа а1, а2, а3, а4, а5, А6. Складемо таку суму: S = а1 - а2 + а3 - а4 + а5 - А6. Після кожного ходу вона не змінюється, оскільки кожна з різновидів а1 - а2, а3 - а4, а5 - А6 при збільшенні зменшуваного і від'ємника на одне і те ж число зберігає своє значення, отже, вона є інваріантом. Але в початковому положенні S = 0 - 1 + 2 - 0 + 2 - 1 = 2, а в кінцевому, коли кожне з шести чисел дорівнює одному й тому числу, S = 0. Тому зробити рівними всі шість чисел не можна.

Відповідь: не можна.

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

Доведіть, що у грі «15» не можна поміняти місцями фішки «15» і «14», залишивши інші на місці.

На 44 деревах, розташованих по колу, сиділи по веселому Чижу. Час від часу якісь два чижа перелітають на сусіднє дерево - один за годинниковою стрілкою, а інший - проти. Чи можуть все чижі зібратися на одному дереві?

Дано 20 карток. На двох картках написана цифра 0, на двох - цифра 1, ... , На двох останніх - цифра 9. Чи можна розташувати ці картки в ряд так, щоб картки з 0 лежали поруч, між картками з 1 лежала рівно одна картка, ... , Між кар ¬ точками з 9 лежало рівно 9 карток?

Розв’язок. Це завдання можна вирішити без всяких інваріантів. Однак для нас вона цікава тим, що у неї є два принципово різних рішення, використовуються інваріанти. Уявімо собі 20 ящиків, розкладених в ряд. Переформулюємо завдання наступним чином: чи можна розташувати картки по ящиках так, щоб виконувались дві умови: a) картки з 0 лежать в сусідніх ящиках, картки з 1 - через одну скриньку, ... , Картки з 9 - через дев’ять скриньок; b) у кожному ящику лежить по одній картці? Очевидно, порізно виконати кожну з умов дуже легко. Це й призводить до двох розв’язків . Перший розв’язок. Покладемо в перший ящик 10 карток: Одну - з 0, одну - з 1, ... , Одну - з 9. Потім другу картку з 0 покладемо в другий ящик, другу картку з 1 - у третій ящик, .... другу картку з 9 - в одинадцятий ящик. Умова а) виконується. Ми хочемо спробувати, не порушуючи його, так перекласти картки, щоб умова b) теж виконувалась. Будемо перекладати будь-які дві «однойменні» (з однією і тією ж цифрою) картки через однакове число ящиків. Неважко помітити, що при довільному дозволеному переміщенні відмінність в сумі відбувається на парне число ящиків. Це підказує ідею взяти за інваріант залишок від ділення на 2 суми номерів ящиків, у яких лежать картки.

На столі стоять вверх дном 7 склянок. Дозволяється за один раз перевернути будь-які 4 склянки. Чи можна через кілька кроків поставити всі склянки у нормальний стан?
Розв’язок. Поставимо відповідно склянці, що стоїть нормально, +1, а стоїть догори дном, - 1.Інваріантом тут буде твір чисел, які відповідають усім 7 склянок, оскільки при зміні знака у 4 співмножників твір не змінюється. Але в початковому положенні цей твір дорівнює -1, а значить, стати +1 воно ніколи не зможе.
На дошці написано десять плюсів і п'ятнадцять мінусів. Дозволяється стерти будь-які два знаки і написати замість них плюс, якщо вони однакові, і мінус у протилежному випадку. Який знак залишиться, на дошці після виконання двадцяти чотирьох таких операцій.

Розв’язок. Замінимо кожен плюс числом 1, а кожен мінус числом –1. Дозволена операція описується так: стираються будь-які два числа і записується їх добуток. Тому добуток усіх написаних на дошці чисел залишається незмінним. Так як спочатку цей добуток дорівнював –1, то і в кінці залишиться число –1, тобто знак мінус. Це міркування можна було провести інакше. Замінимо всі плюси нулями, а мінуси – одиницями, і зауважимо, що сума двох праних чисел має ту ж парність, що й число, що записується замість них. Так як спочатку сума всіх чисел була непарною (вона дорівнювала 15), то і останнє, на дошці число буде непарним, тобто одиницею, і, значить, на дошці залишиться мінус. Нарешті, третій розв’язок задачі можна отримати, зауваживши, що в рядок кожної операції число мінусів або не змінюється, або зменшується на два. Оскільки спочатку число мінусів було непарним, то і в кінці залишиться один мінус. Проаналізуємо всі три розв’язки. Перший розв’язок ґрунтувався на незмінності добутків написаних чисел, друге – на незмінності парності їх суми та третє – на незмінності парності числа мінусів. У кожному розв’язку нам вдалося знайти інваріант: добуток написаних чисел, парність суми, парність числа мінусів. Розв’язок наступних завдань також ґрунтується на вдалому підборі інваріанта.

Числа 1, 2, 3, ...., n розташовані в певному порядку. Дозволяється міняти місцями будь-які два числа, що стоять поруч. Доведіть, що якщо виконати непарне число таких операцій, то напевно матимемо відмінне від початкового розташування чисел 1, 2, 3, ..., n.

Розв’язок. Нехай a1, a2, ..., a_n – довільна перестановка з чисел 1, 2, 3, ..., n. Вважатимемо, що числа а₁ і а_j, утворюють в цій перестановці інверсію, якщо i <j, але a_i> a_j , тобто більше з цих чисел передує меншому. Помінявши місцями два сусідні числа в перестановці, ми збільшимо або зменшимо число інверсій на 1. Проробивши ж непарне число таких операцій, ми змінимо парність числа інверсій, а значить, змінимо і перестановку.

У різних пунктах кільцевого автодрому в один і той же час в одному напрямку стартували 25 автомобілів. За правилами гонки автомобілі можуть обганяти один одного, але при цьому заборонено подвійний обгін. Автомобілі фінішували одночасно в тих же пунктах, що і стартували. Доведіть, що під час гонки було парне число обгонів.

Розв’язок. Замалюємо один з автомобілів у жовтий колір, а іншим автомобілям привласнимо номера 1, 2, 3, ..., 24 в тому порядку, в якому вони розташовуються на старті за жовтим автомобілем. У центрі автодрому встановимо світлове табло, на якому після кожного обгону будемо вказувати номери автомобілів в тому порядку, в якому вони слідують за жовтим автомобілем. Тоді обгін, в якому не бере участь жовтий автомобіль, призводить до того, що на світловому табло змінюються місцями два сусідніх числа.
Подивимося, що станеться, якщо який-небудь автомобіль обжене жовтий. Якщо перед цим обгоном числа на табло утворювали перестановку а1, а2, ..., а24, то після обгонів вони утворюють перестановку а2, а3, ..., а24, а1. Зауважимо, що до такої ж перестановки можна прийти, виповнивши послідовність 23 транспозицій: а1, а2, а3, ..., а24 à а2, а1, а3, ..., a24 à а2, а3, а1, ..., а24 à а2 , а3, а1, ..., а24 à ... à а2, а3, ..., а1, а24 à а2, а3, ..., а24, а1
Якщо ж жовтий автомобіль з вершив обгін, то з перестановки а1, а2, ..., а24 отримаємо перестановку а24, а1, а2, а3, ..., а23. Цей перехід також можна замінити двадцятьма трьома транспозиції. Таким чином, будь-який обгін зводиться до непарного числа транспозицій. Якщо б загальне число обгонів було непарним, то непарних виявилося б і загальне число транспозицій.

Графи
Графом на площині називається множина точок площини, деякі з яких з'єднані лініями. Ці точки називаються вершинами графа, а з'єднують їх лінії - ребрами. Число ребер, що виходять з вершини графа, називається ступенем цієї вершини.. Прикладами графа може служити будь-яка карта доріг, електросхеми, креслення багатокутника і т. д. Теорія графів виникла в 1736 р., коли Леонард Ейлер опублікував першу статтю про графах. Починалася вона з розбору широко відомої тепер задачі про Кенігсбергських мостах. Тривалий час вважалося, що теорія графів застосовується головним чином для вирішення логічних завдань, а сама теорія розглядалася як частина геометрії. Однак у ХХ столітті були знайдені широкі застосування теорії графів в економіці, біології, хімії, електроніці, мережевому плануванні, комбінаториці і інших областях науки і техніки. В результаті вона стала бурхливо розвиватися і перетворилася на самостійну розгалужену теорію.

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

Розв’язок. Позначимо число жителів на поверхах відповідно через а1, а2, а3, а4, а5, а число жителів у під'їздах - відповідно через b1, b2, b3, b4. Тоді загальна кількість жителів будинку можна підрахувати двома способами - по поверхах і по під'їздах: a1 + а2 + а3 + а4 + а5 = b1 + b2 + b3 + b4. Якби всі ці 9 чисел були непарними, то сума в лівій частині записаного рівності була б непарної, а сума в правій частині – парному. Отже, це неможливо. Відповідь: не можуть.

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

Доведення. Позначимо число матчів, проведених першої, другої, третьої і т. д. командами, через а1, а2, а3, ..., А15. Припустимо, що всі ці 15 чисел непарні. Підрахуємо загальне число матчів, проведених командами. Воно дорівнює (А1 + а2 + ... + А15) / 2. Але чисельник дробу є число непарне, як сума непарного числа непарних доданків. Тоді загальна кількість матчів є число дробове. Отримали суперечність. Можна, використовуються інваріанти. Уявімо собі 20 ящиків, розкладених в ряд. Переформулюємо завдання наступним чином: чи можна розташувати картки по ящиках так, щоб виконувались дві умови: a) картки з 0 лежать в сусідніх ящиках, картки з 1 - через одну скриньку, ... , Картки з 9 - через дев’ять скриньок; b) у кожному ящику лежить по одній картці? Очевидно, порізно виконати кожну з умов дуже легко. Це й призводить до двох розв’язків . Перший розв’язок. Покладемо в перший ящик 10 карток: Одну - з 0, одну - з 1, ... , Одну - з 9. Потім другу картку з 0 покладемо в другий ящик, другу картку з 1 - у третій ящик, .... другу картку з 9 - в одинадцятий ящик. Умова а) виконується. Ми хочемо спробувати, не порушуючи його, так перекласти картки, щоб умова b) теж виконувалась. Будемо перекладати будь-які дві «однойменні» (з однією і тією ж цифрою) картки через однакове число ящиків. Неважко помітити, що при довільному дозволеному переміщенні відмінність в сумі відбувається на парне число ящиків. Це підказує ідею взяти за інваріант залишок від ділення на 2 суми номерів ящиків, у яких лежать картки.

На столі стоять вверх дном 7 склянок. Дозволяється за один раз перевернути будь-які 4 склянки. Чи можна через кілька кроків поставити всі склянки у нормальний стан?

Розв’язок. Поставимо відповідно склянці, що стоїть нормально, +1, а стоїть догори дном, - 1.Інваріантом тут буде твір чисел, які відповідають усім 7 склянок, оскільки при зміні знака у 4 співмножників твір не змінюється. Але в початковому положенні цей твір дорівнює -1, а значить, стати +1 воно ніколи не зможе.

На дошці написано десять плюсів і п'ятнадцять мінусів. Дозволяється стерти будь-які два знаки і написати замість них плюс, якщо вони однакові, і мінус у протилежному випадку. Який знак залишиться, на дошці після виконання двадцяти чотирьох таких операцій.

Числа 1, 2, 3, ...., n розташовані в певному порядку. Дозволяється міняти місцями будь-які два числа, що стоять поруч. Доведіть, що якщо виконати непарне число таких операцій, то напевно будемо мати відмінне від початкового розташування чисел 1, 2, 3, ..., n.

Розв’язок. Нехай a1, a2, ..., a_n – довільна перестановка з чисел 1, 2, 3, ..., n. Вважатимемо, що числа а1 і аj, утворюють в цій перестановці інверсію, якщо i <j, але ai> aj , тобто більше з цих чисел передує меншому. Помінявши місцями два сусідні числа в перестановці, ми збільшимо або зменшимо число інверсій на 1. Проробивши ж непарне число таких операцій, ми змінимо парність числа інверсій, а значить, змінимо і перестановку.

У різних пунктах кільцевого автодрому в один і той же час в одному напрямку стартували 25 автомобілів. За правилами гонки автомобілі можуть обганяти один одного, але при цьому заборонено подвійний обгін. Автомобілі фінішували одночасно в тих же пунктах, що і стартували. Доведіть, що під час гонки було парне число обгонів.

Подивимося, що станеться, якщо який-небудь автомобіль обжене жовтий. Якщо перед цим обгоном числа на табло утворювали перестановку а1, а2, ..., а24, то після обгонів вони утворюють перестановку а2, а3, ..., а24, а1. Зауважимо, що до такої ж перестановки можна прийти, виповнивши послідовність 23 транспозицій: а1, а2, а3, ..., а24 à а2, а1, а3, ..., А24 à а2, а3, а1, ..., а24 à а2 , а3, а1, ..., а24 à ... à а2, а3, ..., а1, а24 à а2, а3, ..., а24, а1

Якщо ж жовтий автомобіль з вершив обгін, то з перестановки а1, а2, ..., а24 отримаємо перестановку а24, а1, а2, а3, ..., а23. Цей перехід також можна замінити двадцятьма трьома транспозиції. Таким чином, будь-який обгін зводиться до непарного числа транспозицій. Якщо б загальне число обгонів було непарним, то непарних виявилося б і загальне число транспозицій.

Використані джерела:

1. Вейль Г., Классические группы, их инварианты и представления, пер. с англ., М., 1947.

2. И.В. Аржанцев: Алгебраические кривые и 14-я проблема Гильберта. Вестник МГУ , Серия 1, 4 (1994), 18-23; English transl.: Moscow Univ. Math. Bulletin 49:4 (1994), 15-19.

3. Болтянский В. Г., Виленкин Н. Я. Симметрия в алгебре, 2-е изд. М.: Наука, 2002.

4. Ибрагимов Н. Х. Азбука группового анализа. М.: Знание, 1989, N 8.

5. Ибрагимов Н. Х. Опыт группового анализа обыкновенных дифференциальных уравнений. М.: Знание, 1991, N 7.

6. http://school16.org/tvorcha-laboratoriya-vchitelya-sivachovoyi-nm.

docx

Завантажити

Зберегти на потім

Додав(-ла)

Глущик Олександр Якович

Пов’язані теми

Математика, 11 клас, Матеріали до уроків

Додано

17 грудня 2019

Переглядів

2082

Оцінка розробки

Відгуки відсутні