Принцип Діріхле: завдання з рішеннями
У математиці існує безліч принципів. Деякі з них досить прості і зрозумілі навіть новачкові, а деякі вимагають певних пояснень і доказів. Проте всі вони досить ефективні, і їх легко можна застосовувати на практиці. Одним з них є принцип Дирихле (відомий також як принцип голубів / кроликів). Це досить просте твердження, здатне допомогти у вирішенні багатьох математичних задач.
Історія
Даний принцип був сформульований почесним німецьким математиком Йоганном Дирихле ще в 1834 році. Сьогодні його застосовують в комбінаториці, а також в математичній фізиці. У перекладі з оригінального німецького він звучить як «принцип ящиків». Свої дослідження вчений проводив з кроликами і контейнерами. Він продемонстрував, що якщо помістити, припустимо, 5 кроликів в 7 контейнерів, то, принаймні, в одному контейнері буде знаходитися 5/7 від однієї тварини. Однак кролика не можна розділити на частини, отже, хоча б одна клітина буде пустувати (5/7 дорівнює 0 цілих). Точно так само і у зворотний бік, якщо кроликів 7, а ящиків 5, то хоча б в одному з них - 2 кролика (7/5 дорівнює 2 цілих). Відштовхуючись від цього твердження, математику вдалося сформулювати принцип, який забезпечує успішне вирішення завдань з математики вже багато років.
Сучасна формулювання і доказ
На сьогоднішній день існує декілька різних формулювань даного принципу. Сама зрозуміла і проста увазі, що не можна посадити 8 кроликів в 3 клітини так, щоб у кожній було не більше 2. Більш наукова і складна формулювання, що пояснює принцип Діріхле, говорить: якщо в k осередків знаходиться k + 1 зайців, то, по крайней мірі, в 1 комірці буде розташовуватися більше одного зайця. А якщо в k осередків знаходиться k-1 зайців, то принаймні в 1 комірці буде розташовуватися менше одного зайця. Доказ цього твердження зовсім просте, так би мовити, від протилежного. Якщо припустити, що в кожному осередку розташовується зайців менше, ніж k-1 / k, тоді в k осередків зайців менше ніж k * k-1 / k = k-1, а це суперечить початковим умовам.
Насправді такий простий і зрозумілий принцип значно полегшує вирішення завдань з математики та докази багатьох трудомістких теорем. Просто необхідно враховувати, що зайців і комірки можна легко замінити на математичні предмети і об'єкти (цифри, точки, відрізки, фігури і т. Д.).
Ще одне формулювання
Іноді завдання на принцип Діріхле - не такі прості й очевидні, як з тваринами в ящиках. Необхідно переносити цей принцип на математичні безлічі, щоб відшукати будь-які рішення. У такому випадку можна спиратися на іншу, більш складну формулювання.
Якщо відобразити безліч S, що містить d + 1 елементів, в безліч R з сукупністю d елементів, то два елементи з безлічі S будуть мати однаковий образ.
Хоча сучасні ФГОС з математики пред'являють до учнів творчі вимоги і пропонують нестандартні варіанти, рішення через утвердження Дирихле не завжди таке просте і зрозуміле. Іноді дуже важко визначити, яку величину вважати тваринам, а яку - кліткою, і яким чином факт наявності двох тварин в одній клітці допоможе вирішенню завдання. Та й якщо вдасться в цьому розібратися, все одно не можна визначити, в якій саме клітці буде знаходитися об'єкт. Тобто можна просто довести існування такого осередку, але не можна конкретизувати її.
Приклад № 1. Геометрія
Сучасні приклади розв'язання задач демонструють, що тваринами і клітинами можуть виступати вчинене різні математичні предмети.
Завдання
Пряма k проходить через площину трикутника ABC, однак не перетинає жодну його вершину. Необхідно довести, що вона не може перетинати три його сторони.
Рішення
Уявімо, як пряма k розбиває трикутник на дві площини, назвемо їх s1 і s2. Будемо вважати, що s1 і s2 відкриті, тобто не містять пряму k. Ну а зараз - саме час застосувати принцип Дирихле. Завдання з рішеннями можуть продемонструвати, що під кроликами і осередками в сучасних умовах маються на увазі різноманітні об'єкти. Так, замість зайців ми підставимо вершини трикутника, а замість осередків - півплощині. Оскільки проведена пряма k не перетинає жодну з вершин, то кожна з них знаходиться в тій чи іншій площині. Але оскільки вершини в трикутнику три, а площини у нас всього дві (s1 і s2), то одна з них буде містити дві вершини. Припустимо, що це вершини A і B, і знаходяться вони в півплощині s2 (тобто лежать по одну сторону від k). У такому випадку відрізок АВ не перетинає пряму k. Тобто в трикутнику є сторона, яку пряма k не перетинає.
Альтернативне рішення
У цьому завданню ми припустили, що в одній площині знаходяться точки А і В, проте принцип Дирихле не вказує конкретну клітинку, тому точно так само ми могли вказати, що в одній площині розмістилися вершини С і В, або А і С. Для даної задачі зовсім не важливо, яку сторону трикутника не перетинає пряма k. Тому зазначений принцип ідеально підходить для її вирішення.
Приклад № 2. Геометрія
Завдання
У середині рівностороннього трикутника АВС (у якого АВ = ВС = АС = 1) розмістилося 5 точок. Необхідно довести, що дві з них розташовуються на відстані менше 0,5.
Рішення
Якщо провести в правильному трикутнику АВС середні лінії, вони розділять його на 4 маленьких правильних трикутника зі сторонами frac12- = 0,5. Припустимо, що ці трикутники - осередки, а точки всередині них - кролики. Виходить, у нас є 5 кролів і 4 осередки, отже, в одній з них знаходитиметься як мінімум два кролика. Враховуючи те, що точки не є вершинами (так як вони розташовуються усередині трикутника АВС, а не на одній з його сторін), вони будуть розміщуватися всередині маленьких фігур. Отже, відстань між ними буде менше, ніж 0,5 (оскільки величина відрізка всередині трикутника ніколи не перевищує величини його найбільшою сторони).
Приклад № 3. Комбінаторика
В інших областях також можна вдало застосовувати принцип Діріхле: комбінаторика і математична фізика вже давно спираються на нього при вирішенні завдань.
Завдання
Припустимо, навколо округлено столу стоять на рівній відстані один від одного m прапорців різних країн, а за столом сидять m представників від кожної країни, причому кожен з них розташувався поруч з чужим прапорцем. Потрібно довести, що при певному обертанні столу хоча б двоє з представників виявляться біля своїх прапорців.
Рішення
Виходить, що існує m-1 способів розгорнути стіл так, щоб змінилося взаєморозташування представників і прапорців (якщо виключити початкове розміщення столу), але при цьому залишається m представників.
Застосуємо до вирішення твердження Дирихле і позначимо, що представники виступають кроликами, а певні положення столу при обертанні - осередками. При цьому потрібно провести аналогію між розташуванням представника поруч з відповідному прапорцем і заповненими осередками. Тобто позитивний результат (1 представник розмішається біля свого прапорця) рівносильний результату «кролик виявляється в клітці». Ми розуміємо, що у нас на одну клітинку менше, ніж потрібно (m-1), а значить, в одній з них виявиться як мінімум 2 кролика. При цьому не виключені ситуації, що якась клітина буде порожньою (жоден представник не збігся із прапорцем), а в якійсь клітині виявиться два, три або навіть більше кроликів (два, три і більше представників співпадуть з прапорцями). Таким чином, при одному певному обертанні як мінімум два представники опиняться біля своїх прапорців (як мінімум два кролика потраплять в одну клітинку).
Приступаючи до вирішення такого завдання, важливо розуміти, що початкове положення - це теж осередок, але за умовою завдання вона свідомо пустує, тому ми зменшуємо загальну кількість на 1 (m-1).
Приклад № 4. Теорія чисел
Принцип Діріхле в теорії чисел також має величезне значення.
Завдання
Припустимо, на листочку зошити в клітку учень довільно у вузлах клітинок проставив 5 точок. Необхідно довести, що як мінімум один відрізок з вершинами в цих точках пройде через вузол клітини.
Рішення
Для початку потрібно зобразити на аркуші зошита систему координат, основа якої розташується в одному з вузлів. Осі системи координат будуть збігатися з лініями сітки, а за одиничний відрізок прийнята сторона клітинки. Виходить, що всі 5 відзначених точок будуть знаходитися в системі, а їх координати будуть тільки цілим числом (парних або непарних). Таким чином, ми отримаємо 4 варіанти координат: (четний- парний), (нечетний- парний), (четний- непарний) і (нечетний- непарний). А значить, 2 з 5 точок будуть відповідати одному варіанту. Якщо подивитися на ситуацію з позиції Дирихле, то необхідно позначити точки як зайців, а варіанти координат - як осередки. Ми отримуємо 5 зайців і 4 клітини, відповідно, в одній з них буде мінімум 2 тварин. Припустимо, це точки Р і А, з координатами (x4, y3) І (x5, y6). Середина відрізка, що з'єднує ці дві вершини, матиме координати ((x4+x5) / 2), ((y3+y6) / 2)), які будуть цілими числами в умовах відповідної парності x4 і x5, y3 і y6. Виходить, що середина відрізка розташувалася у вузлі клітини.
Приклад № 5
Досить багато завдань різної складності можна вирішити через принцип Дирихле. Завдання з рішеннями різноманітних математичних та логічних запитань досить часто спираються на цей принцип.
Завдання
На прямій дорозі вириті маленькі поперечні канавки. Відстань між усіма канавками однакове і дорівнює воно o2 м. Необхідно довести, що, незалежно від ширини канавок, людина, що крокує по дорозі з інтервалом 1 м, одного разу потрапить ногою в одну з них.
Рішення
Для того щоб полегшити рішення, необхідно уявити, що дорогу можна «намотати» на окружність довжиною в o2 метрів. Виходить, що всі канавки зіллються в 2 протилежних, а кроки людини будуть відображатися у формі дуги, рівної 1 м. Нам необхідно послідовно відзначити всі кроки, поки один з них не виявиться в дузі, що позначає канавку, незалежно від того, яка буде довжина k дуги (ширина канавки). Звичайно, очевидно, що якби людина крокував на відстань, рівну менше, ніж k, то він рано чи пізно наступив би в канаву. Адже у людини ніяк не вийде переступити відстань k, якщо довжина його кроку менше, ніж k. А значить, нам необхідно знайти два сліди, відстань між якими не перевищуватиме величину k. Для цього доречно буде скористатися принципом Діріхле. Ми подумки поділимо всю окружність на дуги розміром менше k і будемо вважати їх осередками. Припустимо, їх виявиться n штук. Припустимо, що число кроків буде більше ніж число дуг (n + m), хоча ніякі два кроки не збігатимуться з-за ірраціональності числа o2, тоді за принципом Діріхле, принаймні, в одній з комірок розміститься більше одного кроку. А оскільки довжина дуги складає менше k, то і відстань між кроками буде менше. Таким чином, ми виявили необхідні для доказу кроки.
Узагальнення принципу
Матеріали з математики, крім стандартних (простих і не дуже) формулювань, містять також одну узагальнену, яка використовується для виявлення більше двох об'єктів, схожих один на одного. Вона стверджує, що якщо dm + 1 кроликів помістити в d осередків, то як мінімум m + 1 кролик виявиться в одній комірці.
Приклад № 6. Узагальнення
Завдання
Прямокутник з площею 5 х 6 клітин (30 клітин), зафарбованих тільки 19. Чи можна виявити квадрат площею 2 х 2 клітки, в якому мінімум три будуть зафарбовані?
Рішення
Нашу фігуру необхідно розділити на 6 блоків по 5 клітин. Виходячи з твердження Дирихле, в одній з них буде зафарбовано не менше 4 клітинок (19/6 = 4). Тоді в одному з квадратів площею 4 клітинки, розташованому в одному з блоків, буде зафарбовано мінімум 3 клітини.
Приклад № 7
Клас, в якому 25 осіб. З будь-яких випадково вибраних 3 учнів двоє будуть друзями. Необхідно довести, що в класі знаходиться школяр, у якого більше 11 приятелів.
Два вирішення питання
Для початку візьмемо двох школярів, які не дружать один з одним (оскільки якби всі вони дружили між собою, то в кожній трійці було б три одного і кожен учень дружив би з 24 іншими). Решта 23 однокласника будуть дружити з одним з нашої двійки, оскільки в іншому випадку знайшлася б трійка, де немає друзів (а це суперечить споконвічного умовою завдання). Виходить, що один з двох школярів буде дружити як мінімум з 12 учнями. В даному випадку учні - це кролики, а умови "друзі вони чи ні" - це осередки. Ми маємо 23 тварин і лише 2 клітини. Відповідно, в одній з них як мінімум 23/2 = 11,5, т. Е. 12 кроликів. Тобто один з 2 обрані нами учнів буде дружити як мінімум з 12 своїми однокласниками (або навіть більше). Звичайно ж, існують і інші методи розв'язання задачі, проте даний - один з найбільш зрозумілих і зручних.
