Олімпіадні завдання з математики на тему - Принцип Діріхле
Олімпіадні завдання з математики на тему "Принцип Діріхле". Рішення.
У лісі росте мільйон ялинок. Відомо, що на кожній з них не більше 600 000 голок. Доведіть, що у лісі знайдуться дві ялинки з однаковим числом голок.
Перед нами мільйон «кроликів»-ялинок і, на жаль, всього лише 600001 клітинка з номерами від 0 до 600000. Кожен «кролик»-ялинка садиться нами в клітинку з номером, що дорівнює кількості голок на цій ялинці. Так як "кроликів" набагато більше, ніж клітин, то в якійсь клітці сидить принаймні два "кролики" - якби в кожній сиділо не більше одного, то всього "кроликів"-ялинок було б не більше 600001 штук. Але якщо два «кролика»-ялинки сидять в одній клітці, то кількість голок у них однакова.
Дано 12 цілих чисел. Доведіть, що з них можна вибрати два, різницю яких ділиться на 11.
Залишки за модулем 11 - "клітини", числа - "кролики".
У місті Ленінграді мешкає понад 5 мільйонів людей. Доведіть, що у якихось двох із них однакова кількість волосся на голові, якщо відомо, що у будь-якої людини на голові менше мільйона волосся.
Побудуйте мільйон клітин із номерами від 0 до 999999 і розсадіть там людей, помістивши кожного ленінградця в клітину, номер якої дорівнює кількості волосся на його голові.
До магазину привезли 25 ящиків із трьома різними сортами яблук (у кожному ящику яблука лише одного сорту). Доведіть, що серед них є принаймні 9 ящиків із яблуками одного й того самого сорту.
25 ящиків-«кроликів» розсадимо по 3 клітинам-сортам. Так як 25 = 3 • 8 + 1, то застосуємо «узагальнений принцип Діріхле» для N = 3, k = 8 і отримаємо, що в якійсь клітині-сорті не менше 9 ящиків.
У країні Курляндії m футбольних команд (по 11 футболістів у кожній). Усі футболісти зібралися в аеропорту для поїздки до іншої країнина відповідальний матч. Літак зробив 10 рейсів, перевозячи щоразу по m пасажирів. Ще один футболіст прилетів до місця майбутнього матчу на гелікоптері. Доведіть, що хоча б одну команду повністю доставили в іншу країну.
Так як перевезено всього 10m + 1 футболістів, то, розсадивши їх по клітинах-командах, отримуємо, що в якійсь клітці сидить 11 футболістів.
Дано 8 різних натуральних чисел, не більших за 15. Доведіть, що серед їх позитивних попарних різниць є три однакові.
Різних різниць може бути 14 - від 1 до 14 - це ті 14 клітин, в які садитимемо кроликів. Хто буде нашими кроликами? Ними, звісно, мають бути різниці між парами даних нам натуральних чисел. Однак є 28 пар і їх можна розсадити по 14 клітин так, що в кожній клітці буде сидіти рівно два «кролика» (і значить, у кожній менше трьох). Тут треба використовувати додаткове міркування: у клітці з номером 14 може сидіти не більше одного кролика, адже число 14 можна записати як різницю двох натуральних чисел, що не перевищують 15, лише одним способом: 14 = 15 – 1. Значить, у 13 клітинах, що залишилися, сидять щонайменше 27 кроликів, і застосування узагальненого принципу Диріхле дає нам бажаний результат.
Доведіть, що в будь-якій компанії з 5 осіб є двоє, які мають однакову кількість знайомих у цій компанії.
Варіантів числа знайомих всього 5: від 0 до 4. Залишилося зауважити, що якщо у когось 4 знайомих, то ні в кого не може бути 0 знайомих.
Декілька футбольних команд проводять турнір в одне коло. Доведіть, що у будь-який момент турніру знайдуться дві команди, які до цього моменту зіграли однакову кількість матчів.
Нехай команд n. Тоді варіантів числа команд, із якими зіграла дана команда n: від 0 до n – 1. Залишилосяпомітити, що й одна команда зіграла з усіма n – 1-ї, то жодна інша команда не могла ні з ким не зіграти.
а) Яке найбільше полів на дошці 8 ? 8 можна зафарбувати в чорний колір так, щоб у будь-якому куточку виду з трьох полів було принаймні одне незафарбоване поле?
б) Яка найменша кількість полів на дошці 8? 8 можна зафарбувати в чорний колір так, щоб у кожному куточку виду було принаймні одне чорне поле?
а) Розбийте дошку на 16 квадратиків 2? 2 – це клітини; кроликами, звісно, будуть чорні поля.
10 школярів на олімпіаді вирішили 35 завдань, причому відомо, що серед них є школярі, які вирішили одно завдання, школярі, які вирішили рівно два завдання і школярі, що вирішили рівно три завдання. Доведіть, що є школяр, який вирішив щонайменше п'ять завдань.
З умов випливає, що знайдуться 7 школярів, які вирішили 35 – 6 = 29 завдань. Оскільки 29 = 4 • 7 + 1, то знайдеться школяр, який вирішив щонайменше п'ять завдань.
Яке найбільше королів можна поставити на шахівниці так, щоб жодні два з них не били один одного?
Відповідь: 16 королів. Розіб'ємо дошку на 16 квадратиків, у кожному може бути не більше одного короля.
Доведіть, що рівносторонній трикутник не можна покрити двома меншими рівносторонніми трикутниками.
Кожен із менших трикутників не може накривати більше однієї вершини великого трикутника.
У квадрат із стороною 1 метр кинули 51 крапку. Доведіть, що якісь три з них можна накрити квадратом зі стороною 20 см.
Розіб'ємо наш квадрат на 25 квадратів зі стороною 20 см. За узагальненим принципом Діріхле, в одній із них потрапить принаймні три точки з 51 кинутої.
П'ятеро молодих робітників отримали на всіх зарплату – 1500 рублів. Кожен з ниххоче купити собі магнітофон ціною 320 карбованців. Доведіть, що комусь із них доведеться почекати із покупкою до наступної зарплати.
Якби кожен із робітників міг купити магнітофон, то у них у сумі було б не менше 5 • 320 = 1600 рублів.
У бригаді 7 осіб та їх сумарний вік – 332 роки. Доведіть, що з них можна вибрати трьох осіб, сума віку яких не менше 142 років.
Пофарбуємо всю суходіл у синій колір, а всі крапки, діаметрально протилежні суші – у червоний. Тоді обов'язково є точка, яка пофарбована в обидва кольори. У ній і треба рити тунель.
Доведіть, що серед ступенів двійки є дві, різниця яких ділиться на 1987 рік.
Розгляньте 1988 ступенів та їх залишки за модулем 1987 року.
Доведіть, що з 52 цілих чисел завжди знайдуться два, різниця квадратів яких поділяється на 100.
Квадрати при розподілі на 100 можуть давати лише 51 залишок, тому що залишки x і 100 - x при зведенні в квадрат дають один і той же залишок.
Доведіть, що серед чисел, що записуються лише одиницями, є число, яке ділиться на 1987 рік.
Розглянемо 1988 чисел-«кроликів» 1, 11, 111, …, 111 … 11 (1988 одиниць) і посадимо їх у 1987 клітин з номерами 0, 1, 2, …, 1986 – кожне число потрапляє в клітинку з номером, рівним залишку від розподілу цього числа на 1987. Тоді (за принципом Діріхле) знайдуться два числа, які мають однакові залишки при розподілі на 1987. Нехай це числа 11...11(m одиниць) та 11...11(n одиниць), причому m> n. Але їхня різниця, яка ділиться на 1987, дорівнює 11...1100...00 (m – n одиниць та n нулів). Скоротимо всі нулі – адже вони не мають жодного відношення до подільності на 1987 рік – і отримаємо число з одних одиниць, яке ділиться на 1987 рік.
Доведіть, що є ступінь трійки, що закінчується на 001.
Якщо 3m і 3n - ступеня трійки, що дають один і той же залишок при розподілі на 1000, то 3m - 3n = 3n (3m - n - 1) ділиться на 1000 (ми вважаємо для визначеності, що m).
У клітинах таблиці 3? 3 розставлені числа - 1, 0, 1. Доведіть, що якісь дві з 8 сум по всіх рядках, всім стовпцям і двом головним діагоналям будуть рівні.
Ці суми можуть набувати лише 7 різних значень: від – 3 до 3.
Сто чоловік сидять за круглим столом, причому понад половина з них – чоловіки. Доведіть, що якісь два чоловіки сидять один навпроти одного.
Розіб'ємо всіх людей на 50 пар так, що в кожній парі – дві людини, які сидять один навпроти одного. Зрозуміло, що в одній із цих пар-«клітин» обидві людини – чоловіки.
15 хлопчиків зібрали 100 горіхів. Доведіть, що якісь два з них зібрали однакову кількість горіхів.
Якщо це не так, то очевидно, що хлопчики зібрали не менше, ніж 0 + 1 + 2 + … + 14 = 105 горіхів – протиріччя.
Цифри 1, 2, …, 9 розбили на три групи. Доведіть, що добуток чисел в одній із груп не менший за 72.
Добуток чисел у всіх групах дорівнює 9! = 362880, а 71? = 357911.
У таблиці 10? 10 розставлені цілі числа, причому будь-які два числа в сусідніх клітинах відрізняються не більше ніж на 5. Доведіть, що серед цих чисел є два рівні.
Оскільки від будь-якої клітини до будь-якої іншої можна дістатися, не більше 19 разів зрушивши в сусідню клітину, то всі числа знаходяться між числами a і a + 95, де a мінімальне з усіх розставлених чисел. Отже, серед цих чисел трохи більше 96 різних.
Доведіть, що з-поміж будь-яких 6 людина є або троє попарно знайомих, або троє попарно незнайомих.
У даної людини серед решти п'яти є або не менше трьох знайомих, або не менше трьох незнайомихйому. Розберемо, наприклад, перший випадок. Серед цих трьох людей є або двоє знайомих - тоді вони разом з обраною нами вихідно людиною утворюють потрібну трійку, або всі троє попарно незнайомі.
На картатій площині дано 5 довільних вузлів сітки. Доведіть, що середина одного з відрізків, які з'єднують якісь дві з цих точок, також є вузлом сітки.
Розгляньте координати цих точок та їх залишки при розподілі на 2.
На складі є по 200 чобіт 41, 42 та 43 розмірів, причому серед цих 600 чобіт 300 лівих та 300 правих. Доведіть, що з них можна скласти щонайменше 100 придатних пар взуття.
У кожному розмірі якихось чобіт менше: правих чи лівих. Випишемо ці типи чобіт за розмірами. Якийсь тип, наприклад, лівий, повториться принаймні двічі, наприклад, 41 і 42 розмірах. Але оскільки кількість лівих чобіт у цих розмірах сумарно не менше 100 (чому?), ми маємо не менше 100 придатних пар взуття в цих розмірах.
В алфавіті мови племені Ні-Бум-Бум 22 приголосних і 11 голосних, причому словом у цій мові називається довільне буквосполучення, в якому немає двох приголосних поспіль і жодна буква не використана двічі. Алфавіт розбили на 6 непорожніх груп. Доведіть, що з усіх літер однієї групи можна скласти слово.
Доведіть, що в одній із груп різниця між числом приголосних та кількістю голосних не більше 1.
Доведіть, що з-поміж будь-яких 10 цілих чисел знайдеться кілька, сума яких ділиться на 10.
Розгляньте 10 сум: x1, x1 + x2, …, x1 + x2 + … + x10 та його залишки при розподілі на 10.
Дано 11 різних натуральних чисел, не більших за 20. Доведіть, що з них можна вибрати два числа, одне з яких ділиться на інше.
Розбийте числа від 1 до 20 на 10 наборів, у кожному з яких будь-якийпарі чисел одне ділиться інше: 11, 13, 15, 17, 19, 1,2,4,8,16, 3,6,12, 5,10,20, 7,14, 9,18.