Принцип Діріхле.
Формулювання: Якщо в n "клітинах" сидять не менше n + 1 "кроликів", то в якийсь із "клітин" сидять не менше 2-х "кроликів".
Доказ: Протиріччя до формулювання звучить так: "в кожній клітині сидить не більше одного кролика". Але тоді кроликів, очевидно, не більше, ніж клітин ?! Тому є клітина, де кроликів не менше двох ч.т.д.(!)
Принцип Діріхле і різні його посилення - чи не найчастіша ідея в олімпіадних задачах, тому на нього варто звернути особливу увагу.
1. Якщо в n клітинах сидять не більше n-1 кроликів, тобто порожня клітка.Також доводиться від протилежного (як і всі наступні пункти): якщо порожньої клітки немає, то в кожній клітині сидить хоча б 1 кролик. Тоді кроликів не менше, ніж клітин ?! Значить, порожня клітка є, ч.т.д.
2. Якщо в n клітинах сидять рівно n кроликів, то або в кожній клітині сидить рівно один кролик, або є й порожня клітка, і клітка, в якій не менше 2-х кроликів.Дійсно, якщо не в кожній клітині сидить рівно 1 кролик, то або (а) є порожня клітка, або (б) є клітка, в якій не менше 2-х кроликів. У випадку (а) у нас n кроликів виявляються розсаджених в n-1 клітин, тому, за принципом Діріхле, є і клітка, в якій не менше 2-х кроликів ч.т.д. У випадку (б) у нас не більше n-2 залишилися кроликів виявляються розсаджених в n-1 клітин, отже, по п.1, є і порожня клітка ч.т.д.(!) П.2 дуже корисний у тих випадках, коли ми знаємо, що рівно по одному кролику в кожній клітині сидіти не може.
3. Якщо в n клітинах сидять не менше n * (k-1) +1 кроликів, то в якийсь із клітин сидять не менше k кроликів.Дійсно, якщо в кожній клітині сидить не більше k-1 кролика, то у всіх клітинах сидить не більше n * (k-1) кроликів, а їх хоча б на 1 більше ?! ч.т.д.
4. Якщо в n клітинах сидять не більше n * (k + 1) -1 кроликів, то в якийсь із клітин сидять не більше k кроликів.Дійсно, якщо в кожній клітині сидить не менш k + 1 кролика, то у всіх клітинах сидить не менш n * (k + 1) кроликів, а їх хоча б на 1 менше ?! ч.т.д.
5. (Це твердження узагальнює принцип Діріхле на випадок нецілого числа кроликів.) Якщо сума n чисел дорівнює S, то серед них є число, що не меншу S / n, і число, не більше S / n.Дійсно, якщо всі числа (строго!) Менше S / n, то їх сума менше S, а якщо всі числа (строго!) Більше S / n, то їх сума більше S. В обох випадках отримуємо протиріччя ч.т.д.(!) На принцип Діріхле при вирішенні завдань на олімпіаді можна прямо посилатися, на узагальнення і посилення - не рекомендується. Легше підставити в потрібне місце рішеннядоказ відповідного затвердження. Слова "принцип Діріхле" в такому випадку можна взагалі не згадувати ;-)
Приклади:
Завдання 1. У мішку лежать кульки 2-х різних кольорів (багато білих і багато чорних). Яку найменшу кількість кульок треба на дотик вийняти з мішка, щоб серед них свідомо опинилися двоє одного кольору.
Рішення: 3 кульки. Це - просто застосування принципу Діріхле: кроликами будуть взяті кульки, а клітинами - чорний і білий кольори. Клітин зо два, тому якщо кроликів хоча б три, то якісь два потраплять в одну клітку (буде 2 одноколірних кульки). З іншого боку, взяти дві кульки мало, тому що вони можуть бути двох різних кольорів.
Завдання 2. Дано 233 цілих числа. Довести, що різниця якихось двох з них ділиться на 232. (Принцип Діріхле часто використовується і в задачах з теорії чисел!)
Рішення: У нас є 233 числа, які ми, швидше за все, зробимо кроликами. Знайдемо відповідні клітини: їх повинно бути не більше 232, і різниця 2-х чисел, "сидять в одній клітці" повинна ділиться на 232. Залишки від ділення на 232 якраз підходять. Застосовуємо принцип Діріхле для 233 кроликів-чисел і 232 клітин-залишків і отримуємо необхідну. (В теоретико-числових завданнях на Діріхле найчастіше клітинами бувають залишки від ділення чого-небудь на якесь число!)
Завдання 3. У магазин привезли 25 ящиків яблук 3-х сортів (у кожному ящику всі яблука одного сорту). Довести, що серед них є, принаймні, 9 ящиків з яблуками одного сорту.
Рішення: Візьмемо ящики в якості кроликів і сорти в якості клітин. Тоді нам в точності підходить твердження п.3 при n = 3, k = 9.
Завдання 4. П'ятеро програмістів отримали на всіх зарплату - 1750 доларів. Кожен з них хоче купити собі новий комп'ютер за 360 доларів. Доведіть, що комусь із них це не світить.
Рішення: Скористаємося затвердженням п.5 для n = 5, S = 1750. Тоді зрозуміло, що зарплата одного з програмістів не більше S / n = 350 доларів. Йому і не світить покупка.
Дуже часто в задачі на принцип Діріхле потрібні різні додаткові міркування (або він взагалі з'являється, як проміжне міркування)
Приклади:
Завдання 1. На олімпіаді 10 школярів вирішили в сумі 35 завдань, причому серед них були вирішили рівно одну, рівно дві і рівно три завдання. Довести, що хтось із них вирішив не менш 5 завдань.
Рішення: (Стандартне міркування: якщо відомо, що якісь об'єкти є, то є хоча б по одному примірнику, який можна виділити і розглянути!) Візьмемо одного школяра, який вирішив рівно одну задачу, одного, який вирішив рівно дві і одного, який вирішив рівно зо три. Ці троє вирішили в сумі 6 завдань. Залишається ще 7 школярів, які вирішили в сумі 29 завдань. Якщо взяти завдання в якості кроликів і школярів в якості клітин, то виходить в точності твердження п.3 при n = 7, k = 5 ч.т.д.
Завдання 2. Доведіть, що рівностронній трикутник не можна покрити двома меншими рівносторонніми трикутниками. (Так, принцип Діріхле іноді використовується і в геометрії!)
Рішення: Головне міркування: менший рівносторонній трикутник, як його не клади, не зможе покрити 2 вершини більшого. Тому, взявши вершини в якості клітин і маленькі трикутники в якості кроликів, ми отримаємо, що кроликів менше, ніж клітин (затвердження п.1!), Звідки випливає, що є порожня клітка. Це означає, що якусь із вершин великого трикутника ми ніколи не накриємо, тому й не накриємо його цілком ч.т.д.
Завдання 3. На планеті в зіркою системі Тау Кіта суша займає більше половини площі. Довести, що таукітяне зможуть прорити прямий тунель через центр планети так, щоб він з'єднував сушу із сушею .
Рішення: (Так, це завдання в деякому сенсі теж на принцип Діріхле!) Візьмемо на планеті безліч точок суші і безліч точок, діаметрально протилежних суші. Сума площ цих множин - подвійна площа суші, що строго більше площі планети. Тоді ці 2 безлічі перекриються. У точці перекриття і можна буде почати рити тунель.
"Рішення" №2: (прояснює зв'язок з принципом Діріхле) Будемо вважати кроликами точки суші, а клітинами - пари діаметрально протилежних точок планети. "Кількість" кроликів в даному випадку - це площа суші, а "кількість" клітин - половина площі планети. Оскільки площа суші більше половини площі планети, то "кроликів більше, ніж клітин". Тоді є клітка, в якій сидить не менше двох кроликів, тобто пара протилежних точок, обидві з яких - суша. Ці точки і треба з'єднати тунелем.
Завдання 4. За круглим столом сидять 100 чоловік, причому більше половини з них - лицарі. Довести, що якісь два лицаря сидять навпроти один одного
Рішення: (Ця задача має підкреслене схожість з попередньої). Будемо вважати кроликами лицарів, а клітинами - пари діаметрально протилежних місць за столом. Клітин тоді рівно половина від кількості місць за столом (тобто 50), а кроликів - строго більше. Тоді є клітка, в якій сидить не менше двох кроликів, тобто пара протилежних місць, за якими сидять два лицаря. Вони і є шукані.(!) Абсолютно необхідно зрозуміти, чому "рішення" №2 передостанній задачі не є коректним рішенням.
Принцип Діріхле формулювався і доводилася нами тільки для кінцевого числа клітин і кроликів. Тут же ми має справу з нескінченним числом точок, а порівняння нескінченно великих величин, у загальному випадку - окрема глибока теорія (зокрема, до неї ставиться знаменита континуум-гіпотеза). Однак саме для випадку покриттів геометричних фігур вірний принцип Діріхле, сформульований в термінах площі так, як зазначено нижче.Переформулювання принципу Діріхле для площ і покриттів фігур:
0. Якщо фігура площі S покрита декількома фігурами з сумою площ (строго!) Більше S, то у неї є точка, покрита не менше 2-х разів (саме їм ми і користувалися, вирішуючи останню задачу 3).
1. Якщо фігура площі S покрита декількома фігурами з сумою площ (строго!) МеньшеS, то у неї є точка, ні покрита жодного разу
.2. Якщо фігура площі S покрита декількома фігурами з сумою площ рівно S, то або кожна точка покрита рівно один раз, або є і точка, не покрита ні разу, і крапка, покрита не менше 2-х разів.
3. Якщо фігура площею S покрита декількома фігурами з сумою площ (строго!) Більше (k-1) * S, то у неї є точка, покрита не менше k разів.
4. Якщо фігура площі S покрита декількома фігурами з сумою площ (строго!) Менше (k + 1) * S, то у неї є точка, покрита не більше k разів.
(!) Зверніть увагу, що ці твердження є прямою аналогією тверджень з тим же номером, узагальнюючих простий принцип Діріхле. Строгих доказів цих тверджень ми не наводимо, тим більше що в умовах олімпіади набагато легше і краще посилатися на них, як на очевидні, ніж намагатися згадати і записати доказ ;-)
Принцип Діріхле
У найпростішому вигляді його виражають так: «Якщо десять кроликів сидять в дев'яти ящиках, то в деякому ящику сидять не менше двох кроликів».
Загальна формулювання: «Якщо n кроликів сидять у k ящиках, то знайдеться ящик, в якому сидять не менше ніж n / k кроликів, і знайдеться ящик, в якому сидять не більше ніж n / k кроликів». Нехай вас не бентежить дробове число кроликів - якщо вийде, що в скриньці не менше 7/3 кроликів, значить, їх не менше трьох.
Доказ принципу Діріхле просте, але заслуговує на увагу, оскільки схожі міркування часто зустрічаються.
Припустимо, що в кожному ящику сидять менше ніж n / k кроликів. Тоді у всіх ящиках разом кроликів менше ніж n / k * k = n. Протиріччя.
Формулювання принципу Діріхле здається очевидною, однак складність полягає в тому, що в задачах не вказано ні кролики, чи не ящики.
Знаючи принцип Діріхле, можна здогадатися, в яких випадках його застосовувати. Наприклад, якщо кожному елементу множини А відповідає рівно один елемент множини В, то елементи А можна назвати кроликами, а елементи В - ящиками.
Принцип Діріхле буває безперервним: «Якщо n кроликів з'їли m кг трави, то якийсь кролик з'їдено було не менше m / n кг і якийсь з'їдено було не більше m / n кг» (а якщо хтось з'їв більше середнього, то хто -то з'їв менше середнього).
Зауважимо, що в останній формулюванні кролики відіграють роль ящиків для трави, а трава - роль кроликів, що сидять в ящиках.
Приклад 1. У школі 400 учнів. Доведіть, що хоча б двоє з них народилися в один день року.
Розв'язання. Всього в році 365 днів. Назвемо дні ящиками, а учнів кроликами. Тоді в деякому ящику сидять не менше 400/366 кроликів, тобто більше одного. Отже, не менше двох.
Можна міркувати від протилежного. Припустимо, що кожен день відзначають день народження не більше одного учня, тоді всього учнів не більше 366. Протиріччя.
Приклад 2. Кіт Базиліо пообіцяв Буратіно відкрити велику таємницю, якщо він складе чудесний квадрат 6 х 6 з чисел +1, -1, 0 так, щоб всі суми по рядках, по стовпцях і по великих діагоналях були різні. Допоможіть Буратіно.
Розв'язання. Припустимо, що квадрат складений. Тоді суми чисел можуть мінятися від -6 до +6. Всього 13 значень. Рядків у квадраті 6, стовпців 6, діагоналей 2. Отримуємо 14 різних сум. Протиріччя, значить, скласти такий квадрат неможливо.
Приклад 3. На планеті Земля океан займає більше половини площі поверхні. Доведіть, що у світовому океані можна вказати дві діаметрально протилежні точки.
Розв'язання. Відобразимо океан симетрично щодо центру Землі. Оскільки сума площ океану і його образу перевищує площу земної поверхні, то існує точка, що належить океану і його образу. Візьмемо цю точку разом з протилежного до неї.
Приклад 4. На співбесіду прийшли 65 школярів. Їм запропонували 3 контрольних роботи. За кожну контрольну ставилася одна з оцінок: 2,3,4 або 5. Чи вірно, що знайдуться два школярі, які отримали однакові оцінки на контрольних?
Розв'язання. Розглянемо безліч наборів з трьох оцінок за відповідні контрольні. Кількість таких наборів одно 43 або 64 (4 можливості за кожну з трьох контрольних). Оскільки число учнів більше 64, за принципом Діріхле якимось двом учням відповідає один набір оцінок.