Dirichle Printsipi Quyidagi vazifani ko'rib chiqing. Vazifa 1

Dirichle Printsipi
Quyidagi vazifani ko'rib chiqing.
Vazifa 1.Ignabargli o'rmonda 800000 archa o'sadi. Har bir qoraqarag'ada-500000 ignadan ortiq emas. Bir xil miqdordagi igna bilan kamida ikkita qoraqarag'ay borligini isbotlang.
Qaror.Aytaylik, aksincha, bu o'rmonda bir xil miqdordagi ignalar bo'lgan ikkita archa yo'q deb taxmin qiling. Keyin bitta igna bilan bitta qoraqarag'ay (bitta qoraqarag'ay yoki bitta) yo'q. Xuddi shunday, 499999 ignalari bilan bir nechta qoraqarag'ay, 500000 ignalari bilan bir nechta qoraqarag'ay yo'q. Shunday qilib, 500000 dan ortiq archa 1 dan 500000 gacha ignalar soniga ega. Hammasi bo'lib 800000 archa o'sadi va har bir archa 500000 ignadan ortiq emas, shuning uchun kamida ikkita archa bir xil miqdordagi igna bilan topiladi.
Izoh.Eritma aslida 800000 (archa soni) va 500000 (ignalarning eng ko'p soni) aniq raqamlariga bog'liq emasligini payqash oson. 800000 raqami 500000 dan qat'iy ravishda katta bo'lganligi asosan ishlatilgan. Dalil, bu holda vazifa va dalillar adolatli bo'lsa-da, ignalarsiz bitta ovqat yo'q deb taxmin qilingan.
Endi Dirichle tamoyilini shakllantiramiz.
K elementlari n qutilarga joylashtirilsin. Agar ob'ektlar soni qutilar sonidan ko'p bo'lsa (k > n), unda kamida bitta quti bor, unda 2 ta element bo'ladi.
Eslatma:E'tibor bering, qaysi qutida kamida ikkita element mavjudligi muhim emas. Bundan tashqari, ushbu qutidagi qancha narsalar va qancha bunday qutilar muhim emas. Eng muhimi shundaki, kamida ikkita element (ikki yoki undan ortiq) bo'lgan kamida bitta quti mavjud.
Adabiyotda bu tamoyil "quyonlar va hujayralar printsipi", "qutilar va narsalar printsipi"nomlari ostida ham uchraydi.
1-vazifaga qaytish. Ushbu muammoni Dirichle tamoyilidan foydalanib hal qilamiz. Mos ravishda 1,2,3 raqamlangan 500000 quti bo'lsin...,500000. Biz bu qutilarga (aqliy) 800000 archa qo'yamiz: s raqami bo'lgan qutida bizsaniq igna bo'lgan qoraqarag'aylarni joylashtiramizs. Yog', ya'ni "narsalar" qutilarga qaraganda ko'proq bo'lganligi sababli, kamida bitta qutida kamida ikkita element, ya'ni kamida ikkita archa bo'lishi kerak. Xuddi shu qutida bir xil miqdordagi ignalar bo'lgan archa bor ekan, biz bir xil miqdordagi ignalar bilan kamida ikkita archa bor degan xulosaga keldik.
Albatta, biz ko'rib turganimizdek, 1-vazifa aniq va Dirichle printsipining yordamisiz osongina hal qilinishi mumkin. Shuning uchun, albatta, savol tug'iladi: "Dirichle printsipi nima uchun kerak?"Kelajakda biz ba'zi vazifalar to'g'ridan-to'g'ri hal qilishda unchalik aniq emasligini ko'ramiz, ammo shu bilan birga Dirichle printsipi yordamida hal qilinadi. Yechimning soddaligi ko'p jihatdan "qutilar" va "narsalar"qanchalik muvaffaqiyatli tanlanishiga bog'liq. Ya'ni, Dirichle printsipidan foydalanganda (kim) "quti" va nima (kim) "mavzu"ekanligini ko'rsatish kerak.
Kelajakda materialni birlashtirish uchun biz bir qator muammolarni hal qilamiz.