Принцип Діріхле в задачах

 

Зауваження 2. У випадку > 0 для довільною > 0 існує одна, а значить і безліч пар натуральних чисел х та у, для яких

 

Задача 19. Довести, що існує натуральний степінь числа 5, десятковий запис якого розпочинається групою цифр 1997.

Розв'язання. Нам подібно довести існуваня таких натуральних чисел n та , для яких

1997·

 

Тобто

 

Оскільки  -додатне ірраціональне число, то, покладаючи 1997 = а, 1998=b, одержуємо, що для доведення правильності твердження задачі 19 нам потрібно показати, що існує пара натуральних чисел n та , для яких

а < п

тобто

 

Існування такої пари натуральних  чисел п та випливає з теореми Кронекера ( точніше, із зауваження до цієї теореми).

Задача 20. В рядок записано 5 натуральних чисел. Довести, що одне з них або сума декількох чисел, записаних поруч, ділиться на 5.

Розв'язання. Розглянемо допоміжні числа .

Якщо одне з цих чисел  ділиться на 5 то твердження задачі доведено. В протилежному випадку деякі два з цих чисел дають однакові остачі при діленні на 5, а тому їх різниця ділиться на 5. Але ця різниця співпадав з сумою декількох (можливо одного) вихідних чисел, записаних поруч.

Зауваження. Аналог твердження задачі 1  є правильним для довільного натурального п .

Задача 21. Довести, що для кожного натурального числа п знайдеться натуральне число, яке записується лише за допомогою цифр 1 та 0 і ділиться на п.

Розв’язання. Розглянемо наступне п+1 число: 1,11,111,…,11…1. Різниця деяких з них ділиться на п. але ця різниця має вигляд: 111…100…0.

Задача 22. Нехай натуральне число п взаємно просте з 10. Довести, що існує число виду 111…11, яке ділиться на п.

Розв’язання. В попередній задачі було показано, що існує число виду 111…11·, яке ділиться на п.

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

Розв’язання. Будемо поміщати наші числа в наступні 6 ящиків. В перший ящик помістимо ті числа, які діляться на 11, в другий – ті, які при діленні на 11 дають в остачі 1 або 10, в третій – 2 або 9, в четвертий 3 або 8, в п’ятий – 4 або 7, в шостий – 5 або 6. За принципом Діріхле деякі два з 11 чисел попадуть в один ящик. Тоді ці числа або мають однакові остачі при діленні на 11 або сума їхніх остач дорівнює 11. Тому різниця або сума цих чисел, а значить і різниця їхніх квадратів ділиться на 11.

Задача 24. Довести, що існує степінь числа 7, який закінчується цифрами 0001.

Розв’язання. Твердження задачі рівносильне тому, що при деякому натуральному п число

 Розглянемо числа

.

У нас є натуральне число, тому різниця деяких двох цих чисел ділиться на . Значить існують натуральні числа

 

 

 

 Оскільки – взаємо прості, то

,

 що й треба було показати.

Задача 25. Довести, що три останні цифри послідовних степенів числа 12 починаючи з деякого номера утворюють періодичну послідовність.

Розв'язання. Зауважимо, що число, утворене трьома останніми цифрами довільного числа співпадає з остачею від ділення цього числа на 1000. Розглянемо 1001 число виду

12,12²,12³,..., 12¹⁰⁰¹.

Серед них є 2, які при  діленні на 1000 мають однакові остачі,

тобто три останні цифри  деяких чисел виду 12 та . співпадають. Зрозуміло, що починаючи з -го номера наша послідовність є періодичною з періодом j-i

Задача 26. Натуральні числа а та т взаємно прості. Довести, що знайдеться натуральне число k таке, що число kа при діленні на т дає в остачі 1.

Розв'язання. Твердження задачі рівносильне тому, що для деякого натурального kчисло (ka- 1) ділиться на т. Розглянемо числа

 а, а²,..., а^m+1.

Різниця деяких двох з них  ділиться на m, тобто число

 ділиться на m, причому і <j. Оскільки та т взаємно прості, то

.

Тому твердження задачі є  правильним з 

Задача 27. Послідовність (а_п) чисел

1,1,2,3,5,8,13,21,...,

в якій кожне число, починаючи з третього, дорівнює сумі двох попередніх, називається послідовністю  Фiбоначчі. Довести, що

а)Послідовність останніх трьох цифр для чисел Фібоначчі є періодичною; . '

б)Деякий член послідовності Фібоначчі закінчується цифрами 999.

Розв'язання а) При діленні на 1000 кожен член послідовності Фібоначчі може мати одну з наступних остач:

0,1,...,999.

Тому сусідні члени  послідовності Фібоначчі можуть мати 1000² різних пар остач від ділення їх на 1000. Тому серед пар чисел Фібоначчі виду:

є дві, які мають однакові пари остач при діленні на 1000. Нехай це будуть пари .

 З означення послідовності  Фібоначчі випливає, що остачі  двох сусідніх членів послідовності  однозначно визначають остачі  попереднього та наступного членів. Тому послідовність останніх трьох цифр чисел Фібоначчі періодичною з періодом

б) Позначимо (див. розв'язання а). Введемо в розгляд послідовність () остач членів послідовності (а_п) при діленні на 1000. За доведеним в а) при довільному натуральному п, тому = 1,

оскільки  = 1. Тоді з рівності

 

одержуємо, що 1000, тобто = 0. Далі з рівності 

 випливає, що 

= 1,

а з рівності

 

одержуємо, що = 999, тобто три останні цифри числа мають вигляд 999.

Задача 28. Нехай р - просте число, яке більше за 5. а) Довести, що існує натуральне число k, для якого число kр закінчується заданою цифрою с.

б) Довести, що для  заданого натурального числа b існус натуральне число k, для якого число kр+b ділиться на 10 .

Розв'язання. а) Числа

р,2р, Зр,..., 10p

при діленні на 10 мають  різні остачі. Дійсно, в протилежному випадку різниця деяких двох з  цих чисел, тобто число виду тр, де m =, ділилося б на 10, що неможливо. Тому останні цифри чисел

р, 2р, 3р,..., 10р

- різні, тобто пробігають  множину

{0,1,...,9}.

Отже, число k знайдеться навіть серед чисел

1,2,... ,10.

б) Нехай  - остання цифра числа b. Якщо = 0, то твердження очевидне. Якщо ж > 0, то для доведення б) досить використати твердження

а) з с = 10 -

Задача 29. Нехай р - просте число, яке більше за 3, і при деякому натуральному п число р^п є 100-цифровим,. Довести, що одна з цифр числа р^п зустрічається принаймні 11 раз.

Розв'язання. Якби твердження задачі не виконувалося б, то кожна з десяти цифр зустрічалася б в десятковому записі числа р^п рівно 10 разів. Тоді сума цифр числа р^п дорівнювала б

10 • (0 + 1 + 2 + ... + 9) = 450,

а тому число р^п ділилося б на 9, а отже р не було б простим.

Задача 30. Довести, що а) з 64, б) з 17 цілих чисел можна вибрати 9 чисел сума яких ділиться на 9

Розв'язання. а) Згідно узагальненого принципу Діріхле серед даних 64 цілих чисел

 

існують принаймні 8, які  мають одну і ту ж остачу r при діленні на 9. Не порушуючи загальності вважатимемо, що це числа

.

Розглянемо допоміжні  числа

(7)

Кожне з перших восьми цих  чисел ділиться на 9. З дев'яти  чисел

 

можна вибрати одне або  декілька так, щоб їхня сума ділилася на 9. Нехай цих чисел буде і штук, де

1 і 9.

Тоді приєднуючи до цих  чисел 9- чисел множини (7), одержимо деякі дев'ять чисел з (7), сума яких ділиться на 9. Додаючи до кожного з одержаних чисел по r дістанемо 9 чисел з вихідної сукупності, сума яких ділиться на 9.

б) Аналогічно до розв'язання а) можна показати, що з довільних  п'яти цілих чисел можна вибрати  три, сума яких ділиться на 3 (це твердження також можна легко довести методом перебору). Тоді з даних 17 цілих чисел

 

можна вибрати 5 трійок чисел  так, що сума чисел кожної а них  ділиться на 3. Нехай це будуть трійки

 

{,а₂, а₃}, {а₄, а₅,а₆},…,

Розглянемо допоміжні 5 чисел

 

які за доведеним будуть цілими. З цих чисел можна вибрати 3. Сума яких ділиться на 3, сума яких ділиться на 3. Сума їхніх чисельників мі є  шуканою сумою вихідних чисел.

Задача 31. Нехай х₁,х₂,.., та – дві перестановки натуральних чисел від 1 до 100. Довести, що серед кожної сукупності чисел

а)

б)

існують два числа, різниця яких ділиться на 100

Розв'язання. а) Допустило, що всі 100 чисел сукупності а) дають різні остачі при діленні на 100. Тоді множина остач цих чисел співпадає з множиною чисел Нехай S-це сума всіх чисел сукупності а). Тоді

S = +0+1+2+.. .+99 = 100(+49)+50,

 де - натуральне  число. З іншого боку

 

.

Отримали протиріччя, бо 

100(

б) Доведення проведемо  також від супротивного. Нехай  всі числа сукупності б) дають  різні остачі на 100. Тоді серед цих остач буде 50 парних і 50 непарних, а отже і серед чисел сукупності б) буде 50 парних і 50 непарних. Але 50 непарних чисел в сукупності б отримуються лише в тому випадку, коли 50 непарних чисел першої перестановки множаться на 50 непарних чисел другої перестановки. Тому парні числа множини б) одержуються в результаті множення парних чисел наших перестановок. Але добуток парних чисел не може мати остачу 2 при діленні на 100.

Зауваження. Задачу б) можна  було б розв'язувати аналогічно до а). Допустивши протилежне ми б отримали б рівність

(100l)² = (

- цілі невід'ємні  числа які не перевищують 100.

Залишається зауважити, що (100!)²⁵⁴⁸, а права частина останньої рівності не ділиться на 5⁴⁸.

Задача 32. Довести, що для довільного k-значного числа а знайдеться число, яке ділиться на 2001 іk останніх цифр якого утворюють число а.

Розв'язання. Розглянемо послідовність чисел    10...01,10...010...01,10...010...010...010...01,... (кількість нулів між кожними сусідніми одиницями дорівнює k-1). За принципом Діріхле у цій послідовності (навіть серед перших її 2002 членів) знайдуться два члени, які дають однакові остачі при діленні на 2001, а тому їхня різниця ділиться на 2001. Різницю між двома членами даної послідовності можна записати у вигляді

10...010...010 ..010...01 •  10ⁿ.

 Оскільки числа 2001 і 10 є взаємно простими,, то  число

b= 10...010...010...010...01

ділиться на 2001. Значить  число аb є шуканим, оскільки воно ділиться на 2001 і одержується, якщо декілька разів підряд записати число .

Зауваження. З розв'язання цієї задачі випливає, що якщо число N є взаємно простим з 10, і - довільне натуральне число, то знайдеться число, яке одержується, якщо декілька разів підряд записати число а, і яке ділиться на N.

Задача 33. Довести, що для довільного непарного числа т знайдеться число, яке складається лише з непарних цифр і яке ділиться на т 

Розв'язання . Розглянемо два випадки

а) Нехай число т є взаємно простим з 10. Тоді за твердженням задачі 3 існує натуральне число, які десяткові цифри якого є одиницями і яке ділиться на m. Це число з одиниць і буде шуканим.

б) Якщо т не є взаємно простим з 10, то його остання цифра дорівнює 5 (бо т- непарне). Запишем число т у вигляді

т =b·5^k,

де k та b - натуральні, причому b є взаємно-простим з 5.

Знайдемо число, десятковий запис якого складається лише з непарних цифр і яке ділиться на , а потім побудуємо число, яке ділитьсіна 5^k  і на b і складається лише з непарних цифр.

Розглянемо число 5.^k Його остання цифра 5, а передостання - 2. Тому останні дві цифри числа

- непарні і воно ділиться на 5^k. Подовжуючи цей процес ми врешті-решт отримаємо число виду ,

останні k цифр якого є непарними. Розглянемо k- цифрове число а, складене з цих k цифр в тому ж порядку. Воно є різницею двох чисел, які діляться на 5^k , а тому є шуканим. Отже, число -значним числом, яке ділиться на 5^k, і всі його цифри є непарними. Скориставшись зауваженням до попередньої задачі для N =b, одержуємо шукане число, яке одержується, якщо декілька разів підряд записати число . 

Задача 34. Нехай різні прості числа і М - це множина всіх тих натуральних чисел, всі прості дільники яких містяться серед чисел Довести, що з довільного (n+1)-го елемента множини М можна вибрати декілька чисел ( можливо лише одне) так,щоб добуток вибраних чисел був точним квадратом.

Розв'язання. Розглянемо всеможливі не порожні підмножини вибраної (п+ 1) - елементної множини

А={ }

 і для кожної з  цих підмножин знайдемо добуток її елементів. В нас утвориться множина В, яка складається з (2ⁿ⁺¹ -1)-го натурального числа, кожне з яких подається у вигляді

                (8)

де ,і -= 1,2, - деякі цілі невід'ємні числа. Нам потрібно довести, що серед елементів множини В існує такий, для якого всі показники його зображення у вигляді (8) є парними числами.

Співставимо кожному числу b з В, яке подається у вигляді (8), впорядкований набір з п нулів та одиниць за наступним правилом:

b—> (),      (9)

де  - це остача від ділення числа на 2,

 . Оскільки всеможливих впорядкованих наборів з п нулів або одиниць є 2ⁿ, а чисел в множині B - (2ⁿ⁺¹ ), то деяким двом різним числам b' та b" з В співставлятимуться однакові набори. Тому добуток b' b" є точним квадратом. Нехай

 

де  деякі різні підмножини множини  . Покладемо

 

(у випадку Iберемо b=1). Тоді число

 

є шуканим, бо воно є точним квадратом і подається у вигляді  добутку різних чисел з множини А.

Зауваження. Ця нескладна задача допускає також інші розв'язання (наприклад, за допомогою методу математичної індукції).

Задача 35. Довести, що для довільного натурального п, п 2, існує натуральне число r таке, що для всіх цілих х та у число х^п + у^п -r не ділиться на n².

Розв'язання. Скористаємося наступним допоміжним твердженням.

Лема. Якщо х та у - цілі і

(- у), то (

Доведення леми. Оскільки

(х — у)п, то х =

 - ціле.

Тому

 

 

 

Оскільки число в дужках є цілим, то

(хⁿ - ),

і лема доведена.

З цієї леми випливає, що якщо х і у - цілі числа, які при діленні на п, дають остачі