додати матеріал

приховати рекламу

Нестандартні завдання з математики

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

Курсова робота з математики
Нестандартні завдання з математики
Студент: Ігнатьєва Ольга Михайлівна
фізико - математичний факультет 4 курс
Науковий керівник: Емельченков Євген Петрович
СГПУ
2001

1. Інваріанти

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

Нерідко зустрічаються завдання, в яких запитується, чи можна в результаті деяких дій отримати той чи інший результат. Основним методом вирішення подібних завдань є знаходження властивості вихідного об'єкта, яке не змінюється після виконання таких дій, - це і є інваріант. Якщо кінцевий об'єкт завдання не володіє знайденим властивістю, то він, очевидно, не може бути отриманий в результаті цих дій з вихідного об'єкта.
Полуінваріант - величина, що змінюється тільки в одну сторону (тобто яка може тільки збільшуватися або тільки зменшуватися). Поняття полуінваріанта часто використовується при доказах зупинки процесів.
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. На кожній клітці шахової дошки 8х8 написали вироб-ведення номера рядка, в якій розташована клітинка, на номер її стовпця. Вибрали 8 кліток, з яких ніякі дві не стоять в одному рядку і ніякі дві не стоять в одному стовпці. Доведіть, що твір чисел, написаних у цих клітинах, постійно, і обчисліть його.
3. Аркуш паперу розірвали на 5 шматків, деякі з цих шматків розірвали на 5 частин, а деякі з цих нових частин розірвали ще на 5 частин і т. д. Чи можна таким шляхом отримати 1994 шматка паперу? А 1997?
Рішення.
При кожному розриванні аркуша або одного шматка паперу на 5 частин загальне число шматків збільшується на 4. Тому число шматків паперу на кожному кроці може мати тільки вид 4k + 1 (k-
натуральне число). Цей вислів і є інваріантом.
Так як 1994 не можна представити у вигляді 4k + 1, то число шматків, рівне 1994, вийти не може, а 1997 = 4k + 1 при k = = 499, отже, 1997 шматків вийти можуть.
4. Є два аркуші картону. Кожен з них розрізали на 4 шматки, деякі з цих шматків розрізали ще на 4 шматки і т. д. Чи можна таким шляхом отримати 50 шматків картону? А 60?
5. Кожне натуральне число від 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 разів.
6. На дошці написані числа 1, 2, 3, ..., 125. Дозволяється стерти будь-які два числа і написати замість них залишок від ділення суми цих чисел на 11. Після 124 таких операцій на дошці залишилося одне число. Яке це число?
7. Перший член послідовності дорівнює 1, а кожен наступний, починаючи з другого, виходить додатком до попереднього члену суми його цифр. Чи може в цій послідовності зустрітися число 765432?
8. Коло розбитий на 6 рівних секторів, у кожному з яких коштує по одній шашці. Одним ходом дозволяється будь-які дві шашки пересунути в сусідні сектори, причому так, щоб одна шашка рухалася за годинниковою стрілкою, а інша - проти. Чи можна за кілька таких ходів зібрати всі шашки в одному секторі.
9. Коло розбитий на 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. Тому зробити рівними всі шість чисел не можна.
Відповідь: не можна.
10. У вершинах опуклого шестикутника записані числа 8, 3, 12, 1, 10, 6 (у зазначеному порядку). За один хід дозволяється к4 будь-яким двом числах в сусідніх вершинах додати одне і те ж число. Чи можна за кілька таких ходів отримати в послідовному порядку шістку чисел 5, 2, 14, 6, 13, 4?
11. Дано чотири числа 3, 4, 5, 6. За один хід дозволяється написати чотири нові числа, замінивши кожне з вихідних чисел середнім арифметичним трьох інших. Доведіть, що за кілька таких ходів можна отримати набір 1, 3, 5, 8.
12. У кожній клітці дошки 5 х 5 сидить жук. У деякий момент всі жуки переповзають на сусідні (по горизонталі або вертикалі) клітини. Доведіть, що після цього залишиться принаймні одна порожня клітка.
13. На диво-яблуні ростуть банани та ананаси. За один раз дозволяється зірвати з неї два плоди. Якщо зірвати два банани або два ананаса, то виросте ще один ананас, а якщо зірвати один банан і один ананас, то виросте один банан. У результаті залишився один плід. Який це плід, якщо відомо, скільки бананів і ананасів росло спочатку?
Рішення.
Парність числа бананів не змінюється, якщо число бананів було парних, то залишився плід ананас, якщо число бананів було непарним, то - банан.
14. На пряме стоять дві фішки: зліва червона, праворуч синя. Дозволяється проводити будь-яку з двох операцій: вставку двох фішок одного кольору поспіль (між фішками або з краю) і видалення пари сусідніх одноколірних фішок (між якими немає інших фішок). Чи можна за допомогою таких операцій залишити на прямий рівно дві фішки: зліва синю, а праворуч червону?
Рішення.
Розглянемо число різнокольорових пар (не тільки сусідніх), де ліва фішка червона, і зауважимо, що парність цього показника не змінюється. Але у вихідній ситуації наш показник дорівнює 1, а в бажаної ситуації - нулю. Тому перейти до бажаної ситуації неможливо.
15. На острові Серобуромалін живуть хамелеони: 13 сірих, 15 бурих і 17 малинових. Якщо 2 хамелеона різних кольорів зустрічаються, то вони обидва змінюють свій колір на третій. Чи може статися, що в деякий момент всі хамелеони на острові стануть одного кольору?
Зазначення.
Розгляньте залишки від ділення чисел Б бурих, З сірих і М малинових хамелеонів на 3 та перевірте, що попарні різниці у цих залишків не змінюються.
16. Доведіть, що в грі «15» не можна поміняти місцями фішки «15» і «14», залишивши інші на місці.
Ідея рішення.
Розглянемо «порожнє поле» як окрему фішку. Ми можемо тільки міняти «порожню фішку» з сусідніми. Оскільки порожня фішка повинна потрапити на вихідне поле, число наших операцій має бути парним. Тому ми можемо отримати конфігурації, що відрізняються від початкової тільки парним числом перестановок.
17. На 44 деревах, розташованих по колу, сиділи по веселому Чижу. Час від часу якісь два чижа перелітають на сусіднє дерево - один за годинниковою стрілкою, а інший - проти. Чи можуть все чижі зібратися на одному дереві?
Рішення.
Пронумеруємо дерева по колу з 1-го по 44-е. Сума номерів дерев, на яких сидять чижі або не змінюється, або зменшується на 44, або збільшується на 44. Тим самим, залишок від ділення цієї суми номерів на 44 не змінюється. Спочатку цей залишок дорівнює 22, а якщо все чижі сядуть на одне дерево, то він буде дорівнює нулю. Тому чижі не зможуть зібратися на одному дереві.
18. Чи можна розрізати опуклий 17-кутник на 14 трикутників?
Загальна постановка задачі.
За допомогою інваріантів вирішуються завдання наступного типу: дано безліч М (Елементи його ми будемо називати «позиціями») і правило, за яким дозволяється переходити від однієї позиції до іншої; чи можна з даної позиції а перейти за кілька кроків в іншу дану позицію p? Більш спільне завдання: як. для довільної пари позицій а, p встановити, чи можна з а за кілька кроків перейти в р?
Очевидно, описані ситуації мають наступну властивість: якщо з позиції a можна перейти в позицію р і з p можна перейти в позицію h, то з a можна перейти в h. Це властивість називається транзитивне.
Розглянемо конкретне завдання.
Завдання 1. Коло розділений на n секторів, в яких якось розставлені n фішок. Дозволяється одночасно пересунути будь-які дві фішки: одну - на один сектор за годинниковою стрілкою, іншу - на один сектор в протилежному напрямку. Чи можна з позиції M, в якій в кожному секторі коштує 'по одній фішці, перейти до позиції V, в якій всі фішки зібрані в якому-небудь одному секторі?
У цьому завданню, крім властивості транзитивності, має місце також наступне важливе властивість: якщо з позиції a можна перейти в позицію р, то і з р можна перейти в a. Це властивість називається симетричністю.
Властивість симетричності дотримується не у всіх завданнях розглянутого типу; наприклад, у шахах пішаки назад не ходять. У цій статті ми обмежимося завданнями, для яких умова симетричності виконано.
Домовимося вважати, що з будь-якої позиції a можна «перейти» у неї ж. Це властивість називається рефлексивностью.
Назвемо позиції a і p еквівалентними, якщо за заданими правилами з a можна перейти в p (зважаючи на намічену симетричності це рівнозначно тому, що з p можна перейти в a). Еквівалентність позицій a і p ми будемо позначати так: a ~ p; нееквівалентність - так: a ~ / p.
Оскільки еквівалентність позицій рефлексивна, симетрична і транзитивна, вихідна безліч М розбивається на непорожні непересічні підмножини (рис. 1): М = M1UM2UM3U ... У кожному з підмножин M i, всі позиції еквівалентні: якщо a з М i, і p з M i, то a ~ p. Якщо ж позиції a і p належать різним підмножинами: a з M i p з M j (i відмінно від j ), То a і p не еквівалентні). Підмножини М i ми будемо називати орбітами. Повторимо ще раз: якщо ми знаходимося в позиції a, що належить який-небудь орбіті M i, то ми можемо, переміщаючись по цій орбіті, перебратися з позиції a в будь-яку іншу позицію, що належить орбіті. З іншого боку, зійти з цієї орбіти, тобто перебратися з позиції a на позицію p, що належить будь-який інший орбіті, ми не можемо. Орбіт може бути як кінцеве, так і нескінченне число. Втім, якщо безліч М звичайно, те, зрозуміло, і число орбіт звичайно. Інваріант. Числова функція f, визначена на множині «позицій» M, називається інваріантної функцією, або інваріантом, якщо на еквівалентних позиціях вона приймає однакові значення: якщо a ~ р, то f (а) = f (р). (1)
Завдання 1 (продовження). Нехай п = 2 т. Розфарбував сектори через один на сірий і білий колір. Тоді при кожному переміщенні число фішок у білих секторах або не змінюється (рис. 2), або збільшується на 2 (рис. 3), або зменшується на 2 (рис. 4). Для довільної розстановки a фішок по секторах позначимо через б (а) число фішок у білих секторах. Розглянемо тепер таку функцію g.
0, якщо б (a) парне,
g (a) =
1, якщо б (a) непарній.
Зі сказаного вище випливає, що ця функція g (парність числа фішок у білих секторах) є інваріантом. Оскільки п = 2 т, для кінцевої позиції v маємо g (v) = 0. Якщо т = 2 k + 1, то n / 2 непарній. Значить, для початкової позиції w маємо g (w) = 1. З того, що g (w) відмінно від g (v) випливає, що позиції w і v не еквівалентні. Таким чином, в цьому випадку
(П = 2 т, т = 2 k + 1) з позиції w не можна перейти в позицію v. Ну, а якщо т = 2 k? Тоді n / 2 парне і g (w) = g (v) = 0. У цьому випадку інваріант g не дає можливості встановити еквівалентні позиції w і v чи ні.
Справа в тому, що якщо f - Інваріант, то з f (a.) = F (p), взагалі кажучи, нічого не випливає. Якщо f (a) відмінно від f (p) то позиції а й p не еквівалентні (це випливає з (1)). Якщо ж f (a) = f (p), то позиції чи р можуть бути як еквівалентними, так і не еквівалентними: інваріанта не забороняється на різних орбітах приймати однакові значення. (Наприклад, постійна функція, тобто функція, яка на всіх елементах з М приймає одне і те ж значення, теж інваріантна.)
Як же бути? Спробуйте для якого-небудь п виду 4 k перейти від позиції w, до позиції v ... Чомусь не вдається. Спробуємо Знайти інший, більш тонкий інваріант.
Занумеруем сектори (скажімо, за годинниковою стрілкою) від 1 до n. Для довільної розстановки а. Фішок по секторах позначимо через x k (А) кількість фішок в k-му секторі при розстановці a.
Розглянемо тепер таку функцію q:
q (a) = 1 x 1 (a) + 2 x 2 (a) +3 x 3 (a) +
+ ... + N x n (a). (2)
Чи є функція q інваріантом?
Довільне допустиме переміщення (рис. 5) зачіпає 4 доданків суми (2):
... + I x i (a) + (i + 1) x i + 1 (a) + ... + (j - 1) x j - 1 (a) + j x j (a) + ...   (3)

При переміщенні, зображеному

... + I [X i (a) - 1] + (i + 1) [x i +1 (a) + 1] +
+ ... + (J - 1) [x j -1 (a) + 1] + j [X j (A) - 1] + ...
Легко перевіряється, що обидві суми рівні. Отже, q - інваріант! Ні,
ми забули, що n-й сектор межує з першим. Значить, є ще 3 можливості. Підрахунок, аналогічний щойно зробленому, показує, що у випадку, зображеному на рис. 6, q (a) зменшиться на п, а в випадку збільшиться на п. У третьому випадку q (а), звичайно, не зміниться. Отже, за одне переміщення значення функції q може змінитися, але тільки на п. Отже, функція r, значення якої на розстановці a дорівнює залишку. від ділення числа q (a) на п, є інваріант.
Для позиції v (якщо все п фішок зібрані в 1-му секторі)
x 1 (v) = x 2 (v) = ... = x l -1 (v) = x l + 1 (v) = ... = x n (v) = 0,
x l (v) = n.
Значить, q (v) = l n і r (v) = 0 (які б не були п і l ). З іншого боку,
x 1 (w) = x 2 (w) = ... = x n (w) = 1. Значить, q (w) = 1 + 2 + 3 + ... + n = (n (n + 1)) / 2
Якщо n = 2 m, то q (w) = nm + m і   r (w) = т = / 0. Отже, при парному п отримуємо r (w) = / r (v). Отже, при парному п позиції w і v не еквівалентні.
Якщо ж п = 2т + 1, то q (w) = n (m + 1) і r (w) = 0. Таким чином, при непарному п ми знову маємо: r (і) - r (v). Виходить, що при непарному п питання про еквівалентність позицій w і v знову залишається відкритим.
Універсальний інваріант
Назвемо інваріант f універсальним, якщо на нееквівалентних позиціях він приймає різні значення: якщо a ~ / P, то f (a) ¹ f (p). Таким чином, для універсального інваріанта f: якщо f (a) = f (Р), то a ~ р.
Універсальний інваріант на кожній орбіті приймає своє значення. Оскільки для універсального інваріанта a ~ p Û f (a) = f (p), універсальний інваріант для будь-якої пари позицій дозволяє встановити, еквівалентні ояі чи ні.
Як перевірити, що деякий інваріант f універсальний? Загального методу не існує. Іноді може допомогти наступна проста
Теорема. Якщо а) існують такі l позицій б1, б2, ..., б l, що кожна позиція a з М еквівалентна одній з них і b) інваріант f приймає, принаймні, l різних-значень, то f-універсальний інваріант і позиції б i, б j (i = / j) no парно не еквівалентні.
З а) випливає, що існує не більше l орбіт. З b) випливає, що існує не менш l орбіт. Отже, існує рівно l орбіт. Знову з b) випливає тепер, що інваріант f приймає рівно l значень і, значить, f універсальний. Нарешті, з а) випливає, що позиції б1, б2, ..., б l належать різних орбітах і, таким чином, попарно не еквівалентні.
Завдання 1 (закінчення). Доведемо, що інваріант r універсальний. Позначимо через б i, таку розстановку фішок: одна фішка - в i-му секторі, всі інші - в п-му секторі. Під б n ми будемо, зрозуміло, розуміти розстановку, при якій всі n фішок - в n-му секторі.
Легко збагнути, що будь-яка розстановка еквівалентна одній з позицій б1, б2, ... , Б n. Справді, нехай a - довільна розстановка фішок. Спробуємо зібрати всі п фішок в n-му секторі. Для цього будемо пересувати перший фішку, поки не заженемо її в п-ий сектор; одночасно, у відповідності з правилами, ми будемо переміщувати другу фішку в протилежну сторону. Потім заженемо в n-й сектор другий фішку, рухаючи в протилежну сторону третій фішку, і так далі - аж до (п-1)-ї фішки. Коли ми заженемо п - 1 фішок в n-й сектор, п-а фішка буде в якомусь i-му секторі (i = 1, 2, ..., п). Це й означає, що a ~ бi.
Порахуємо ri). При i не рівному п:
x 1 (бi) == x 2 (бi) = ... = x i - 1 (бi) = x i +1 (бi) =...= x n-1 (бi) = 0,
x i (бi) = 1,
x n (бi) -= n - 1.
Отже, q (бi) -= i l + п (п-1) і r (Бi) = i. Крім того, qn) = nn і rn) = 0. Отже, інваріант r приймає принаймні п значень.
По теоремі інваріант r універсальний і позиції б1, б2, ... , Б n попарно не еквівалентні.
Оскільки r - універсальний інваріант, a ~ р Û r (а) = r (р).
У попередньому параграфі ми порахували, що r (w) = r (v) Û n-непарне. Отже, w ~ v, тоді і тільки тоді, коли п - непарне. Завдання, нарешті, вирішена повністю.
Завдання
1.19. Доведіть, не використовуючи поняття інваріанту, що при непарному п позиції w і v еквіваленти.
1.20. Перевірте, що будь-яка функція від інваріанта знову є інваріантом: якщо f - Інваріант і g - Довільна числова функція, то і функція h : H (a) = g (f (a)) (4) теж інваріантна.
1.21.Докажіте, що будь-який інваріант можна представити у вигляді функції від будь-якого універсального інваріанта: якщо h - інваріант, a f - Універсальний інваріант, то існує така числова функція g, що виконується (4).
1.22.Определім через універсальний інваріант r з завдання 1 два нових інваріанта: f (a) = [r (a)] 2; g (a) = [r (а) - 2] 2. Доведіть, що інваріант f універсальний, а інваріант g не універсальний.
1.23. Нехай f - універсальний інваріант. Яким умовам має задовольняти числова функція g, щоб інваріант h, визначений рівністю (4), був універсальним?
Завдання 2. Дано 20 карток. На двох картках написана цифра 0, на двох - цифра 1, ... , На двох останніх - цифра 9. Чи можна розташувати ці картки в ряд так, щоб картки з 0 лежали поруч, між картками з 1 лежала рівно одна картка, ... , Між картками з 9 лежало рівно 9 карток?
Це завдання можна вирішити без всяких інваріантів. Однак для нас вона цікава тим, що у неї є два принципово різних рішення, що використовують інваріанти.
Уявімо собі 20 ящиків, розташованих в ряд. Переформулюємо тепер наше завдання наступним чином: чи можна розташувати картки по ящиках так, щоб виконувалися дві умови:
a) картки з 0 лежать у сусідніх ящиках, картки з 1 - через одну скриньку, ... , Картки з 9 - через дев'ять ящиків;
b) у кожному ящику лежить по одній картці?
Очевидно, порізно виконати кожне з умов дуже легко. Це і призводить до двох рішень.
Перше рішення. Покладемо в перший ящик 10 карток:
Одну - з 0, одну - з 1, ... , Одну - з 9. Потім другу картку з 0 покладемо в другій ящик, другу картку з 1 - у третій ящик, .... другу картку з 9 - у одинадцятий скриньку. Умова а) виконується. Ми хочемо спробувати, не порушуючи його, так перекласти картки, щоб умова b) теж виконувалося. Дозволимо перекладати будь-які дві «однойменні» (з однією і тією ж цифрою) картки через однакове число ящиків. Неважко помітити, що при довільному дозволеному переміщенні зрушення в сумі відбувається на парне число ящиків. Це підказує ідею взяти як інваріанта залишок від ділення на 2 суми номерів ящиків, у яких лежать картки.
Завдання
1.24. Закінчити намічене рішення.
Друге рішення. Покладемо в перший і другий ящики картки з 0, в третій і четвертий - картки з 1, ... , Дев'ятнадцятий і двадцятий - картки з 9. На цей раз виконана умова b). Дозволимо міняти місцями будь-які дві картки. При такому переміщенні відстань між вісьмома парами «однойменних» карток не змінюється, між двома - міняється; таким чином, сума всіх цих відстаней ...
Повна система інваріантів
Іноді замість універсального інваріанта простіше знайти і використовувати повну систему інваріантів. Система інваріантів <f 1, f 2, f 3> називається повною, якщо рівності,
f 1 (a) = f 1 (p),
f 2 (a) = f 2 (p), (5)
f k (a) = f k (p).
мають місце одночасно тоді і тільки тоді, коли позиції a і p еквівалентні.
У чому суть цього визначення? Якщо позиції a і p еквівалентні, то, оскільки f 1, f 2, ..., f k - інваріанти, кожне з рівностей системи (5) все одно виконується. «У цей бік» повнота ще ні до чого. Якби інваріанти f 1, f 2, ..., f k були універсальними, то еквівалентність позицій бенкет випливала б з будь-якого рівності системи (5). Нам не дано їх універсальність, але зате потрібно, щоб одночасне виконання рівностей системи (5) тягло еквівалентність позицій a і p. Саме в цьому суть поняття повноти. Таким чином, хоча деякі з інваріантів f 1, f 2, ..., f k можуть на нееквівалентних позиціях a і p приймати однакове значення, значення набору
< f 1, f 2, ..., f k> на них різні.
Повна система інваріантів - це узагальнення поняття універсального інваріанта: якщо f - універсальний інваріант, то система <f>, що складається з одного інваріанта, звичайно, повна.
Завдання 3. У таблиці 2х2 записуються цілі числа. Дозволяється, по-перше, в будь-якому стовпці одночасно: до одного числа додати 2, з іншого - відняти 2 і, по-друге, в будь-якому рядку одночасно: до одного числа додати 3, з іншого - відняти 3. Які таблиці еквівалентні?

Розглянемо три функції: для будь-якої таблиці

a = ab
cd
позначимо через g (a) суму а + b + с + d, через q (a) - залишок від ділення числа а + b на 2 і через r (а) - залишок від ділення числа а + з на 3. Функції g, q, r є інваріантами. Не дуже важко довести, що довільна таблиця a еквівалентна таблиці
0 q (a)
r (a) g (a)-q (a)-r (a)
Отже, з рівностей
g (a) = g (p),
q (a) = q (p),
r (a) = r (p).
випливає що таблиці a і р еквівалентні одній і тій же таблиці і, значить, еквівалентні між собою. І навпаки: еквівалентність таблиць a і р тягне рівності (6), оскільки g, q і r - інваріанти. Таким чином, "g, q, r> - повна система.
Завдання.
1.26. Вирішіть задачу для таблиць n x n, в яких вирішуються ті ж перетворення, що і в задачі 3. Природно очікувати повну систему з 2n--1 інваріантів.
1.27. Якщо f 1, f 2, fk - Інваріанти і g - числова функція від k аргументів, то функція h: h (a) = g (f 1 (a), f 2 (a ),..., fk (a)) (7) є інваріантом (ср . з вправою 2). Перевірте.
1.28. Якщо h - інваріант, a <f 1, f 2, ..., f k> - повна система інваріантів, то існує така числова функція g від k аргументів, що виконується (7) (пор. з вправою 3). Доведіть.
1.29. Безліч М - безліч точок числової площини, то є безліч пар <х, у> дійсних чисел. Єдиний допустимий перехід: <x, y> à <y, x>. Нехай
f 1 (x, y) = xy,
f 2 (x, y) = x + y.
Довести, що <f 1, f 2> - повна система інваріантів.
1.30. Безліч М - безліч точок простору або безліч трійок <x, y, z> дійсних чисел. Дозволені переходи
<X, y, z> à <y, x, z> і <x, y, z> à <x, z, y>. Нехай
f 1 (x, y, z) = xyz,
f 2 (x, y, z) = ху + у z + z х,
f 3 (x, y, z) = х + у + z.
Довести, що <f 1, f 2, f 3> - повна система інваріантів.
1.31. Безліч М складається з різноманітних наборів (або кортежів) 1, x 2, x 3, ..., x n> дійсних чисел (n фіксовано). Дозволяється міняти місцями будь-які дві сусідні числа. Знайти повну систему інваріантів.
На відміну від завдань 1 - 3, які були просто завданнями олімпіадного типу, вправи 11-13 грають важливу роль в алгебрі многочленів. Інваріанти в них цікаві не для вирішення питання про еквівалентність (який ясний і без них), а самі по собі - як корисні функції.
1.32. Дано розетка з п дірками і електронна лампа з n штирями. Дірки занумеровані від 1 до n (рис. 9). Чи можна занумеровані штирі від 1 до n так, щоб при будь-якому включення в розетку один з штирів потрапляв в дірку зі своїм номером?
1.33. Багато хто знає «гру в 15»: в коробочці 4x4 лежать 15 шашок з номерами від 1 до 15; дозволяється за один хід пересунути в порожню клітину одну з шашок, сусідніх з нею. Чи можна перетворити положення a в положення p (рис. 10)? Знайдіть для цієї гри універсальний інваріант.
1
2
3
4
1
2
3
4
5
6
7
8
5
6
7
8
9
10
11
12
9
10
11
12
13
14
15

13
15
14
                 а p
1.34. На картатій дошці 11x11 відзначено 22 клітинки так, що на кожній вертикалі і на кожній горизонталі зазначено рівно 2 клітини. Два розташування зазначених клітин еквівалентні, якщо, змінюючи будь-яке число раз вертикалі між собою і горизонталі між собою, ми з одного розташування можемо отримати інше. Скільки існує нееквівалентний розташуванні зазначених клітин?
1.35. Іспанський король вирішив переважити по-своєму портрети своїх попередників у круглій вежі замку. Однак він хоче, щоб за один раз міняли місцями тільки два портрети, що висять поруч, причому це не повинні бути портрети королів, один з яких царював відразу після іншого. Крім того, йому важливо лише взаємне розташування портретів, і два розташування, відмінні поворотом кола, він вважає однаковими. Довести, що, як би спочатку ні висіли портрети, король може за цими правилами домогтися будь-якого нового їх розташування.
1.36. Всі цілі числа від 1 до 2 n виписані в рядок. Потім до кожного числа додали номер того місця, на якому воно стоїть. Довести, що серед отриманих сум знайдуться хоча б дві, що дають при діленні на 2 n однаковий залишок.
1.37. Повернемося до задачі 1 з фішками в колі і вирішимо тепер рухати дві фішки як у різні сторони, так і в одну сторону. Знайти для цього завдання універсальний інваріант.
1.38. У таблиці 3x3 розставлені числа +1 і -1. Дозволяється змінювати знак одночасно у всіх елементів рядка або стовпця. Доведіть, що:
a) число орбіт дорівнює 16;
b) кожна орбіта містить рівно 32 елемента;
c) добуток всіх чисел будь-якого квадрата 2x2 в таблиці є інваріантом;
d) твори чисел у чотирьох квадратах, вказаних на малюнку 11, утворюють повну систему інваріантів.
Вирішувати ці завдання можна в будь-якому порядку; ясно, що одні допомагають іншим.
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
1.39. Вектор <а, b>, де a, b-цілі числа, дозволяється замінювати одним із векторів <а + b, b>, <a - b, b>, <b, a>. Знайти універсальний інваріант.
1.40. Пару векторів <а, b>, <с, d>, де а, b, с, d - цілі числа, дозволяється замінювати на одну з пар <а + b, b>, <c + d, d>; <a - b, b>, <c - d, d>; <b, a>, <d, c>. Знайти повну систему інваріантів.
2.Четность плюс інваріант
2.1. На дошці написані натуральні числа 1, 2, 3, ..., 100. Дозволяється стерти будь-які два числа і записати модуль їх різниці, після чого кількість написаних чисел зменшується на 1. Чи може після 99 таких операцій залишитися записаним на дошці число 1?
Рішення.
Підрахуємо загальну суму початкових 100 чисел:
1 + 2 + 3 + ... + 100 = 5050.
Ця сума виявилася парному. Переходячи до наступного набору чисел, ми фактично в цій сумі замінювали суму двох чисел на їх різниця. Але сума і різниця двох цілих чисел мають однакову парність, тому загальна сума записаних чисел залишиться парному. Отже, ця сума дорівнює 1 бути не може.
П о в е т: не може.
2.2. На дошці написані 8 плюсів і 11 мінусів. Дозволяється стерти будь-які два знаки і написати замість них плюс, якщо вони однакові, і мінус якщо вони різні. Який знак залишиться на дошці після 18 таких операцій?
2.3. На головній діагоналі шашковій дошки 10 на 10 коштують 10 шашок, всі в різних клітинах. За один хід дозволяється вибрати будь-яку пару шашок і пересунути кожну з них на одну клітку вниз. Чи можна за кілька таких ходів поставити всі шашки на нижню горизонталь?
2.4. На столі стоять вверх дном 7 склянок. Дозволяється за один раз перевернути будь-які 4 склянки. Чи можна через кілька кроків поставити всі склянки в нормальне положення?
Рішення.
Поставимо у відповідності склянці, що стоїть нормально, +1, а що стоїть догори дном, - 1. Інваріантом тут буде твір чисел, які відповідають усім 7 склянках, тому що при зміні знаку у 4 співмножників добуток не змінюється. Але в початковому положенні це добуток дорівнює -1, а значить, стати +1 воно ніколи не зможе.
2.5. На столі коштують 7 перевернутих склянок. Дозволяється одночасно перевертати будь-які дві склянки. Чи можна домогтися того, щоб всі склянки стояли правильно?
2.6. На столі стоять вверх дном 9 склянок. Дозволяється за один раз перевернути будь-які 4 склянки. Чи можна за кілька таких ходів поставити всі склянки в нормальне положення?
2.7. Три коника грають в чехарду: якщо коник з точки А стрибає через коника, що знаходиться в точці В, то він опиниться в точці С, симетричної точці А відносно точки В. У вихідному положенні коники займають три вершини квадрата. Чи можуть вони, граючи в чехарду, потрапити в четверту його вершину?
Рішення.
Введемо на площині систему координат так, щоб три вершини квадрата, в яких знаходяться коники, мали координати (0; 0),
(0; 1) і (1; 0). При зазначених стрибках кожна з координат коників або залишається незмінною, або змінюється в ту чи іншу сторону на парне число (рис 12) х

Так як у початковому положенні

щонайменше одна з координат кожної з трьох точок
парна, то вона при стрибках залишиться парному: парність хо
тя б однієї з двох кожній з точок є інваріант.
Тому потрапити в М один з коників
не може Відповідь: не може.
2.8. Є 30 карток, кожна з яких пофарбована з одного боку в червоний, а з іншого - в синій колір. Картки розклали поспіль у вигляді смуги так, що у 8 карток зверху виявився синій колір. За один дозволяється перевернути будь-які 17 карток. Чи можна за кілька ходів домогтися того, щоб смуга стала повністю: а) червоною; б) синій?
Завдання 1: На дошці написано десять плюсів і п'ятнадцять мінусів. Дозволяється стерти будь-які два знаки і написати замість них плюс, якщо вони однакові, і мінус у противному випадку. Який знак залишиться, на дошці після виконання двадцяти чотирьох таких операцій.
Рішення.
Замінимо кожний плюс числом 1, а кожен мінус числом -1. Дозволена операція описується тоді так: стираються будь-які два числа і записується їх твір. Тому твір всіх написаних на дошці чисел залишається незмінним. Так як спочатку це твір дорівнювало -1, то і в кінці залишиться число -1, то є знак мінус.
Це міркування можна було провести інакше. Замінимо всі плюси нулями, а мінуси-одиницями, і зауважимо, що сума двох стираних чисел має ту ж парність, що і число, що записується замість них. Так як
спочатку сума всіх чисел була непарної (вона дорівнювала 15), то й останнє, на дошці число буде непарних, тобто одиницею, і, значить, на дошці залишиться мінус.
Нарешті, третє рішення задачі можна отримати, зауваживши, що в результаті кожної операції число мінусів або не змінюється, або зменшується на два. Оскільки спочатку число мінусів було непарним, то і в кінці залишиться один мінус.
Проаналізуємо всі три рішення.
Перше рішення грунтувалося на незмінності твори написаних чисел, друге-на незмінності парності їх суми та третє - на незмінності парності числа мінусів. У кожному рішенні нам вдалося знайти інваріант: твір написаних чисел, парність суми, парність числа мінусів. Рішення наступних завдань також грунтується на вдалому підборі інваріанту.
2.9. На дошці написано кілька плюсів і мінусів. Дозволяється стерти будь-які два знаки і написати замість них плюс, якщо вони різні, і мінус у противному випадку. Доведіть, що останній залишився на дошці знак не залежить від порядку, в якому проводилися стирання.
2.10. У таблиці 4х4 знаки «+» і «-» розставлені так, як показано на малюнку 13. Дозволяється змінити знак на протилежний одночасно у всіх клітинах, розташованих в одному рядку, в одному стовпці або вздовж прямої, паралельної який-небудь з діагоналей (зокрема, в будь-якій кутовий клітці). Чи можна за допомогою цих операцій отримати таблицю, що не містить жодного мінуса?
Рішення.
Замінимо плюси і мінуси числами 1 і -1. В якості інваріанта можна взяти твір чисел, що перебувають у клітках, які заштриховані на малюнку 14, оскільки воно внаслідок
дозволеної операції весь час зберігає первинне значення, рівне -1. Але, значить, серед заштрихованих чисел завжди буде залишатися -1, отже, отримати таблицю, що не містить жодного мінуса, не можна.
2.11. Вирішіть задачу 2 для таблиць, зображених на малюнках 15 - 17.
2.12. На дошці написано кілька нулів, одиниць і двійок. Дозволяється стерти дві нерівні цифри і замість них написати одну цифру, відмінну від стертих (2 замість 0 і 1, 1 замість 0 і 2, 0 замість -1 і 2). Доведіть, що якщо в результаті декількох таких операцій на дошці залишиться одна-єдина цифра, то вона не залежить від порядку, в якому проводилися стирання.
Рішення.
Позначимо через х0, х1, х2 число нулів, одиниць і двійок відповідно. Виконавши один раз дозволену операцію, ми змінимо кожне з цих чисел на 1 і, отже, змінимо парність всіх трьох чисел. Коли на дошці залишається одна цифра, два з чисел х0, x1, х2 стають рівними нулю, а. Третє - одиниці. Значить, з самого початку два з цих чисел мають одну парність, а третє-другу. Тому незалежно від того, в якому порядку проводяться стирання, в кінці одиниці може дорівнювати лише одне з чисел х0, х1, x .2, яке з самого початку мало не ту парність, що два інших.
З наведеного рішення видно, що якщо числа х0, х1, х2 мають одну і ту ж парність, то ми не зможемо добитися, щоб на дошці залишилася одна-єдина цифра. Доведіть, що якщо серед чисел х0, х1 х2 є як парні, так і непарні, і, крім того, хоча б два з них відмінні від нуля, то існує такий порядок стирок, що в результаті на дошці залишиться "одна цифра.
Змінимо умову задачі 3: зажадаємо,. Щоб одні і ті ж дві нерівні цифри стиралися два рази, а замість них записувалася одна цифра, відмінна від стертих. Припустимо, що знову після деякого числа операції на дошці залишилася одна-єдина цифра. Чи можна заздалегідь, за кількістю нулів, одиниць і двійок, передбачити, яка це цифра?
Міркування з парністю тут не допомагає, бо в результаті виконання кожної операції одне з чисел х0, х1, x 2 змінює свою парність, а два інших зберігають парність, так що числа, які мали різну парність, можуть тепер отримати одну і ту ж парність. Однак можна помітити, що залишки від ділення чисел х0, х1, х2 на 3 змінюються щоразу таким чином, що рівні рештки залишаються рівними, а нерівні залишаються нерівними. Подальші міркування повторюють рішення задачі 3.
2.13. У кожній клітці таблиці 8х8 написано деяке ціле число. Дозволяється вибирати в таблиці будь-який квадрат розмірами 3х3 або 4х4 і збільшувати на одиницю всі, хто стоїть в клітинах обраного квадрата числа. Чи завжди можна за допомогою таких операцій перетворити вихідну таблицю в таблицю, у якій вага числа діляться на З?
Рішення.
Ні, не завжди. Знайдемо суму чисел, написаних у заштрихованих на малюнку 6 клітинах. Оскільки будь-який квадрат розмірами 4х4 містить 12 заштрихованих клітин, а квадрат розмірами 3х3-6 або 9 таких клітин, то в результаті описаної операції залишок від ділення на 3 цієї суми (чисел, що стоять в заштрихованих клітинах) не буде змінюватися. Тому, якщо з самого початку знайдена сума не ділиться на 3, то серед заштрихованих клітин весь час будуть зберігатися клітини, в яких написані числа не кратні трьом.
2.14. З будь-якої чи таблиці можна в умовах задачі 4 отримати таблицю, що не містить парних чисел?
2.15. Числа I, 2, 3, ...., n розташовані в певному порядку. Дозволяється міняти місцями будь-які два поруч стоять числа. Доведіть, що якщо виконати непарне число таких операцій, то напевно вийде відмінний від початкового розташування чисел 1, 2, 3, ..., n.
Рішення.
Нехай a 1, a 2, ..., an - довільна перестановка з чисел 1, 2, 3, ..., п. Будемо говорити, що числа а i, і а j, утворюють в цій перестановці інверсію, якщо i <j, але ai> aj, тобто більше з цих чисел передує меншому. Помінявши місцями два сусідніх числа в перестановці, ми збільшимо або зменшимо кількість інверсій на 1. Проробивши ж непарне число таких операцій, ми змінимо парність числа інверсій, а значить, змінимо і перестановку.
2.16. Доведіть, що затвердження завдання 2.15 залишиться справедливим, якщо дозволити міняти місцями будь-які два числа в перестановці.
Зазначення.
Доведіть, що будь-які два числа можна поміняти місцями, виконавши непарне число раз операцію, описану в задачі 2.12.
Перехід від однієї перестановки чисел 1, 2, 3, .... п до іншої перестановці цих чисел, при якому будь-які два числа міняються місцями, а решта залишається на місці, називається транспозицією. Результат завдання 2.16 можна сформулювати так: виконавши непарне число транспозицій, ми змінимо перестановку
2.17. У різних пунктах кільцевого автодрому в один і той же час в одному напрямку стартували 25 автомобілів. За правилами гонки автомобілі можуть обганяти один одного, але при цьому заборонено подвійний обгін. Автомобілі фінішували одночасно в тих же пунктах, що і стартували. Доведіть, що під час гонки було парне число обгонів.
Рішення.
Забарвимо один з автомобілів у жовтий колір, а іншим автомобілям привласнимо номери 1, 2, 3, ..., 24 в тому порядку, в якому вони розташовуються на старті за жовтим автомобілем. У центрі автодрому встановимо світлове табло, на якому після кожного обгону будемо вказувати номери автомобілів в тому порядку, в якому вони слідують за жовтим автомобілем. Тоді обгін, в якому не бере участь жовтий автомобіль, призводить до того, що на світловому табло міняються місцями два сусідніх числа.
Подивимося, що станеться, якщо який-небудь автомобіль обжене жовтий. Якщо перед цим обгоном числа на табло утворювали перестановку а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. Цей перехід також можна замінити двадцятьма трьома транспозиція.
Таким чином, будь-який обгін зводиться до непарному числу транспозицій. Якщо б загальне число обгонів було непарним, то непарних виявилося б і загальне число транспозицій. Залишається скористатися результатом завдання 2.16.
3. Графи
Графом на площині називається скінченна множина точок площини, деякі з яких з'єднані лініями. Ці точки називаються вершинами графа, а що з'єднують їх лінії - ребрами. Число ребер, що виходять з вершини графа, називається ступенем цієї вершини.
З графами ми зустрічаємося частіше, ніж це, можливо, здається на перший погляд. Прикладами графа може служити будь-яка карта доріг, електросхема, креслення багатокутника і т. д.
Теорія графів виникла в 1736 р., коли Леонард Ейлер опублікував першу статтю про графах. Починалася вона з розбору широко відомої тепер задачі про кенігсберзькими мостах. Довгий час вважалося, що теорія графів застосовується головним чином для вирішення логічних завдань, а сама теорія розглядалася як частина геометрії. Однак у ХХ столітті були знайдені широкі застосування теорії графів в економіці, біології, хімії, електроніці, мережевому плануванні, комбінаториці і інших областях науки і техніки. У результаті вона стала бурхливо розвиватися і перетворилася на самостійну розгалужену теорію.
Завдання на відповідність між множинами.
3.1. У п'яти корзинах А, Б, В, Г і Д лежать яблука п'яти різних сортів. У кожній з кошиків А і Б знаходяться яблука 3-го і 4-го сорту, у кошику В - 2-го і 3-го, у кошику Г - 4-го і 5-го, у кошику Д - 1-го і 5-го. Занумеруйте кошика так, щоб у кошику № 1 були яблука 1-го сорту (принаймні одна), в кошику № 2 - яблука 2-го сорту і т. Д
Рішення.
Зобразимо дві множини безліч кошиків і безліч їх номерів. У кожному з цих множин по п'ять елементів позначимо їх точками
Встановимо відповідність між цими двома множинами так, щоб умови завдання виконувалися. Будемо відповідні елементи двох множин з'єднувати суцільними лініями, а не відповідні - пунктирними або зовсім не з'єднувати. Так як яблука першого сорту лежать тільки в кошику Д, то саме цьому кошику і потрібно дати номер 1; проведемо суцільну лінію між точками Д і 1. Далі номер 2 можна привласнити тільки кошику В, а після цього номер 5 - лише кошику Г. Нарешті, номери 3 і 4 дамо кошиках А і Б (у будь-якому порядку).
Відповідь: кошики розташувалися, починаючи з № 1, у послідовному порядку Д, В, А, Б, Г або в порядку Д, В, Б, А, Г.
3.2. Петро, ​​Геннадій, Олексій і Володимир займаються в одній дитячій спортивній школі в різних секціях: гімнастики, легкої атлетики, волейболу та баскетболу. Петро, ​​Олексій і волейболіст навчаються в одному класі. Петро і Геннадій на тренування ходять пішки разом, а гімнаст їздить на автобусі. Легкоатлет не знайомий ні з волейболістів, ні з баскетболістом. Хто в якій секції займається?
3.3. Футбольні команди п'яти шкіл міста беруть участь у розіграші кубка. У фінал кубка виходять дві команди. До змагань п'ять уболівальників висловили прогнози, що у фінал вийдуть команди:
1) Б і Г, 2) У і Д, 3) Б і В, 4) А і Г, 5) Г і Д.
Один прогноз виявився повністю невірним, в решті була правильно названа тільки одна з команд-фіналісток. Які команди вийшли у фінал?
3.4. Три товариші - Володимир, Ігор і Сергій - закінчили один і той же педагогічний інститут і викладають математику, фізику і літературу в школах Тули, Рязані і Ярославля. Володимир працює не в Рязані, Ігор - не в Тулі. Рязанець викладає не фізик, Ігор - не математику, туляк викладає літературу. Який предмет і в якому місті викладає кожен з них?
3.5. Серед офіцерів А, Б, В і Г - майор, капітан і два лейтенанти. А і один з лейтенантів - танкісти, Б і капітан - артилеристи, А молодші за званням, ніж В. Визначте рід військ і військове звання кожного з них.
3.6. У країні Радонеж деякі міста пов'язані між собою авіалініями. Зі столиці виходить 1985 авіаліній, з міста Далекого одна, а з решти міст - по 20 ліній. Доведіть, що зі столиці можна дістатися до Далекого.
Рішення.
Розглянемо безліч міст, до яких можна дістатися зі столиці. Це граф: його вершини - міста, ребра - авіалінії, їх з'єднують. З кожної вершини графа виходить стільки ребер, скільки всього авіаліній виходить з відповідного міста. Граф містить непарну вершину - столицю. Оскільки число непарних вершин у графі парне, в ньому є ще одна непарна вершина. Цією вершиною може бути тільки місто Далекий.
Завдання, при вирішенні яких використовуються вершини, сторони і діагоналі багатокутника
3.7. Чи можна організувати футбольний турнір дев'яти команд так, щоб кожна команда провела по чотири зустрічі?
Рішення
Зобразимо кожну команду точкою, а проведену нею зустріч - відрізком, що походить з цієї точки. Дев'ять точок краще розташувати так, щоб при послідовному з'єднанні їх відрізками утворився опуклий девятіугольнік.
Завдання зводитися до наступного: чи можна дев'ять точок з'єднати відрізками так, щоб з кожної точки виходили чотири відрізка? Іншими словами, чи існує граф з деят вершинами, у якого ступінь кожної вершини дорівнює 4?
Перш за все проведемо всі сторони девятіугольніка; вони будуть означати, що кожна команда провела дві зустрічі.
Для того щоб отримати ще дві зустрічі будемо, наприклад, з'єднувати всі вершини діагоналями через одну (рис. 19). (Доцільно для всіх триматися однієї і тієї ж системи проведення з них відрізків, інакше рішення ускладниться.) Після цього все виходить.
Відповідь: можна.
3.8. Чи можна провести футбольний турнір восьми команд так, щоб кожна команда провела: а) по чотири зустрічі, б) по п'ять зустрічей
3.9. Чи можна провести футбольний турнір семи команд так, щоб кожна команда провела по три зустрічі?
Рішення.
Спроби вирішити цю задачу тим же методом, що й попередні завдання, призводять до невдачі. Виникає підозра, що провести турнір таким чином не можна.
Для того щоб довести нашу гіпотезу, спробуємо замість малюнка підрахувати загальне число зустрічей, які треба провести командам. Воно дорівнює 7 (3 / 2). Але це число не є цілим.
Відповідь: не можна.
3.10. Доведіть що загальне число вершин графа, які мають непарну ступінь парне.
3.11. У трьох вершинах правильного п'ятикутника розташували по фішці. Дозволяється пересувати їх по діагоналі в будь-яку вільну вершину. Чи можна таким чином домогтися того, щоб одна з фішок повернулася на своє місце, а дві інші помінялися місцями?
3.12. Дан правильний 45-і кутник. Чи можна так розставити в його вершинах цифри від 0 до 9 так, щоб для будь-якої пари різних цифр знайшлася сторона, кінці якої занумеровані цими цифрами.
Зазначення.
Розглянути повний граф, вершини якого суть цифри від 0 до 9. Завдання зводиться до його обходу.
3.13. Доведіть що загальне число вершин графа, які мають непарну ступінь парне.
Рішення.
Позначимо число вершин графа, що мають непарну ступінь, через k, а ступені таких вершин - відповідно через а1, а2, ..., а k. Крім того, у графа можуть бути вершини з парної ступенем; позначимо ступеня цих вершин відповідно через b 1, b 2, ..., bn.
Припустимо, що число k непарній. Підрахуємо загальне число ребер графа. Воно дорівнює [(а1 + а2 + ... + а k) + (b 1 + b 2 + ... + bn)] / 2.
Сума в перших дужках чисельника отриманої дробу є число непарне, як сума непарного числа непарних доданків, а сума в других дужках число парне. Але тоді весь чисельник - число непарне, а значить дріб не є натуральним числом. Ми прийшли до протиріччя.
3.14. Чи можна 15 телефонів з'єднати між собою так, щоб кожен з них був пов'язаний рівно з 11 іншими?
3.15. Дев'ять школярів, роз'їжджаючись на канікули, домовилися, що кожен з них пошле листівки п'ятьом з інших. Чи може виявитися, що кожен з них отримає листівки саме від тих друзів, яким напише сам?
3.16. У шаховому турнірі в одне коло беруть участь 17 шахістів. Чи вірно, що в будь-який момент турніру знайдеться шахіст, який зіграв до цього моменту парне число партій (може бути жодної)?
Завдання на обведення контуру фігури безперервної лінією
3.17. У 18 столітті місто Кенігсберг (нині Калінінград у складі нашої країни) був розташований на берегах річки і двох островах. Різні частини міста було сполучено сімома мостами (рис. 20). Чи можна обійти всі ці мости так, щоб побувати на кожному з них рівно один раз?
Це і є завдання Ейлера про кенігсберзькими мостах, про яку згадувалося на початку параграфа.
Рішення.
Позначимо різні частини міста літерами А, В, С і К і зобразимо їх точками. Мости зобразимо лініями, що з'єднують ці точки. Отримаємо граф (рис. 21).
Завдання зводиться до наступної: чи існує шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз?
Розглянемо два випадки.
1) Припустимо, що існує такий замкнутий шлях. Тоді ступінь кожної вершини графа повинна бути парному, так як, входячи в будь-яких вершину, ми потім повинні з неї вийти, причому по іншому ребру. Що стосується початку шляху, то після виходу з нього ми повинні врешті-решт у нього і повернутися, оскільки шлях замкнутий. Однак на малюнку 20 немає жодної вершини, ступінь якої була б парному. Значить цей випадок неможливий.
2) Нехай існує такий незамкнений шлях; наприклад, нехай він починається у вершині А, а закінчується в С.
Тоді з вершин А і С повинно виходити вже непарне число ребер, а з проміжних вершин В і К - як і раніше парне число. Але на малюнку ступеня вершин В і К непарних. Отже, і цей випадок відпадає.
Відповідь: не можна.
Хоча міркування проведене під час вирішення завдання 3.13, виконано для окремого випадку, воно носить загальний характер:
1) якщо існує замкнутий шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз, то ступеня усіх вершин графа парні,
2) якщо існує аналогічний незамкнений шлях, то ступеня початку і кінця шляху непарні, а інших вершин - парні.
Ейлер у своїй статті довів і зворотні твердження. Нехай граф зв'язний, тобто будь-які дві його вершини можна зв'язати шляхом, які пройшли за його ребрах. Тоді шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз, існує лише в наступних двох випадках:
1) коли ступінь кожної вершини парна (у цьому випадку шлях замкнутий),
2) коли граф має тільки дві вершини А і В з непарної ступенем (тоді шлях не замкнутий і має своїми кінцями вершини А і В).
3.18. Чи можна обвести олівцем, не відриваючи його від паперу і не проводячи по одній лінії двічі:
а) квадрат з діагоналями,
б) правильний п'ятикутник з діагоналями?
3.19. Чи можна з дроту довжиною 12 дм виготовити каркас куба з ребром довжини 1 дм, не ламаючи дріт на частини?
3.20. Чи можна граф, зображений на малюнку 22, обвести олівцем, не відриваючи його від паперу і не проходячи жодної лінії двічі? Якщо можна, то як?
3.21. У точці А розташований гараж для снігоочисної машини (рис. 23). Водієві машини було доручено прибрати сніг з вулиць частини міста зображеної на малюнку. Чи може він закінчити свою роботу на тому перехресті, де знаходиться гараж, якщо по кожній вулиці своєї ділянки міста водій буде проїжджати тільки один раз?
3.22. У марсіанському метро 100 станцій. Від будь-якої станції до будь Інший можна проїхати. Страйковий комітет хоче закрити проїзд через одну із станцій так, щоб між усіма іншими станціями був можливий проїзд. Доведіть, що така станція знайдеться.
3.23. У тридев'ятому царстві кожні два міста з'єднані дорогою з одностороннім рухом. Доведіть, що існує місто, з якого в будь-який інший можна проїхати не більше ніж за двома дорогами.
3.24. У місті на кожному перехресті сходиться парне число вулиць. Відомо, що з будь-вулиці міста можна проїхати на будь-яку іншу. Доведіть, що всі вулиці міста можна об'їхати, побувавши на кожній по одному разу.
Різні завдання на графи.
3.25. У кутах шахівниці 3х3 коштують 4 коня: 2 білих (у сусідніх кутах) і два чорних. Чи можна за кілька ходів (з шахових правилами) поставити коней так, щоб у всіх сусідніх кутах стояли коні різного кольору?
Рішення.
Відзначимо центри клітин дошки і з'єднаємо відрізками пари зазначених точок, якщо з однієї в іншу можна пройти ходом коня. Ми отримаємо граф, що містить «цикл» з восьми точок і одну ізольовану точку (рис. 24). Переміщення коней по дошці відповідає руху по ребрах цього циклу. Ясно, що при русі по циклу не можна змінити порядок проходження коней.
3.26. Випишіть в ряд цифри від 1 до 9 так, щоб число, складене з двох сусідніх цифр, поділялося або на 7, або на 13.
Рішення.
Напишемо цифри на аркуші. З'єднаємо стрілками ті цифри, які можуть слідувати один за одним (рис. 25). Тепер ясно, що першою йде 7, потім 8 і 4. Оскільки 8 вже використана, то стрілки, що йдуть до неї, треба прибрати. Після 4 йде 9, оскільки до дев'ятці іншого шляху немає. Далі йде 1 і так далі.
Відповідь: 784913526.
3.27. У шкільному турнірі в одне коло грають шість шахістів: Олександр, Борис, Віктор, Григорій, Дмитро і Костя. Щодня гралися три партії, і весь турнір закінчився у п'ять днів. У перший день Боря грав з Олексою, а в другій - з Костею. Вітя в четвертий день грав з Костею, а в п'ятий з Дімою. Хто з ким грав у кожен день турніру?
Рішення.
Позначимо шахістів відповідно точками А, Б, В, Г, Д і К, а зіграні ними партії - відрізками, що з'єднують ці точки.
Точки краще розташовувати так, щоб при послідовному їх поєднанні вони стали вершинами правильного шестикутника.
1) Перший день турніру. За умовою в цей день Боря грав з Олексієм. З ким грав Вітя? Тільки з Грицем, так як з Дімою і Костею він грав у інші дні. Отже, третю партію в перший день грали Діма з Костею. Побудуємо відповідний граф (рис. 26).
2) Другий день турніру. У цей день Боря грав з Костею, тому Вітя, з огляду на перший і п'ятий дні, міг грати лише з Олексою (рис. 27).
3) Третій день турніру. Вітя, з урахуванням всіх попередніх і наступних турніру, міг грати тільки з Борею. Так як Діма вже грав з Костею і Грицем, то в цей день він грав з Олексою (рис. 28). Значить Гриша грав з Костею.
4) Четвертий день турніру. Тут неважко визначити, хто з ким грав: Вітя - з Костею, Альоша - з Грицем, Боря з Дімою (рис.29).
5) П'ятий день турніру (рис. 30).
3.28. В одному купе поїзда їхали чотири пасажири. Серед них не було трьох осіб, які раніше були знайомі один з одним, але один був знайомий з трьома іншими. Доведіть, що ці три останніх пасажира раніше не були знайомі один з одним.
3.29. Кожні дві з шести ЕОМ з'єднані проводом. Чи можна всі ці дроти розфарбувати в один з п'яти кольорів так, щоб з кожної ЕОМ виходили п'ять проводів різного кольору?
Рішення. Для вирішення накреслимо опуклий шестикутник
і проведемо в ньому все діагоналі (рис. 31). Нехай кожна вершина шестикутника означає однуB з ЕОМ, а кожен відрізок провід, що з'єднує дві ЕОМ. Занумеруем різні кольори натуральними числами від 1 до 5 для того, щоб відрізняти їх один від одного. Почнемо наприклад з вершини Апроведем з неї відрізки всіх п'яти кольорів. Перейдемо до вершини В і з неї проведемо чотири відрізка всіх квітів з № 2 по № 5, враховуючи, що відрізок ВА, що виходить з цієї вершини, вже забарвлений в колір № 1. Потім займемося вершиною С. І т. д. У результаті отримуємо позитивну відповідь на питання завдання.
Відповідь: можна.
На малюнку 31 кожні дві вершини графа з'єднані своїм ребром. Такий граф називається повним.
3.30. На туристському зльоті з'ясувалося, що кожен юнак знаком з 8 дівчатами, кожна дівчина знайома з 6 юнаками. Кого на зльоті більше: юнаків або дівчат?
3.30. На гуртку, в якому беруть участь шість школярів, було дано шість завдань. Кожен школяр вирішив два завдання, і кожне завдання вирішили два школярі. Доведіть, що розбір завдань можна організувати так, щоб кожен школяр виклав вирішення однієї з вирішених ним завдань і всі завдання були розібрані.
Рішення.
Зобразимо школяра точкою, а вирішену їм завдання - лінією виходить із цієї точки. Нехай один із школярів позначений крапкою А.. Проведемо з неї лінію. Так як кожне завдання вирішили два школяра, то проведена лінія з'єднує точку А з іншою точкою В, яка позначає другу школяра, який вирішив ту ж задачу. Оскільки кожен школяр вирішив два завдання, то з точки В повинна виходити ще одна лінія, яка з'єднує точку В з ще однією точкою С і т. д.
Можливі наступні випадки.
1) Може вийти шестикутник. Тоді твердження завдання виконується.
2) Може вийти чотирикутник і «двуугольнік»; останнє можливо тоді, коли двоє школярів вирішили одні й ті ж завдання.
3) Можуть вийти два трикутника.
4) Можуть вийти три «двуугольніка».
Цим вичерпуються всі можливості. У кожному з розглянутих випадків твердження завдання виконується.
3.31. На столі в приймальні перукарні лежать журнали. Кожен клієнт перукарні переглянув два журнали; кожен журнал переглянули три людини; для кожної пари журналів є тільки один клієнт, який їх переглянув. Скільки журналів і скільки клієнтів у приймальні перукарні?
Рішення.
Позначимо журнал точкою, а клієнта, переглянув цей журнал - відрізком, що виходять з цієї точки.
Візьмемо одну таку точку А. Так як кожен журнал переглянули три людини, то з точки А повинні виходити три відрізки. Оскільки кожен клієнт переглянув два журнали, то кожен
Відрізок з'єднають дві точки. (Рис. 32).
Оскільки кожну пару журналів переглянув одна людина, то треба кожну пару точок з'єднати відрізком. Отримуємо чотирикутник з діагоналями (рис. 33). Перевірте ще самі, що тут всі три умови задачі виконуються.
Може виникнути питання: а чи не існує ще хоча одна, п'ята точка Е, така, що всі умови задачі виконуються? Тоді з кожної з п'яти точок буде виходити не по три, а по чотири відрізка, а це суперечить умовам завдання.
Відповідь: 4 журналу, 6 клієнтів.
3.32. У одній установі кожен співробітник виписує дві газети, кожну газету виписує п'ять людей і кожну пару газет виписує тільки одна людина. Скільки людей в установі і скільки вони виписують газет.
3.33. Шість точок, з яких ніякі три не лежать на одній прямій з'єднані всілякими відрізками і кожен відрізок забарвлений в чорний або червоний колір. Доведіть, що знайдеться трикутник з вершинами в даних точках, у якого всі сторони чорні, або трикутник, у якого всі сторони червоні.
Рішення.
Візьмемо одну з шести точок А1более чотирьох відрізків (по узагальненому принципу Діріхле). Нехай відрізки А1А2, А1А3 і А1А4 - червоні. Розглянемо два випадки.
1) Припустимо, що серед відрізків А2А3, А2А4 і А3А4 є червоний, наприклад відрізок А2А3. Тоді у трикутника А1А2А3 всі сторони червоні. Саме цей варіант зображений на малюнку 34.
2) Якщо припустимо, що серед відрізків А2А3, А2А4 і А3А4 немає червоного, тоді всі ці відрізки - чорні, а отже у трикутника А2А3А4 всі сторони чорні.
3.34. Доведіть, що якщо в задачі 3.33 замість шести точок взяти п'ять, трикутник з одноколірними сторонами може і не знайтися.
3.35. У міжнародному туристичному таборі шість туристів познайомилися між собою. З'ясувалося, що серед будь-яких трьох з них є двоє, які можуть розмовляти один з одним на якому-небудь мовою. Чи вірно, що серед них знайдуться троє, кожен з яких може розмовляти з кожним із двох інших на якому-небудь мовою?
3.36. 17 учених із різних країн переписуються між собою на одному з трьох мов: англійською, французькою або російською. Доведіть, що серед них знайдуться троє, які переписуються між собою на одному і тому ж мовою.
Рішення.
Позначимо кожного з учених точкою і з'єднаємо ці точки всілякими відрізками. Точки розташуємо так, щоб ніякі три з них не лежали на одній прямій. Так як кожен учений листується з 16 іншими, то з кожної точки виходить 16 відрізків. Кожен з відрізків, що означає листування вчених на англійській мові, забарвимо в чорний колір, французькою - в червоний, російською - у білий.
Розглянемо два випадки.
1) Нехай серед відрізків, що з'єднують точки А2, А3, А4, А5, А6 і А7 попарно між собою, є чорний, скажімо А2А3. Тоді у трикутника А1А2А3 всі сторони чорні, тобто відповідна трійка вчених переписуються між собою англійською мовою.
2) Нехай серед цих відрізків немає чорного. У цьому випадку відрізки між шістьма точками А2, А3, А4, А5, А6 і А7 пофарбовані не більше, ніж у два кольори - червоний і білий. Тоді на підставі затвердження завдання 3.33 серед відрізків, що з'єднують ці точки, є три, складові трикутник зі сторонами одного кольору.
3.37. На площині дано п точок, з яких ніякі три не лежать на одній прямій. Вони з'єднані всілякими відрізками, і кожен відрізок забарвлений в один з чотирьох різних кольорів. При якому найменшому п обов'язково знайдеться трикутник з одноколірними сторонами з вершинами у трьох з даних точок?
3.38. Послідовність з 36 нулів та одиниць починається з п'яти нулів. Серед п'ятірок поспіль стоять цифр зустрічаються всі 32 можливі комбінації. Знайдіть п'ять останніх цифр послідовності.
3.39. Доведіть, що можна розташувати по колу символи 0 і 1 так, щоб будь-який можливий набір з n символів, що йдуть поспіль, зустрівся.
Зазначення.
Розглянути граф, вершини якого суть слова довжини n -1. Дві вершини u і v з'єднуються стрілкою, якщо існує слово довжини n, у якого u є початком, а v - кінцем.
4. Розмальовки
Кажуть, що фігура пофарбована в кілька кольорів, якщо кожній точці фігури приписаний певний колір. Бувають завдання, де розфарбування вже дана, наприклад для шахової дошки, бувають завдання, де розфарбування з даними властивостями потрібно придумати, і бувають завдання, де розфарбування використовується як ідея рішення.
Завдання
4.1. З шахової дошки вирізали дві протилежні кутові клітини. Доведіть, що залишилася постать не можна розрізати на «доміно» з двох клітин
Рішення.
Кожна фігура «доміно» містить 1 білу і 1 чорну клітину. Але в нашій фігурі 32 чорних і 30 білих клітин (або навпаки).
4.2. Чи можна все клітини дошки 9х9 обійти конем по одному разу і повернутися у вихідну клітку?
Рішення.
Кожним ходом кінь змінює колір клітини, тому, якщо існує обхід, то число чорних клітин дорівнює числу білих, що невірно.
4.3. Дан куб 6х6х6. Знайти максимально можливе число паралелепіпедів 4х1х1 (зі сторонами паралельними сторонам куба), які можна помістити в цей куб без перетинів.
Ідея рішення.
Легко розмістити 52 паралелепіпеда всередину куба. Доведемо, що не можна більше. Розіб'ємо куб на 27 кубиків 2х2х2. Розфарбуємо їх у шаховому порядку. При цьому утворюється 104 клітини одного кольору (білого) і 112 - іншого (чорного). Залишилось зауважити, що кожен паралелепіпед містить дві чорних і два білих клітини.
Відповідь: 52.
4.4. Пряма розфарбована в 2 кольори. Доведіть, що знайдуться 3 точки А, В, С одного кольору такі, що AB = НД
4.5. Розфарбуйте пряму в 3 кольори так, щоб не можна було знайти трьох точок А, В, С різного кольору таких, що AB = НД
5. Площина розфарбована а) в 2 кольори, б) в 3 кольори. Доведіть, що знайдуться 2 точки одного кольору, відстань між якими дорівнює 1
Ідею, винесену в заголовок, добре ілюструє наступне завдання. 4.6. Є квадрат 8Х8, з якого видалено дві кутові клітини, розташовані на одній діагоналі. Чи можна цей квадрат замостити кісточками доміно розмірами 1х2? Рішення дає нам правильна «шахова» розфарбування цієї дошки. Кожна кісточка доміно закриває дві клітини різного кольору, у той час як клітин чорного і білого кольорів різна кількість.
А ось ще два завдання на цю ідею.
4.7. Ділянка прямокутної форми розбитий на квадрати, що утворюють n рядів по m квадратів в кожному ряду. Кожен квадрат є окремою ділянкою, сполученим хвіртками з усіма сусідніми ділянками. За яких m і n можна обійти всі квадратні ділянки, побувавши у кожному по одному разу, і повернутися в початковий?
Рішення.
Розфарбуємо квадрати в шаховому порядку. При кожному переході міняється колір квадрата. Тому, якщо такий маршрут можливий, то число кроків має бути парним, тобто m або n парне. Залишилося перевірити, що в цьому випадку шуканий маршрут можливий.
4.8. Всі ми в дитинстві грали в «морський бій». Нагадаємо, що грається він на квадраті 10Х10, на картатої папері. «Лінкором» у цій грі називається «корабель» 1х4. У зв'язку з цим виникає питання: чи можна весь квадрат для морського бою розрізати на 25 лінкорів? А до речі, дайте відповідь ще на одне питання: яку найменшу число «пострілів» треба зробити, щоб напевно хоча б один раз потрапити у лінкор, самотньо плаваючий по морю?
Рішення.
Розфарбуємо клітини в 4 кольори, як на рис. 36. Кожен «лінкор» закриває чотири клітини різного кольору. Але клітин кольору 2 всього 26, а «лінкорів» має бути 25.
Ця ж розфарбування допомагає відповісти і на друге питання. Найменше число пострілів дорівнює числу клітин кольори 4, тобто 24.

5. Завдання з цілими числами. Парні і непарні числа
Зазвичай парні і непарні числа пов'язують лише з натуральними числами. Тут ми розповсюдимо їх на будь-які цілі числа. Ціле число називається парним, якщо воно ділиться на 2, і непарних, якщо воно на 2 не ділиться.
Будь-яке парне число можна представити у вигляді 2 а, а будь-яке непарне - у вигляді 2 а + 1, де а - ціле число.
Два цілих числа називаються числами однаковою парності, якщо обидва вони парні чи непарні обидва. Два цілих числа називаються числами різної парності, якщо одне з них парне, а інше непарне.
Розглянемо властивості парних і непарних чисел важливі, для вирішення завдань.
1) Якщо хоча б один множник твори двох (або декількох) чисел четен, то і весь твір парне.
2) Якщо кожен множник твори двох (або декількох) чисел непарне, то і весь твір непарній.
3) Сума будь-якої кількості парних чисел є число парне.
4) Сума парного і непарного чисел є число непарне.
5) Сума парного кількості непарних чисел є число парне; сума непарної кількості непарних чисел є число непарне.
Завдання
5.1. У п'ятиповерховому будинку з чотирма під'їздами підрахували число жителів на кожному поверсі і, крім того, в кожному під'їзді. Чи можуть все отримані 9 чисел бути непарними?
Рішення.
Позначимо число жителів на поверхах відповідно через а1, а2, а3, а4, а5, а число жителів у під'їздах - відповідно через b 1, b 2, b 3, b 4. Тоді загальна кількість жителів будинку можна підрахувати двома способами - по поверхах і по під'їздах:
a1 + а2 + а3 + а4 + а5 = b 1 + b2 + b3 + b 4.
Якби всі ці 9 чисел були непарними, то сума в лівій частині записаного рівності була б непарної, а сума в правій частині - парному. Отже, це неможливо.
Відповідь: не можуть.
5.2. У футбольному турнірі в одне коло беруть участь 15 команд. Доведіть, що в будь-який момент турніру знайдеться команда, яка зіграла до цього моменту парне число матчів (може бути, жодного).
Рішення.
Позначимо число матчів, проведених першої, другої, третьої і т. д. командами, через а1, а2, а3, ..., А15.
Припустимо, що всі ці 15 чисел непарних. Підрахуємо загальне число матчів, проведених командами. Воно дорівнює
(А1 + а2 + ... + А15) / 2.
Але чисельник дробу є число непарне, як сума непарного числа непарних доданків. Тоді загальна кількість матчів є число дробове. Отримали протиріччя.
Затвердження завдання є окремий випадок однієї з теорем теорії графів.
5.3. Парне чи непарне твір
(7а + b - 2 c +1) (3 a - 5 b + 4 c + 10),
  де числа a, b, c - цілі?
Рішення.
Можна перебирати випадки, пов'язані з парністю або непарних чисел а, b, c (8 випадків!), Але простіше поступити інакше. Складемо множники:
(7 a + b - 2 c + 1) + (3 a - 5 b + 4 c + 10) =
= 10 a - 4 b + 2 c + 11.
Так як отримана сума непарна, то один із множників цього твору четен, а інший непар. Отже, сам твір парне.
Відповідь: парне.
5.4. Нехай а 1, а 2, а 3, ..., а 25 - цілі числа, а з 1, с 2, с 3, ..., з 25 - ті ж самі числа, взяті в іншому порядку. Доведіть, що число
1 - з 1)2 - з 2)3 - з 3) ... (а 25 - з 25)
є парним.
5.5. Парне чи непарне число
1 - 2 + 3 - 4 + 5 - 6 + ... + 993?
Рішення.
Різниця 1 - 2 має ту ж парність, що і сума 1 + 2, різниця 3 - 4 - ту ж парність, що і сума 3 + 4, і т. д. Тому дана сума має ту ж парність, що і сума
1 + 2 + 3 + 4 + 5 + 6 + ... + 993.
З 993 доданків останньої суми 496 парних і 497 непарних, отже, сума непарній.
П о в е т: непарній.
5.6. На пряме розташовано кілька точок. Потім між кожними двома сусідніми точками поставили ще по точці. І т. д. Доведіть, що після кожної такої операції загальна кількість точок буде непарним.
Зазначення.
Якщо є п точок і до них додається ще п - 1 проміжних точок, то загальна кількість точок стає непарних, так як п + (п -1) = = 2 п - 1.
5.7. Знайдіть всі цілі значення а, при яких число
x 3 + ax 2 + 5x + 9
непарній для всіх цілих значень х.
5.8. На семи картках написали числа 1, 2, 3, 4, 5, 6 і 7. Потім картки перевернули, перемішали і на зворотних сторонах написали ті самі числа. Числа, написані на обох сторонах кожної картки, склали і отримані суми перемножила. Парне або непарній отримане твір?
Рішення.
Припустимо, що твір непарній. Для цього всі 7 множників повинні бути непарними. Але тоді у чотирьох карток, у яких на одній стороні написані непарні числа 1, 3, 5, 7, на іншій стороні повинні бути числа парні. Однак парних чисел тут - тільки три. Отже, цей випадок неможливий.
Відповідь: парне.
5.9. Доведіть, що в будь-якій компанії число тих людей, які знайомі з непарним числом членів компанії, парне.
Рішення.
Позначимо число людей, які мають у компанії непарне число знайомих, через k, а число знайомих цих людей відповідно через a 1, a 2, ..., a k. Крім того, число людей, знайомих з парним числом членів компанії, позначимо через n, а число знайомих цих людей відповідно через b 1, b 2, ..., b n. Тоді загальна кількість знайомств одно
(A 1 + a 2 + ... + a k + b 1 + b 2 + ... + b n ) / 2
Сума b 1 + b 2 + ... + b n   парна, так як всі її складові парні.
Тоді для того, щоб ця частина була рівна цілому, сума
a 1 + a 2 + ... + a k , Повинна бути парному. Але всі складові останньої суми непарних, тому число k доданків суми може бути тільки парним.
5.10. Доведіть, що не існує багатогранника, у якого 1997 граней - трикутники, а інші грані - чотирикутники і шестикутники.
5.11. Окружність розділили на 40 рівних дуг і в 40 точках розподілу поставили по шашці. Серед шашок 25 білих і 15 чорних. Доведіть, що серед шашок знайдуться біла і чорна, які стоять на кінцях одного діаметра.
Рішення.
Припустимо, що це не вірно. Розглянемо будь-яку білу шашку і діаметр, на якому вона стоїть. Тоді на нашу допущенню на іншому кінці цього діаметру повинна стояти теж біла шашка. Виходить, що всього білих шашок (як і чорних) парне число. Але останнє суперечить умові задачі.
5.12. Сума номерів будинків одного кварталу дорівнює 99, а сусіднього кварталу тієї ж вулиці - 117. Знайдіть номери всіх будинків цих кварталів.
5.13. У деякому натуральному числі довільно переставили цифри. Доведіть, що сума отриманого числа з вихідним не може бути дорівнює 999 ... 9 (125 дев'яток).
Рішення.
Позначимо вихідне число через а, число, отримане з нього після перестановки цифр - через b.
Припустимо, що рівність
а + b = 999 ... 9 (125 дев'яток)
можливо. Тоді при додаванні чисел а і b не може бути перенесення одиниці в наступний розряд. Так як сума цифр чисел а і b рівні, то сума цифр у числа а + b у два рази більше, ніж у числа а, а значить вона парні. Але з іншого боку, ця сума дорівнює 9 125, а отже, непарна. Ми отримали протиріччя.
5.14. Яке найбільше кількість натуральних чисел можна записати в рядок так, щоб сума будь-яких трьох сусідніх чисел була парною, а сума будь-яких чотирьох сусідніх чисел - непарної?
Рішення.
Позначимо послідовні натуральні числа рядка через а 1, а 2, а 3 і т. д.
За умовою суми
а 1 + а 2 + а 3, а 2 + а 3 + а 4, а 3 + а 4 + а 5, а 4 + а 5 + а 6
та інші парні. Віднімаючи з кожної суми, починаючи з другої, попередню отримаємо, що різниці    
а 4 - а 1, а 5 - а 2, а 6 - а 3, ...
парних, а отже, мають однакову парність пари чисел
а 4 і а 1, а 5 і а 2, а 6 і а 3 і т. д.
Випишемо непарні суми, що складаються з чотирьох сусідніх чисел: а 1 + а 2 + а 3 + а 4 = 1 + а 2 + а 3) + а 4,
а 2 + а 3 + а 4 + а 5 = (а 2 + а 3 + а 4) + а 5,
а 3 + а 4 + а 5 + а 6 = (а 3 + а 4 + а 5) + а 6, ...
Звідси випливає, що числа а 4, а 5, а 6 і т. д. непарних. Але тоді сума а 4 + а 5 + а 6 непарна, а це суперечить умові.
Отримане протиріччя виникає кожного разу, коли чисел не менше шести. Спробуємо взяти п'ять чисел.
Розмірковуючи аналогічно, встановлюємо, що числа а 4, а 5 непарних, а отже, за попереднім, непарних і числа а 1, а 2. Тоді, так як сума а 1 + а 2 + а 3 парна, то число а 3 парне.
Зробимо ще перевірку і переконаємося в тому, що якщо взяти п'ять чисел а 1, а 2, а 3, а 4, а 5, де число а 3 парне, а інші непарних, то кожна із сум а 1 + а 2 + а 3 , а 2 + а 3 + а 4, а 3 + а 4 + а 5 парна, а кожна із сум а 1 + а 2 + а 3 + а 4, а 2 + а 3 + а 4 + а 5 непарних.
Відповідь: 5.
5.15. Чи можна на картатій папері, зафарбувати 25 клітин так, щоб у кожної з них було: а) парне, б) непарне число зафарбованих сусідів? (Клітини називаються сусідами, якщо у них спільна сторона)
Рішення.
Припустимо, що вдалося зафарбувати 25 клітин потрібним чином. Спробуємо знайти число загальних сторін зафарбованих кліток і прийдемо до протиріччя. Порахуємо, скільки в кожної клітини загальних сторін з сусідами, складемо отримані числа і суму розділимо навпіл (так як кожну загальну сторону ми вважали при цьому двічі). У кожної клітини - непарне число сусідів, і клітин 25. Сума 25 непарних чисел непарна і тому без остачі на 2 не ділиться.
Відповідь: а) можна, б) не можна.
Таке ж міркування показує, що при будь-якій непарній n, зафарбувати n клітин так, щоб у кожній було непарне число зафарбованих сусідів, неможливо. У разі будь-якого парного n таке розфарбовування можлива.
5.16. Чи існує замкнута ламана, яка перетинає кожне свою ланку рівно один раз і складається з: а) 6 ланок, б) 7 ланок?
Прості і складені числа
Натуральне число, більше 1, називається простим, якщо воно ділиться тільки на 1 і на саме себе. Натуральне число називається складовим, якщо воно має більше двох різних дільників.
Прийнято вважати, що число 1 не відноситься ні до простих, ні до складних чисел.
Звідси випливає, що безліч натуральних чисел можна розбити на такі три підмножини: безліч простих чисел, безліч складових чисел і безліч містить єдиний елемент 1.
Справедлива наступна теорема.
Будь-яке натуральне число, більше 1, можна і до того ж єдиним чином представити у вигляді добутку простих чисел.
Це пропозиція називається основною теоремою арифметики натуральних чисел.
Серед простих дільників натурального числа можуть бути рівні, і їх добуток можна записати у вигляді ступеня. Тоді розкладання натурального числа а на прості множники можна представити в наступному вигляді:
a = p 1 k 1 p 2 k 2 ... p n kn ,
де p 1, p 2, ..., p n - Різні прості числа, k1, k2, ..., kn - натуральні.
Завдання
5.17. До двузначному числа приписали таке ж число. Чи може отримане число бути простим?
5.18. До числа, що є твором двох послідовних натуральних чисел, приписали праворуч число 21. Доведіть, що отримане число - складене.
5.19. Натуральні числа a і b такі, що 31 a = 54 b. Доведіть, що число a + b - складене.
Рішення.
Так як число 31 а ділиться на 54 і числа 31 і 54 - взаємно прості, то а ділиться на 54: a = 54 n; де n ÎN. Тоді
31 54 n = 54 b, b = 31n.
Звідси a + b = 54 n + 31 n = 85 n, а отже, число a + b є складовим.
5.20. Натуральні числа a і b задовольняють умові 15 a = 32 b. Чи може число a - b бути простим? Якщо може - побудуйте приклад, якщо не може - доведіть.
5.21. Назвіть всі натуральні n, при яких число n 4 + 4-складене.
Рішення.
Спробуємо розкласти вираз n 4 + 4 на множники з цілими коефіцієнтами. Ми звикли до того, що сума квадратів на множники з цілими коефіцієнтами не розкладається. У даному випадку це робиться за допомогою прийому «плюс - мінус» наступним чином:
n 4 + 4 = (n 4 + 4 + 4 n 2) - 4 n 2 = (n 2 + 2) 2 - 4 n 2 = (n 2 + 2 n + 2) (n 2 - 2 n + 2) .
Очевидно, множник n 2 + 2 n + 2 завжди більше 1. Другий множник n 2 - 2 n + 2 може бути рівним 1:
n 2 - 2 n + 2 = 1, n 2 - 2 n + 1 = 0, (n - 1) 2 = 0, n = 1.
Тому що при n = 1 множник n 2 + 2 n + 2 приймає значення 5, що є простим числом, то значення n = 1 потрібно відкинути.
Відповідь: все n не рівні 1.
5.22. Доведіть, що будь-яке число виду а = 101010 ... 101 (n нулів, n + +1 одиниця, де n> 1) - складене.
Рішення.
Перетворимо число а, враховуючи, що всього у нього 2 n + 1 цифр, а отже, перша одиниця - розряду 2 n:
a = 101010 ... 101 = 10 2n + 10 2n-2 + 10 2n-4 + ... + 10 2 + 1 =
= (1 / (10 2 -1)) (10 2 - 1) (10 2n + 10 2n-2 + ... +10 2 +1) =
= (1 / 99) (10 2n +2 -1) = (1 / 99) ((10 n +1) 2 - 1) = (1 / 99) (10 n +1 +1) (10 n +1 -1).
Тепер розглянемо два випадки.
1) Нехай n парне.
Тоді сума 10 n +1 +1 ділиться на 11, причому частка від такого розподілу більше 1, тому що 10 n +1 +1> 11; різниця 10 n +1 -1 ділиться на 9, причому приватне також більше 1, тому що 10 n +1 +1> 11; різниця 10 n +1 -1 ділиться на 9, причому приватне також більше 1. Вийшло складене число
а = ((10 n +1 +1) / 11) ((10 n +1 -1) / 9).
2) Нехай n непарне.
У цьому випадку різниця 10 n +1 -1 ділиться на 10 2 - 1 = 99 і приватне більше 1, оскільки 10 n +1 -1> 99.
5.23. Доведіть, що всі числа виду
10001,100010001,1000100010001, ...
- Складові.
5.24. Доведіть, що число 8 (3 травня k + 5 травня n) - 5 при будь-яких натуральних k і n є складеним.
5.25. Яке найбільше число простих чисел може бути серед 15 послідовних натуральних чисел, великих 2?
Рішення.
Очевидно, прості числа потрібно шукати серед непарних. З 15 послідовних натуральних чисел є 7 чи 8 непарних. Серед будь-яких трьох послідовних чисел натуральних рівно одне ділиться на 3, тому серед 7 або 8 послідовних непарних натуральних чисел є 2 або 3 числа, що діляться на 3. Якщо їх відкинути, то залишиться 5 або 6 непарних чисел.
Потрібно ще переконатися, що такі 6 простих чисел можливі. Наприклад, якщо взяти такі 15 послідовних натуральних чисел: 3, 4, 5, 6, ..., 17, то серед них - 6 простих. 3, 5, 7, 11, 13, 17.
П о в е т: 6.
5.26. Складіть з простих чисел всі можливі арифметичні прогресії з різницею 6 і числом членів, великим 4.
5.27. Доведіть, що всі числа p, p + 2, p + 4 є простими тільки у випадку, коли вони утворюють трійку 3, 5, 7.
Рішення.
Розглянемо кілька випадків, в залежності від p.
При p = 2 число p +2 = 4 - складене, тому значення p = 2 відпадає.
При p = 3 отримаємо трійку 3, 5, 7, про яку згадується в умові завдання.
При p = 5 число p + 2 = 7 - просте, але число p + 4 = 9 - складене, значить, p = 5 потрібно відкинути.
При p = 7 число p + 2 = 9 - складене.
При p = 11 число p + 4 = 15 - теж складене.
Виникає припущення, що підходить тільки p = 3. Доведемо його.
Неважко помітити, що значення p = 5, p = 7, p = 11 не підходили тому, що або p + 2 або p + 4 діляться на 3. Переконаємося, що так буде завжди при простому p> 3.
Просте число, більше 3, не ділиться на 3 і, отже, при діленні на 3 може давати в залишку лише 1 або 2. Розглянемо обидва випадки.
1) Нехай p при діленні на 3 дає в залишку 1: p = 3k + 1 (kÎN). Тоді число p + 2 = (3k + 1) + 2 = 3k = 3 ділиться на 3, причому частка від цього поділу більше 1. Значить число p + 2 складене.
2) Нехай p = 3k + 2 (kÎN). Тоді число p + 4 = (3k + 2) + 4 = 3k + 6 - складене.
5.28. Знайдіть всі такі p, що числа p, p + 10 і p + 20 - прості.
Завдання цього пункту - це, по суті, числові ребуси. Своєрідність таких завдань у тому, що одна з двох компонент дії виходить з іншої шляхом перестановки або закреслення цифр.
Завдання на закреслення цифр у натуральному числі
5.29. Знайдіть всі натуральні числа, які при закреслення останньої цифри зменшуються в 14 разів.
Рішення.
Позначимо дані число через 10 x + y, де x - кількість десятків числа, y - його остання цифра. Тоді
10 x + y = 14 x, y = 4 x.
Так як y є цифра, то і x - цифра, причому не перевершує 2. Вважаючи x = 1, 2, знаходимо, що відповідно y = 4, 8.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова | 224,1кб. | скачати

Схожі роботи:
Завдання в шкільному курсі математики
Контрольні завдання для заочників з математики
Основні завдання обчислювальної математики
Предмет і завдання методики початкового навчання математики
Компетентнісно-орієнтовані завдання в процесі навчання математики учнів основної школи
Нестандартні уроки в школі
Нестандартні уроки в молодших класах
Нестандартні уроки в початкових класах
Нестандартні питання хімії та їх вирішення
© Усі права захищені
написати до нас
Рейтинг@Mail.ru