Універсальний інваріант на кожній орбіті приймає своє значення. Оскільки для універсального інваріанта 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.
Порахуємо r (б i). При i не рівному п:
x ₁ (бi) == x ₂ (б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. Крім того, q (б n) = nn і r (б n) = 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 ₁ (a) = f ₁ (p),
f ₂ (a) = f ₂ (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 ₁ (x, y) = xy,
f ₂ (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 ₁ (x, y, z) = xyz,
f ₂ (x, y, z) = ху + у z + z х,
f ₃ (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? Рішення дає нам правильна «шахова» розфарбування цієї дошки. Кожна кісточка доміно закриває дві клітини різного кольору, у той час як клітин чорного і білого кольорів різна кількість.