РОЗВЯЗУВАННЯ ЗАДАЧ ЗА ДОПОМОГОЮ ПРИНЦИПУ ДІРІХЛЕ

Скачати 96.41 Kb.

Назва	РОЗВЯЗУВАННЯ ЗАДАЧ ЗА ДОПОМОГОЮ ПРИНЦИПУ ДІРІХЛЕ
Дата	22.12.2013
Розмір	96.41 Kb.
Тип	Документи

bibl.com.ua > Математика > Документи

РОЗВЯЗУВАННЯ ЗАДАЧ ЗА ДОПОМОГОЮ ПРИНЦИПУ ДІРІХЛЕ

Жук І.В., старший викладач

кафедри методики викладання

базових дисциплін ІППОЧО

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

Вивчаючи матеріал з теми рекомендується не протягом кількох занять, а починаючи з 6-7 класів і до одинадцятого по мірі вивчення програмового матеріалу, враховуючи психологічний та розумовий розвитком самої дитини.

В чому ж полягає принцип Діріхле? Для учнів 6-7 класів зручніше всього подавати його в жартівливій формі: «Якщо в N клітках сидить не менше N+1 кролика, то існує хоча б одна клітка, де сидить не менше, ніж 2 кролика.»

Слід звернути увагу учнів на слова "не менше", "хоча б", оскільки саме ці фрази дозволяють по-перше, розпізнати задачі на принцип Діріхле, а по-друге, тільки використовуючи такі формулювання можна розв'язувати ці задачі. Як же довести цей принцип? Доведення базується на методі доведення від супротивного.

Припустимо, що у кожній клітці сидить не більше одного (тобто один або жодного) кролика. Тоді в усіх клітках сидить не більше N кроликів. А це суперечить умові, оскільки кроликів є N+1. Отже, наше припущення було хибним, тобто знайдеться хоча б одна клітка, в якій сидить не менше 2 кроликів.

Але клітки і кролики є не в кожній задачі. Тому самим першим кроком при розв'язуванні задач є визначення того, кого прийняти за «клітки», а кого за «кроликів».

Розглянемо кілька найбільш простих прикладів:

Приклад 1. В класі навчається 35 учнів. Доведіть , що серед них є принаймні 2, у яких день народження одного числа (можливо, в різні місяці).

Доведення. Тут „клітки" - дні місяця, а „кролики" -учні. Оскільки треба довести, що є принаймні 2 таких учні, то припускаємо, що таких учнів є не більше одного. Тоді за 31 день місяця може відсвяткувати свій день народження не більше 31 учня. Але це суперечить умові (учнів 35). Отже, наше припущення невірне. Тому є в класі хоча б 2 таких учні, у яких день народження одного числа.

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

Розв’язання. Кульки - „кролики", кольори - „клітки". І за принципом Діріхле „кроликів" мало би бути хоча б на 1 більше, тому логічно припустити, що кульок мало би бути 3. Доведемо це. Припустимо, що кульок слід дістати не більше, ніж дві. Тоді одна може бути чорна, а одна біла, що не задовольняє умову. Якщо ж кульок три, то для 2-х кольорів є З кульки. Отже, за законом Діріхле знайдеться хоча б 2 кульки одного кольору.

Приклад 3: В місті Санкт-Петербург живе три мільйони людей. Доведіть, що у яких-небудь двох із них однакова кількість волосин на голові.

Розв’язання. Очевидно, що «кролики» - це жителі Санкт-Петербурга, «клітки»- кількість волосин на голові. Але перше запитання тут: скільки є "кліток"? Їх буде 2 000 001, оскільки люди можуть бути як з волоссям на голові, так і лисі. І знову доведення від супротивного: Припустимо, що є не більше однієї людини з певною кількістю волосся на голові. Тоді всього в місті живе не більше 2 000 001 людини, що суперечить умові. Отже, наше припущення невірне. Отже, у Санкт-Петербурзі є щонайменше двоє людей з однаковою кількістю волосин на голові.

Приклад 4: В магазин привезли 25 ящиків яблук з трьома різними сортами

яблук - в кожному ящику по окремому сорту яблук. Довести, що серед них

знаходится принаймні 9 ящиків яблук одного сорту.
Доведення: «Клітки» — сорти яблук; «кролики»" — ящики.

Припустимо, що кожного сорту не більше 8 ящиків. Тоді 8*3=24, а ящиків 25.

Отже, наше припущення хибне. Тому є принаймні 9 ящиків яблук одного

сорту.

Слід пам'ятати, що на принцип Діріхле не слід проводити ціле заняття, оскільки дітям важко протягом 1,5 — 2 годин опрацьовувати нестандартні міркування. Краще всього розбити заняття на декілька частин — задачі на різну тематику. При розборі задач слід підбирати по кілька однотипних задач, щоб учні мали змогу самостійно повторити подібні міркування, адаптуватися до них. І, звичайно, поряд з вивченням нових тем обов'язкової програми слід використовувати їх у задачах на принцип Діріхле.

Після опрацювання найпростіших міркувань переходимо до другого етапу: відокремлення деяких даних. Якщо в умові задачі поряд з основною умовою йдеться про відокремлені дані, то їх спочатку відділяють в розв'язанні і лише потім використовують принцип Діріхле.

Приклад 5. В класінавчається 30 учнів. В диктанті 1 учень зробив 13 помилок, а інші — менше. Довести, що є принаймні 3 учні, що зробили однакову кількість помилок.

Доведення : 1 учень відділений в умові, тоді учнів 30—1 = 29. Помилок може бути від 0 до 12, тобто їх кількість — 13. Припустимо, що не більше 2-х учнів зробили однакову кількість помилок, тоді всього в класі (13*2=26) — не більше 26 учнів, а це суперечить умові, адже їх 29. Отже, наше припущення хибне, і в класі є хоча б 3 учні, що зробили однакову кількість помилок.

Приклад 6: 10 школярів на олімпіаді розв'язали 35 задач, причому серед них є такі, що розв'язали рівно одну, рівно дві, рівно три задачі. Довести, що є

учень, який розв'язав не менше 5 задач.
Доведення: Якщо розв'язувати задачу напряму, то матимемо: Припустимо, що всі діти розв'язали не більше, ніж по 4 задачі, тоді розв’язаних задач

, що задовольняє умову.

Але можна відокремити трьох учнів: одного — з однією задачею, одного — з двома, одного — з трьома задачами. Тоді відокремимо відповідно і 1+2+3=6 задач.

Маємо: 10—3=7учнів, 35—6=29 задач.

Припустимо, що кожен з 7 учнів розв'язав не більше 4 задач, тоді всього

розв'язано не більше 28 задач. А це суперечить умові. Тому є хоча б один учень, що розв'язав хоча б 5 задач.

Крім відокремлювання змінних зустрічаються ще і задачі, які потребують додаткових міркувань. Їх можна запропонувати на наступному етапі вивчення теми.

Приклад 7: У країні Курляндії М футбольних команд по 11 чоловік в кожній. Всі футболісти зібрались у аеропорту для поїздки в іншу країну на відповідальний матч. Літак зробив 10 рейсів у іншу країну, перевозячи при цьому по М футболістів кожного рейсу. Ще один футболіст добрався сам. Доведіть, що хочаб 1 команда зібралась у повному складі у іншій країні.

Доведення:

I спосіб. Нехай жодна із команд не зібралась повним складом у іншій країні.
Літак перевіз 10М пасажирів, а ще один добрався сам, тому всього переїхало
(10М+1) футболістів. Всього ж їх було 11М. Згідно з нашим припущенням,
принаймні по одному гравцю кожної команди залишилось у аеропорту, тобто
їх залишилось не менше М гравців. Але було 11М гравців, і прилетіло (10М+1)
гравців, тобто залишилось 11М-10М-1=М-1 футболістів. Отже, наше
припущення хибне. Тому хоча б 1 команда зібралась повним складом у іншій
країні.

Слід звернути увагу, що учні могли б піти іншим шляхом міркувань. В такому випадку не слід їх зупиняти, а розібрати обидва способи розв'язання цієї задачі.

II спосіб: Нехай в країні призначення не зібралось жодної команди у повному складі. Тоді кожної команди приїхало не більше 10 чоловік, а всього приїхало не більше 10М чоловік, що суперечить умові і літак привіз 10М чоловік і 1 добрався сам. Тобто всього добралося (10М+1) чоловік. Отже, наше припущення невірне, тому хоча б одна команда зібралась повним складом у
іншій країні.

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

Доведення: Звернемо увагу учнів на те, що як тільки мова заходить про кратність, слід проаналізувати питання про остачі від ділення в даному

випадку на 11.

Таких остач може бути 11: 0, 1, 2, 3, ..., 10.

В якому ж випадку різниця кратна 11? Коли остача r=0. А це можливо лише

тоді, коли зменшуване і від'ємник при діленні на 11 мають однакову остачу.

Тобто задача звелася до того, щоб довести, що у двох із 12 цілих чисел є однакова остача при діленні на 11. За принципом Діріхле (для учнів це вже стає

очевидним) дійсно, з 12 цілих чисел знайдеться хоча б 2 таких, що остачі r за модулем 11 будуть рівні. Тоді різниця цих чисел при діленні на 11 дасть остачу

0 за модулем 11, що і означає кратність 11.
Приклад 9: Дано 8 різних натуральних чисел, кожне з яких не перевищує 15.

Довести, що серед попарних різниць різних чисел є 3 однакові.
Доведення: Різниця двох таких попарно різних чисел може дорівнювати будь-якому числу від 1 до 14. А кількість таких пар чисел дорівнює

. Тоді можна взяти „ кроликів" як пари чисел і розташувати їх по 2 в кожну „клітку"- результат різниці. І умова задачі не виконується. Але можна

також ще помітити, що любе число від 1 до 13 може бути поданим у вигляді

кількох різниць, а 14- ні :

1=2-3=4-3=... 2=5-3=6-4=... 13=15-2=14-1 14=15-1.

Тоді матимемо 13 „кліток" і 27 „кроликів" і згідно принципа Діріхле дійсно,

серед попарних різниць різних чисел є хоча б 3 однакових.
Приклад 10: Довести, що серед будь-яких чотирьох попарно різних чисел з інтервалу (0;) можна вибрати 2 таких числа х та у, щоб виконувалась нерівність: .

Доведення: Здійснимо з даним виразом деякі перетворення:

4(соs (х-у)+соs(у+х)) соs(х-у)+1>4 соs²х+4сos²у

4(соs² (х-у)+ соs (х+у) соs(х-у))+1>4 соs² х+4 соs²y

4соs²(х-у)+2(2соs²х-1+2 соs²у-1)+1>4 соs²х+4 соs²у

4 соs²(х-у)+4соs² х+4соs²у - 3>4соs²х+4соs²у

соs²(х-у)>

.

Оскільки х і у - числа з інтервалу (0;

), то соs (х-у) >

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

: ( 0;

] ; (

;

] ; (

;

]. Згідно принципу Діріхле хоча б в один з цих інтервалів попадає два із чотирьох заданих нам чисел. Їх різниця буде за модулем менша ніж

. Візьмемо ці числа як х та у. Тоді

| х+ у| <

.

Згідно властивостей косинуса cos>

,

cos>

, що і треба було довести.

Приклад 11. Чи можна на семи 3-тонних машинах вивезти з каменоломні 50

каменів масою 370кг, 372 кг, 374 кг, , 468 кг?

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

₅₀=

=20950 кг. А на семи 3-тонних машинах можна перевезти 21000кг. І відповідь до задачі: так.

Але діти забувають про те, що камені – цілі. І їх не дозволяється розбивати. Подивимось на цю задачу з іншого боку. Всього 7 машин і 50 каменів. За принципом Діріхле принаймні на одній машині мало би бути не менше 8 каменів. Але маса навіть 8-ми найлегших каменів складає 3016 кг > 3 тонн, тому жодна машина не зможе їх вивезти одразу. Тому відповідь до задачі: ні.

Принцип Діріхле часто використовується і в задачах із клітчастою дошкою.

Приклад 12: В кожній клітинці клітчастої дошки 7*7 сидить коник. Всі вони за командою перескакують на сусідню клітинку, але не по діагоналі. Довести, що після виконання цієї команди знайдеться клітинка, в якій сидить 2, або більше коників.

Доведення : Дуже часто в задачах з клітчастою дошкою застосовують метод розфарбовування в декілька кольорів. Розфарбуємо нашу дошку за принциом шахової. Тоді кожний коник сидить на білій або чорній клітинці. Причому чорних клітинок буде 25, а білих 24(або навпаки, що не є суттєвим). За командою коник, що був на чорній клітинці переходить на білу і навпаки. Отже, з 25 чорних клітинок 25 коників перестрибують на 24 білих клітинки. Тому за принципом Діріхле обов'язково знайдеться клітинка, на якій буде сидіти принаймні 2 коника.

Також принцип Діріхле використовується і в геометрії. Наведемо ще кілька прикладів геометричних задач.

Приклад 13: Вся площина розмальована в 2 кольори. Довести, що знайдеться дві точки одного кольору, які знаходяться на відстані 1 метра одна від одної. Доведення : Кольорів 2, тоді інтуїтивно відчувається, що точок слід брати не 1, а більше, тобто три (И кліток; (М+1)кроликів). Візьмемо три точки площини, які розташовані на відстані 1 метра одна від одної. Такі точки вибрати можливо, оскільки існує рівносторонній трикутник із стороною 1 метр. А точками будуть вершини цього трикутника. Тоді за принципом Діріхле серед трьох точок знайдеться хоча б дві однакового кольору. Що і треба було довести.

Приклад 14. В квадрат 1*1 кинули 51 точку. Довести, що хоча б три з них можна накрити кругом радіуса .

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

2*? =50 (найбільше парне число, яке не перевищує 51). Тоді розбиваємо на 25 квадратів весь квадрат, тобто кожну сторону на 5 відрізків довжиною 1/5 кожний.

Тоді припустимо, що в такий квадрат попаде не більше двох точок, що суперечить умові, тобто буде існувати квадратик, в який попаде не менше 3-х точок. Але ж нам слід помістити ці точки в круг радіуса 1/7, а не в квадрат зі стороною 1/5. Тоді перевіримо, чи поміститься цей квадрат в круг. Для цього діагональ квадрата d має не перевищувати діаметр круга D. Порівняємо їх :

та

.

Оскільки дані величини є додатними, то вони порівнюються так само, як і їх квадрати. Тоді

порівняємо з

.

Очевидно, що

. Отже, квадрат вміщається в круг. Задачу доведено.

Схожі:

ГУРТКИ, ФАКУЛЬТАТИВИ Застосування принципу Діріхле до різних задач... Німецький математик XIX століття Лежен Діріхле у своїх наукових дослідженнях часто користувався міркуваннями, які пізніше дістали...	Урок №9 Тема. Розв'язування задач за допомогою рівнянь Мета: розширити знання про види задач, що розв'язуються складанням рівнянь, розширити спектр умінь щодо складання математичної моделі...
МЕТОДИКА РЕАЛІЗАЦІЇ ДИДАКТИЧНОГО ПРИНЦИПУ СВІДОМОСТІ І ТВОРЧОЇ АКТИВНОСТІ...	С. В. Бутківська, Н. А. Мисліцька Анотація. В статті розглянуті окремі шляхи реалізації принципу історизму під час вивчення фізики, а саме наведені приклади задач...
Тема. Дослідження тиристорів за допомогою програмного комплексу Electronics Workbench Мета роботи: вивчення принципу дії та властивостей, дослідження характеристик, ознайомлення з основними параметрами та використанням...	Тема: Розв’язування задач за допомогою рівнянь Мета: Розширити знання учнів про практичне застосування рівнянь, зокрема до розв’язання задач. Вдосконалити навики встановлення залежностей...
Тема. Дослідження підсилювальних каскадів за допомогою програмного... Мета роботи: вивчення принципу дії та властивостей, дослідження характеристик підсилювальних каскадів	Урок №80 Тема. Розв'язування задач за допомогою систем лінійних рівнянь Мета: відпрацювати навички застосування схеми розв'язання текстових задач на складання системи лінійних рівнянь із двома змінними...
Тема. Дослідження біполярних транзисторів за допомогою програмного... Мета роботи: вивчення принципу дії та властивостей, дослідження характеристик, ознайомлення з основними параметрами та використанням...	Тема. Дослідження польових транзисторів за допомогою програмного комплексу Electronics Workbench Мета роботи: вивчення принципу дії та властивостей, дослідження характеристик, ознайомлення з основними параметрами та використанням...

Додайте кнопку на своєму сайті:
Портал навчання