asyan.org
добавить свой файл
1
ПРИНЦИП ДІРІХЛЕ


  1. В ящику лежать кулі двох різних кольорів: чорного і білого. Яку найменшу кількість куль требі взяти із ящика, не розглядаючи, так, щоб серед них напевно було дві кульки одного кольору?

Розв'язання

Дістанемо з ящика 3 кулі, оскільки кольорів 2. Тоді, за принципом Діріхле, знайдуться принаймні дві кулі одного кольору. З іншого боку, зрозуміло, що двох куль може й не вистачити.


  1. Дано 12 цілих чисел. Доведіть, що серед них можна вибрати два, різниця яких ділиться на 11.

Розв'язання

При діленні на 11 можна дістати одинадцять різних остач: 0, 1,2, ..., 10. За принципом Діріхле, при діленні дванадцяти чисел на 11 знайдуться принаймні два, які даватимуть однакову остачу. Тоді різниця цих двох чи­сел ділиться на 11 без остачі.
Важливі теоретичні відомості

Узагальнений принцип Діріхле: якщо множина із N елементів розбита на п підмножин, жодні дві з яких не мають спільних елементів, і при цьому N > kn, то знайдеться підмножина, що містить не менше ніж k+1 еле­мент.


  1. У квадраті зі стороною 1 см взяли 51 точку. Доведіть, що деякі три із цих точок можна накрити квадратом зі стороною см.

Розв'язання

Розіб'ємо цей квадрат на 25 менших квадратів зі стороною см.

Оскільки 51 > 25∙2, то в один з цих менших квадратів попаде принаймні три точки.


  1. У клітинках таблиці 3x3 розставлено числа -1; 0; 1. Доведіть, що деякі дві із 8 сум по всіх рядках, всіх стовпцях і двох головних діагоналях будуть рівні.

Розв'язання

Можливо мати лише 7 варіантів сум: -3; -2; -1; 0; 1; 2; 3. Отже, за принципом Діріхле, якийсь варіант має повторитися.


  1. Доведіть, що в будь-якій компанії з 5 осіб є двоє, що мають однако­ве число знайомих у цій компанії.

Розв'язання

Можливі два випадки: коли в компанії є хтось, хто знає чотирьох осіб, і коли в компанії такого немає. В першому випадку в цій компанії немає нікого, хто знав би 0 осіб. Отже, тоді маємо чотири варіанти знайомих: 1; 2; 3; 4. У другому випадку теж маємо чотири варіанти кількості знайомих: 0; 1; 2 і 3. Оскільки 5 > 4, то, за принципом Діріхле, серед п'яти осіб є принаймні дві, які мають однакову кількість знайомих.


  1. Доведіть, що для кожного натурального п існує число вигляду
    11...100..0 (спочатку записані лише одиниці, а далі — тільки нулі), яке
    ділиться на п без остачі.

Розв'язання

Розглянемо n+1 число вигляду 1, 11, 111, ..., 11...1 (останнє записане з допомогою n+1 одиниць). При діленні на п можна мати не більше ніж п
різних остач. А тому, за принципом Діріхле, знайдуться два числа, що да­дуть однакову остачу при діленні на п.

Різниця цих чисел ділиться не п і є числом потрібного вигляду.


  1. Відомо, що для простого числа р > 3, число рk записується 20-ма цифрами. Доведіть, що принаймні три його цифри однакові.

Розв'язання

Жодні три цифри числа рk на будуть однаковими лише тоді, коли кожна цифра буде використана двічі. Але тоді сума його цифр повинна дорівнювати 2(1+2+3+...+9) = 90; тому таке число має ділитися на 3. Але якщо просте число р > 3, то рk не ділиться на 3.


  1. Кожна точка площини пофарбована в один із двох кольорів: чорний чи білий. Доведіть, що існує відрізок довжиною їм, кінці якого мають однаковий колір.

Розв'язання

Розглянемо довільний правильний трикутник зі стороною 1 м. За принципом Діріхле, принаймні дві вершини його будуть одного кольору. Вони і є кінцями шуканого відрізка.


  1. Кожна точка площини пофарбована в один з двох кольорів: чорний чи
    білий. Доведіть, що існує прямокутник, усі вершини якого одного кольору.

Розв'язання

Нехай a, b, c три паралельні прямі, що лежать у даній площині. Прямі d1, d2, ..., d9 — паралельні між собою, що перпендикулярні прямим а, b, с. Позначимо точки перетину кожної прямої d1 з прямими a, b, c відповідно А1, В1, С1. Існує 23 = 8 варіантів розфарбування трьох точок. А оскільки таких трійок маємо 9, то принаймні дві трійки точок пофарбо­вані однаково. Позначимо ці трійки Атт, Ст та Аn, Вп, Сп.

У першій трійці принаймні дві точки мають один колір. Відповідні їм точки другої трійки мають такий самий колір. Отже, маємо чотири точки одного кольору і ці точки є вершинами прямокутника.


  1. Кожна точка площини пофарбована в білий або чорний колір. До­
    ведіть, що на цій площині знайдеться трикутник з кутами 30°, 60°, 90°
    і гіпотенузою 2 см, вершини якого однокольорові.

Розв'язання

Легко довести, що існує відрізок довжиною 2 см, кінці якого одного кольору (задача 8). Позначимо його АВ. Розглянемо правильний шестикутник АМ1М2ВМ3M4.

Якщо якась із вершин М1, М2, М3, М4 має той самий колір, що А й В, то ця вершина разом із А й В є вершинами шуканого трикутника. Якщо ж кожна вершина М1, М2, М3, М4 має інший колір, ніж А й В, то трикутник М1М2М4, задовольняє умову задачі.


  1. У ряд виписані 2n прості числа. Відомо, що серед них не менше
    ніж п різних. Доведіть, що можна вибрати групу із чисел, що стоять поряд, так, щоб їх добуток був повним квадратом.

Розв'язання

Для розв'язання задачі досить довести, що існує така група чисел, що стоять поряд, в якій кожне просте число зустрічається парну кількість разів. Нехай уданій послідовності {a1, а2, ..., } зустрічається т різних простих чисел р1, р2, ..., рт. За умовою т > п. Позначимо Cij степінь числа pi (1 ≤ iт), в якому це число входить у добуток a1a2...aj перших j простих чисел даної послідовності, 1 ≤ j2n. Нехай dij — остача від ділення Cij на 2: Cij = 2lij + dij, dij може набувати значення 0 або 1. Кожен набір вигляду (d1j,d2j, ...,dmj) складається з т нулів і одиниць, усього таких наборів 2n, оскільки 1 ≤ j ≤ 2n. Зазначимо, що всього існує 2т різних наборів (d1, ..., dm ), де . Оскільки 2т < 2n за умовою, то серед побудованих 2n наборів знайдуться два однакові

(d1j, d2j, ..., dmj) = (d1k, d2k, ..., dmk),

для яких 1 j к 2n. Тому dij = dik для всіх 1 ≤ і ≤ т. Звідки маємо, що

Сik Сij = 2(lik lij) + (dik dij) = 2(lik lij)

ділиться на 2 при кожному 1 іт. Зазначимо, що за визначенням Сij число рi зустрічається в добутку рівно Сik – Сij разів. Тому кожне число pj входить у добуток у парному степені, тобто – точний квадрат.


  1. Доведіть, що для будь-якого натурального числа т знайдуться цілі числа а і b такі, що |a| ≤ m, |b| ≤ m та .

Розв'язання

Розглянемо множину чисел .

Усі числа множини S різні (інакше дістанемо, що подається у вигляді відношення цілих чисел), їх кількість (m+1)2. Усі вони лежать на числово­му відрізку і розбивають цей відрізок на (m+1)2 – 1 = т2 +2т час­тин, причому серед цих частин є різні. Тому довжина найменшої з цих частин строго менша, ніж . Нехай цей найменший проміжок утворений числами та , . Тоді



і числа а = а2 a1 ,b = b2 b1 задовольняють умову задачі.
Важливі теоретичні відомості

Часто принцип Діріхле застосовують в якій-небудь геометричній формі, наприклад:

а) якщо відрізок довжиною l розбито на п відрізків, що не мають спільних внутрішніх точок, то довжина найбільшого відрізка не менша від , а довжи­на найменшого відрізка не більша за ;

б) якщо на відрізку довжини l розташовано декілька відрізків, сума довжин яких більша від l, то принаймні два з цих відрізків мають спільну точку;

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



  1. Усередині квадрата зі стороною 1 розташовано декілька кіл, сума довжин яких дорівнює 10. Доведіть, що існує пряма, яка перетинає принаймні чотири із цих кіл.

Розв'язання

Спроектуємо всі кола на одну зі сторін квадрата. Проекцію кола дов­жини l є відрізок довжини . Тому сума довжин проекцій усіх даних кіл дорівнюватиме . Але . Отже, на стороні квадрата знайдеться точ­ка, яка належить принаймні чотирьом проекціям. Тому пряма, що про­ходить через цю точку перпендикулярно до сторони квадрата, перетне принаймні 4 кола.


  1. У квадраті з площею 6 розташовані три прямокутники, кожний із
    площею 3. Доведіть, що площа спільної частини принаймні двох із прямо­кутників не менша від 1.

Розв'язання

Нехай S12, S13, S23 відповідно площі спільних частин першого і друго­го, першого і третього та другого і третього прямокутників. Тоді разом ці прямокутники покривають площу, не меншу за 3 ∙ 3 – (S12 + S13 + S23), де 3∙3=9 — сума площ даних прямокутників (величину S12 + S13 + S23 слід відняти, щоб не враховувати двічі площі спільних частин). Оскільки всі три прямокутники помістились у квадраті з площею 6, то 9 – ( S12 + S13 + S23) ≤ 6.

Тому S12 + S13 + S233. А отже, принаймні одне з чисел S12, S13, S23 не мен­ше ніж 1.


  1. Доведіть, що в кожному дев'ятикутнику існує пара діагоналей, кут між якими менше ніж 7°.

Розв'язання

Усього в дев'ятикутнику (9∙6):2=27 діагоналей, оскільки з кожної вершини виходить по 6 діагоналей. Проведемо через довільну точку О площини 27 прямих, паралельних діагоналям дев'ятикутника. Ці прямі роз­бивають повний кут у 360° на 54 частини. Якщо серед 54 таких кутів немає кута, меншого за 7°, то сума всіх кутів є більшою, ніж 7°∙54 = 368° > 360°. Тому існує кут, менший за 7°. Оскільки при паралельному перенесенні прямих кут між ними не змінюється, то твердження задачі доведено.


  1. На аркуші паперу знаходиться клякса невизначеної форми із пло­щею, меншою за 1 см2. Доведіть, що на кожному аркуші можна побудува­ти систему координат із одиницею в 1 см так, що жодна точка з обома
    цілочисловими координатами не лежатиме на кляксі.

Розв'язання

Розглянемо спочатку довільну систему координат із одиницею 1 см. Кожній точці М клякси із координатами (х; у) поставимо у відповідність точку Р із координатами ({х}; {у}), де {х} = х – [х] — дробова частина чис­ла х. Зрозуміло, що всі точки Р опиняться в одиничному квадраті, причо­му площа фігури, складеної з точок Р, не перевищить площі клякси, складеної з точок М. Отже, всередині цього одиничного квадрата знай­деться точка, яка не співпадає з точкою Р. Виберемо її за початок нової системи координат з осями, паралельними осям попередньої системи. Очевидно, що побудована таким чином система координат буде шуканою.


  1. Доведіть, що останні цифри членів послідовності Фібоначчі, почи­наючи з певного місця, періодично повторюються. (Послідовністю Фібо­наччі називається послідовність натуральних чисел (un), така, що u1 = и2 = 1, а для будь-якого п > 2 un = un-2 + un-1).

Розв'язання

Позначимо через ап останню цифру числа ип й розглянемо послі­довність пар (a1; а2), (a2; a3). (a3; a4), … . Оскільки число пар нескінчен­не, а число різних пар не більше ніж 102, то знайдуться такі k і р, що аk = ар, аk+1 = ар+1. Оскільки значення аk+2 повністю визначається зна­ченнями аk та аk+1, для будь-якого ik маємо: аi = аi+p+k.


  1. Доведіть, що в послідовності Фібоначчі є число, яке ділиться на 2004.

Розв'язання

Позначимо через ап остачу від ділення ип на 2004. Розглянемо послідов­ність пар остачі (а1; а2), 2; а3), 3; а4), … . Кількість таких різних пар дорівнює 20042, а загальна кількість пар нескінченна. Тому в цій послідовності знайдуться дві однакові пари. Тобто для деяких k i р (k<р) будуть мати місце рівності аk = ар, аk+1 = ар+1. Тому аk-1 = ар-1, ак-2 = ар-2, ..., а2 = ар-к+2, а1 = ар-к+1 Оскільки аk = ап = 1, то up-k+2 та u p-k+1 при діленні на 2004 дають однакові остачі. Тому число ир-k = ир-k+2 ир-k+1 ділиться на 2004.


  1. У правильному 9-кутнику одні вершини пофарбовані білим, а ін­ші — чорним кольором. Доведіть, що існують два рівні трикутники (з вершинами, що є вершинами даного 9-кутника), вершини кожного з яких за­фарбовані в один колір.

Розв'язання

Із 9 вершин, зафарбованих у два кольори, принаймні п'ять мають од­наковий колір. Можна вважати, що цей колір – білий. П'ять білих вершин утворюють одноколірних (білих) трикутників. Зауважимо, що поворот на кут , k = 0, 1,..., 8 відносно центра О даного 9-кутника не міняє множини М вершин цього 9-кутника. Тому після повороту кожного із 10 білих трикутників на кут , 0 < k < 8 відносно О ми дістанемо 10 ∙ 9 = 90 трикутників з вершинами у множині М. Усі вони не можуть бути різними, оскільки загальна кількість різних трикутників з вершинами у множині М дорівнює . Отже, знайдуться два білі трикутники ∆1 і 2, які після декількох поворотів суміщаються з одним і тим самим трикутни­ком ∆. Зауважимо, що трикутники ∆1 і ∆2 рівні, але різні. Дійсно, два одна­кові трикутники не можна дістати різними поворотами (які ми використову­вали) із одного і того ж трикутника. Оскільки кожен трикутник ∆1 і ∆2 суміщається після повороту самого з трикутником ∆, то і ∆2 можна дістати із ∆1 за допомогою деякого повороту. Отже, трикутники ∆1 і ∆2 — шукані.
Задачі для самостійного розв'язування

  1. Доведіть, що серед будь-яких трьох цілих чисел можна знайти два,
    сума яких ділиться на 2.

  2. Доведіть, що серед будь-яких 10 цілих чисел можна вибрати одне
    чи декілька, сума яких ділиться на 10.

  3. 10 школярів на олімпіаді розв'язали 35 задач, причому відомо, що
    серед них є школярі, які розв'язали рівно одну задачу, школярі, які
    розв'язали рівно дві задачі, і школярі, які розв'язали рівно три задачі. До­
    ведіть, що є школяр, який розв'язав не менше ніж п'ять задач.

  4. Усередині правильного шестикутника зі стороною 3 см довільно
    розміщено 55 точок, жодні три з яких не лежать на одній прямій. Доведіть,
    що серед них знайдуться три точки, що утворюють трикутник, площа яко­го не перевищує см2.

  5. У класі 25 учнів. Серед будь-яких трьох із них двоє дружать між со­бою. Доведіть, що є учень, у якого не менше ніж 12 друзів.

  6. На площині дано шість точок, жодні три з них не лежать на одній
    прямій. Будь-які дві точки з'єднано відрізком, кожен відрізок пофарбовано або в червоний, або в синій колір. Доведіть, що знайдеться трикутник з вершинами в даних точках, усі сторони якого мають один колір.

  7. Площина розфарбована в 100 кольорів. Доведіть, що знайдеться
    прямокутник з вершинами одного кольору.

  8. Із аркуша клітчатого паперу розміром 29x29 вирізали 99 квадра­
    тиків, кожен з яких складається із чотирьох клітинок. Доведіть, що можна
    вирізати ще один такий самий квадратик.

  9. Комісія з 60 осіб провела 40 засідань, причому на кожному були
    присутні рівно 10 членів комісії. Доведіть, що якісь два члени комісії
    зустрічались на засіданнях хоча б двічі.

  10. На числовій прямій взято інтервал довжиною, меншою від (n
    натуральне). Доведіть, що в цьому інтервалі міститься не більше ніж нескоротних дробів вигляду , де р та q — цілі числа, 1 ≤ q ≤ п.

  11. З натуральним числом к проводиться така операція: спочатку його
    розкладають на прості множники k = р1, р2, ... , рп (не обов'язково всі різні), а потім знаходять суму р1 + р2 + ...+ рп + 1. Із здобутим числом прово­дять таку саму операцію і т. д. Доведіть, що здобута числова послідовність з якогось моменту буде періодичною.

  12. Під кожним членом послідовності Фібоначчі напишемо три ос­танні його цифри (якщо цих цифр менше ніж три, число доповнюється зліва нулями): 001, 001, 002, 003, 005, 008, 013, 021, 034, ... Доведіть, що здобута послідовність періодична.

  13. У колі з радіусом 1 проведено декілька хорд так, що кожен діаметр
    перетинає не більше ніж чотири із них. Доведіть, що сума довжин хорд не
    перевищує 13.

  14. На відрізку довжиною 10 декілька менших відрізків, що не перетинаються, пофарбовані в червоний колір, причому жодні дві червоні точки не знаходяться на відстані 1. Доведіть, що сума довжин зафарбованих
    відрізків не перевищує 5.

  15. У колі з радіусом 1 проведено кілька хорд, сумарна довжина яких більша за 7π. Доведіть, що знайдеться діаметр, який перетинає не менше
    ніж вісім хорд.

  16. Усередині круга з радіусом 16 розміщено 650 точок. Доведіть, що знайдеться кільце шириною 1 і внутрішнім радіусом 2, яке містить не менше ніж 10 з цих точок.