Dirichlė principas ir skaičiavimo argumentai

Keturios kojinės, trys spalvos: kas būtinai pasikartos?

Stalčiuje yra lygiai trijų galimų spalvų kojinių. Nežiūrėdami paimate keturias kojines; tarkime, kad jų yra bent keturios. Kiekviena kojinė yra vienos spalvos. Ar visos keturios galėtų būti skirtingų spalvų? Pirmosios trys galėtų būti visų trijų spalvų, tačiau ketvirtoji negali būti ketvirtos spalvos. Bent dvi iš keturių kojinių yra tos pačios spalvos, nors dar negalite pasakyti, kokia tai spalva ar kurios tai kojinės.

Objektai yra atskiros kojinės, o ne spalvos. Trys kategorijos yra spalvų žymos. Net dvi vienodai atrodančios kojinės yra skirtingi objektai, kai skaičiuojama, kiek jų paimta. Diagramoje skaičiai žymi kojines, o langeliai – jų kategorijas; pavaizduotas išdėstymas yra tik vienas pavyzdys, o ne prognozė, kokios kojinės iš tikrųjų bus paimtos.

Naudinga iš anksto mokėti dalyti sveikuosius skaičius su liekana, lyginti nelygybes, suprasti funkcijas su nurodytomis pradine ir galutine aibėmis ir samprotauti remiantis bendra taisykle. Pamokos, į kurias pateiktos nuorodos, jau paskelbtos. Visi čia reikalingi atvaizdžių ir skaičiavimo apibrėžimai pateikti vietoje; vėlesnės pamokos apie aibes ir įrodymus yra papildoma medžiaga, o ne būtinos išankstinės žinios.

Skaitydami pirmą kartą, sekite kojinių pavyzdį, įrodymą, kuriame kiekvienas objektas priskiriamas tik vienai kategorijai, ribą su viršutine sveikąja dalimi ir talpos pavyzdžius. Tada pasirinkite taikymą dalybos liekanoms arba kvadrato diagramą. Prie įrodymo su apatine sveikąja dalimi ir bendrosios erdvinės nelygybės grįžkite tada, kai galėsite paaiškinti, kodėl kiekvienas objektas priklauso lygiai vienai kategorijai. Pasirinkimų medis trumpai primena, kaip tiksliai suskaičiuoti kategorijas.

Kiekvienas objektas patenka į lygiai vieną kategoriją

Tegu A yra baigtinė n skirtingų objektų aibė, o B – baigtinė m kategorijų aibė. Čia n yra neneigiamas sveikasis skaičius, o m – teigiamas sveikasis skaičius. Žymėjimas |A| = n nurodo aibės A elementų skaičių. Funkcija f: A → B kiekvienam aibės A objektui priskiria lygiai vieną aibės B kategoriją. Kategorijos gali būti tuščios; objektas negali likti nepriskirtas jokiai kategorijai ar būti suskaičiuotas dviejose kategorijose.

Tegu aᵢ yra i-ajai kategorijai priskirtų objektų skaičius. Šie skaičiai yra neneigiami sveikieji skaičiai, o a₁+⋯+aₘ = n. Ši suma susieja priskyrimą su išvada. Jei prieš priskyrimą kategorijos persidengia, pirmiausia nustatykite taisyklę, pagal kurią kiekvienas objektas priklausytų tik vienai kategorijai; kitaip skaičiuojant objektus atskirose kategorijose tas pats objektas gali būti suskaičiuotas kelis kartus.

Dirichlė principas baigtinėms aibėms teigia: jei n > m, tai bent vienoje kategorijoje yra bent du objektai. Tarkime priešingai, kad kiekvienoje kategorijoje yra ne daugiau kaip vienas objektas. Sudėję visų m kategorijų objektų skaičius gautume n ≤ m, o tai prieštarauja sąlygai n > m. Taigi egzistuoja skirtingi objektai x ir y, kuriems f(x) = f(y). Tai vadinama kolizija; objektai išlieka skirtingi, nors priklauso tai pačiai kategorijai.

Sąlygoje nelygybė yra griežta. Kai n = m, kiekvienoje kategorijoje gali būti po vieną objektą. Kolizija taip pat galima, kaip rodo objektų skaičiai (2, 0, 1), kai n = m = 3. Kai n < m, kolizija vis tiek gali įvykti, tačiau vien objektų ir kategorijų skaičiai jos negarantuoja. Teorema pateikia pakankamą sąlygą, o ne būtiną ir pakankamą sąlygą kolizijai įvykti.

Skirtingoms išvestims reikia pakankamai kategorijų

Funkcija yra injektyvi, kai skirtingus argumentus visada atitinka skirtingos reikšmės. Kitaip tariant, kiekvienai reikšmės kategorijai priskiriamas ne daugiau kaip vienas argumentas. Todėl funkcijos tarp baigtinių aibių injektyvumas reiškia, kad n ≤ m. Tai yra teiginio, kad n > m lemia neinjektyvumą, kontrapozicija: jei jokie du argumentai neįgyja tos pačios reikšmės, pradinė aibė negali būti didesnė už tikslinę.

Netaikykite šios implikacijos atvirkščiai. Nelygybė n ≤ m nereiškia, kad konkreti funkcija yra injektyvi: du argumentai gali būti priskirti pirmajai kategorijai, net jei daugelis kitų kategorijų lieka nepanaudotos. Jei nėra papildomų apribojimų, sąlyga n ≤ m leidžia sudaryti bent vieną injektyvų priskyrimą, pasirenkant n skirtingų kategorijų. Injektyvaus priskyrimo egzistavimas ir nagrinėjamo priskyrimo injektyvumas yra skirtingi teiginiai.

Jei m = 0, iš netuščios pradinės aibės į tokią tikslinę aibę nėra jokios funkcijos; iš tuščios pradinės aibės yra tuščioji funkcija. Toliau nagrinėjamiems objektų skaičiaus dėžutėse vidurkiams reikalaujame, kad m ≥ 1, nes tik tada dalyba iš m ir teiginys apie kurią nors kategoriją turi prasmę. Šis samprotavimas taikomas baigtinėms aibėms: begalinės pradinės ir begalinės tikslinės aibės negalima palyginti taip atimant jų dydžius ar skaičiuojant vidurkius.

Vidurkis užtikrina didelę ir mažą kategoriją

Kai t yra realusis skaičius, ⌈t⌉ yra mažiausias sveikasis skaičius, ne mažesnis už t, o ⌊t⌋ yra didžiausias sveikasis skaičius, ne didesnis už t. Pavyzdžiui, ⌈11/4⌉ = 3 ir ⌊11/4⌋ = 2, o abi suapvalintos 12/4 reikšmės lygios 3. Objektų skaičiai yra sveikieji, todėl apvalinimo kryptis svarbi.

Kai n ≥ 0 objektų priskiriama m ≥ 1 kategorijų, bent vienoje kategorijoje yra ne mažiau kaip ⌈n/m⌉ objektų. Pažymėkime c = ⌈n/m⌉. Jei visose kategorijose būtų mažiau nei c objektų, kiekvienoje jų būtų ne daugiau kaip c−1 objektų. Bendras objektų skaičius būtų ne didesnis kaip m(c−1), o ši reikšmė griežtai mažesnė už n, nes c−1 < n/m. Tai prieštarauja tikrajam bendram objektų skaičiui n.

Taip pat bent vienoje kategorijoje yra ne daugiau kaip ⌊n/m⌋ objektų. Pažymėkime q = ⌊n/m⌋. Jei kiekvienoje kategorijoje būtų daugiau nei q objektų, kiekvienas sveikasis objektų skaičius būtų ne mažesnis kaip q+1. Bendras objektų skaičius būtų ne mažesnis kaip m(q+1) > n, nes q+1 > n/m. Taigi tokia prielaida neįmanoma.

Kai n = 0, kiekviena kategorija yra tuščia: abu teiginiai užtikrina, kad kurioje nors kategorijoje yra bent 0 objektų, o kurioje nors – ne daugiau kaip 0. Jie neužtikrina nei objekto, nei objektų poros egzistavimo. Jei m = 1, vienintelėje kategorijoje yra lygiai n objektų. Kai n > m, reikšmė ⌈n/m⌉ yra ne mažesnė kaip 2, todėl vėl gauname pagrindinį principą.

Kai vienuolika objektų paskirstoma į keturias kategorijas, apvalinimas į didesniąją pusę užtikrina, kad bent vienoje kategorijoje yra ne mažiau kaip 3 objektų, o apvalinimas į mažesniąją pusę – kad bent vienoje kategorijoje yra ne daugiau kaip 2 objektų. Tai gali būti skirtingos kategorijos. Išvada nėra tokia, kad kiekvienoje kategorijoje yra 3 objektų ar kad bet kurioje pasirinktoje kategorijoje yra 3 objektų. Objektų skaičiai (8, 1, 1, 1) tenkina abi garantijas, kaip ir objektų skaičiai (3, 3, 3, 2).

Tolygūs paskirstymai parodo ribos tikslumą

Dalyba su liekana leidžia užrašyti n = mq+r, kur q ≥ 0 ir 0 ≤ r < m. Į r kategorijų įdėkime po q+1 objektų, o į kitas m−r kategorijų – po q objektų. Kai r = 0, visose kategorijose objektų skaičius lygus q; kitu atveju didžiausias objektų skaičius kategorijoje yra q+1. Abiem atvejais didžiausias skaičius lygus ⌈n/m⌉, o mažiausias – ⌊n/m⌋.

Ši konstrukcija įrodo rėžių optimalumą: remiantis vien n ir m, negalima garantuoti didesnės apatinės ribos didžiausios kategorijos objektų skaičiui ar mažesnės viršutinės ribos mažiausios kategorijos objektų skaičiui. Netolygiai paskirsčius objektus, viena kategorija gali būti gerokai didesnė; universali garantija turi galioti ir tolygaus paskirstymo atveju.

Vien dalumas neužtikrina vienodo objektų skaičiaus. Dvylika objektų keturiose kategorijose gali būti pasiskirstę taip: (9, 1, 1, 1). Tačiau jei n = mq ir kiekvienoje kategorijoje yra ne daugiau kaip q objektų, kiekvienoje jų turi būti lygiai q: jei kurioje nors būtų mažiau nei q, visų objektų suma būtų mažesnė nei mq. Panašiai, jei kiekvienoje yra bent q objektų, o jų suma lygi mq, nė vienoje negali būti daugiau nei q. Bendras objektų skaičius kartu su atskirų kategorijų rėžiais lemia lygybę.

Talpos riba tampa griežtu neišvengiamumo slenksčiu

Pasirinkite netuščią rinkinį iš m kategorijų. Tarkime, reikalaujama, kad objektų skaičius kiekvienoje kategorijoje būtų tarp sveikųjų skaičių L ir U, kur 0 ≤ L ≤ U. Sudėję atskirų kategorijų rėžius, gauname mL ≤ n ≤ mU. Šie rėžiai būtini, kad reikalavimą būtų įmanoma įvykdyti. Jei objektus galima nevaržomai skirstyti tarp kategorijų, šie rėžiai yra ir pakankami: iš pradžių į kiekvieną kategoriją įdėkite po L objektų, tada paskirstykite likusius n−mL objektų, kiekvienoje kategorijoje panaudodami ne daugiau kaip U−L laisvų vietų.

Jei n > mU, kurioje nors kategorijoje objektų skaičius turi viršyti U; lygybė n = mU viršijimo nelemia. Skaičiuojant sveikaisiais skaičiais, pirmasis bendras objektų skaičius, kuriam esant viršijimas neišvengiamas, yra mU+1. Jei n < mL, kurioje nors kategorijoje objektų skaičius turi būti mažesnis nei L; lygybė n = mL trūkumo nelemia. Šio teiginio apie apatinį slenkstį prielaida gali būti tenkinama tik tada, kai L > 0, nes n negali būti neigiamas.

Kad vienoje kategorijoje neišvengiamai būtų bent k objektų, kai k yra sveikasis skaičius ir k ≥ 1, reikia atmesti paskirstymą, kuriame kiekvienoje kategorijoje yra ne daugiau kaip k−1 objektų. Tikslus slenkstis yra n ≥ m(k−1)+1. Kai n = m(k−1), į kiekvieną kategoriją įdėjus po k−1 objektų, tikslas nepasiekiamas. Kai k = 1, pakanka vieno objekto; nulio objektų nepakanka.

Jei yra trys kategorijos ir kiekvienoje gali būti ne daugiau kaip du objektai, šeši objektai gali tilpti taip: (2, 2, 2), o esant septyniems kurioje nors kategorijoje neišvengiamai bus daugiau nei du. Jei kiekvienoje turi būti bent po du objektus, šešis galima paskirstyti taip: (2, 2, 2), o esant penkiems kurioje nors kategorijoje neišvengiamai bus mažiau nei du. Talpos reikalavimas nėra fizinė garantija, kad neįmanomas paskirstymas kaip nors tilps; ribos peržengimas įrodo, kad bent vienas reikalavimas negali būti įvykdytas.

Nesikertančius atvejus sudėkite, nuoseklius pasirinkimus dauginkite

Prieš taikydami skaičiavimo rėžį, tiksliai suskaičiuokite kategorijas. Jei kiekvienas objektas priklauso tik vienai iš kelių nesikertančių grupių, sudėkite grupių dydžius. Nesikertančios grupės reiškia, kad joks objektas nepriklauso dviem iš jų. Jei dvi grupės persidengia, sudedant jų dydžius bendri objektai suskaičiuojami du kartus; pirmiausia kiekvieną tokį objektą priskirkite tik vienai grupei arba vieną kartą atimkite bendrų objektų skaičių.

Kai pasirinkimai atliekami vienas po kito, skaičiuokite visus užbaigtus kelius. Jei pirmasis pasirinkimas turi dvi galimybes, o po kiekvienos jų yra trys galimi antrieji pasirinkimai, šeši rezultatai, kuriuose svarbi tvarka, yra (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3). Sandauga 2×3 kiekvieną kelią suskaičiuoja vieną kartą. Tam būtina, kad po kiekvieno pirmojo pasirinkimo būtų trys tęsiniai; jokia tikimybinio nepriklausomumo prielaida netaikoma.

Jei pirmoji šaka turi tris tęsinius, o antroji tik du, bendras skaičius yra 3+2 = 5, o ne 2×3. Medyje matyti trūkstamas kelias. Nustačius šešias iš tiesų skirtingas kategorijas, septynis objektus paskirsčius į jas, bent du neišvengiamai pateks į tą pačią kategoriją; jei netyčia vieną kategoriją suskaičiuosite du kartus, ši garantija gali susilpnėti arba būti pritaikyta klaidingai.

Vienodos liekanos lemia dalų skirtumą

Fiksuokime teigiamą sveikąjį skaičių m. Kiekvieną sveikąjį skaičių a, taip pat ir neigiamą, galima vieninteliu būdu užrašyti a = qm+r, kur q yra sveikasis skaičius, o liekana tenkina 0 ≤ r < m. Skaičių a priskirkime jo liekanai r. Yra lygiai m kategorijų, pažymėtų 0, 1, …, m−1; neigiamas sveikasis skaičius nesukuria naujos kategorijos su neigiama liekana.

Tarp m+1 skirtingų sveikųjų skaičių būtinai yra du, turintys tą pačią liekaną. Jei a = qm+r ir b = pm+r, atėmę gauname b−a = (p−q)m, taigi skirtumas yra m kartotinis. Skaičiai skirtingi, todėl jų skirtumas nelygus nuliui. Teorema neteigia nei kad vienas iš pradinių skaičių dalijasi iš m, nei kad jų suma dalijasi iš m.

Kai m = 5, šešių sveikųjų skaičių −7, −2, 0, 3, 8 ir 11 liekanos yra atitinkamai 3, 3, 0, 3, 3 ir 1. Viena teiginį tenkinanti pora yra −7 ir −2: jų skirtumas yra 5. Priskyrimo lentelė leidžia rasti konkrečias teiginį tenkinančias poras; skaičiavimo argumentas įrodo, kad tokia pora egzistuoja pasirinkus bet kuriuos šešis skirtingus sveikuosius skaičius.

Jei pradiniai duomenys yra pakartotiniai stebėjimai, o ne skirtingų sveikųjų skaičių reikšmių aibė, objektais laikykite jų pozicijas. Du stebėjimai, kurių reikšmė yra 2, turi tą pačią liekaną, o jų skirtumas yra 0, kuris dalijasi iš m. Tai yra tinkamas dviejų pozicijų priskyrimo tai pačiai kategorijai atvejis, bet ne skirtingų sveikųjų skaičių reikšmių pora, kurios skirtumas nelygus nuliui. Nurodykite, kokių objektų reikia konkrečiam taikymui.

Didelė grupė nebūtinai yra jūsų grupė

Baigtinės aibės skaidinys suskirsto jos elementus į netuščias, tarpusavyje nesikertančias grupes, kurių sąjunga yra visa aibė. Šios grupės gali būti principo kategorijos. Jei klasė, kurioje yra 25 mokinių, suskirstoma į šešias projektų grupes, kurioje nors grupėje yra bent ⌈25/6⌉ = 5 mokinių. Teorema nenurodo, kuri tai grupė, ir neteigia, kad visose šešiose yra po penkis mokinius.

Priskiriant žmones pagal gimimo mėnesį, yra dvylika galimų kategorijų, net jei kai kurios iš jų tuščios. Tarp trylikos žmonių būtinai yra du, gimę tą patį mėnesį. Jau ir tarp dvylikos žmonių gali būti daug gimusių tais pačiais mėnesiais, tačiau jei kiekvieną mėnesį gimęs tik vienas žmogus, sutapimo nėra. Tai deterministinė garantija; nereikia nei atsitiktinumo, nei vienodų gimimo kiekvieną mėnesį tikimybių, nei gimimo datų nepriklausomumo.

Negalite daryti išvados, kad dar kas nors gimė tą patį mėnesį kaip jūs. Visi kiti dvylika žmonių galėtų būti gimę vieną ir tą patį, bet kitą nei jūsų, mėnesį. Apskritai tai, kad kuriai nors kategorijai priskirtas daugiau nei vienas objektas, neišskiria iš anksto nurodytos kategorijos, paskutinio objekto ar iš anksto nurodytos poros. Norėdami baigtiniame duomenų rinkinyje rasti teiginį tenkinančią porą, nustatykite kategorijas ir palyginkite jų elementus; įrodymas ir paieška atsako į skirtingus klausimus.

Tarp penkių taškų kvadrate yra artima pora

Imkime penkis skirtingus taškus uždarame vienetiniame kvadrate: jų koordinatės tenkina 0 ≤ x ≤ 1 ir 0 ≤ y ≤ 1, naudojant tą patį ilgio vienetą. Kiekvieną koordinačių intervalą padalykime į apatinę pusę [0, 1/2) ir viršutinę pusę [1/2, 1]. Laužtinis skliaustas reiškia, kad intervalo galas įtrauktas, o apvalusis – kad neįtrauktas. Vidurio taškas priklauso viršutinei pusei; išorinis intervalo galas priklauso tai pusei, kurioje jis yra.

Tašką priskirkime pagal tai, ar jo x ir y koordinatės priklauso apatinei, ar viršutinei intervalo pusei. Šios keturios kategorijos nesikerta ir apima visus taškus, įskaitant taškus ant skiriamųjų linijų. Diagramoje kategorijų žymos yra 0, kai abi koordinatės priklauso apatinėms pusėms, 1, kai x priklauso viršutinei, o y – apatinei pusei, 2, kai x priklauso apatinei, o y – viršutinei pusei, ir 3, kai abi koordinatės priklauso viršutinėms pusėms. Kadangi 5 > 4, du taškai priklauso tai pačiai kategorijai.

Dviejų vienai kategorijai priklausančių taškų koordinačių skirtumai tenkina |Δx| ≤ 1/2 ir |Δy| ≤ 1/2. Pagal Pitagoro teoremą atstumas d tenkina d² = (Δx)²+(Δy)² ≤ 1/4+1/4 = 1/2, todėl d ≤ √2/2 ilgio vienetų. Nubrėžtų ašių mastelis vienodas. Kiekvieną ribos tašką priskyrus vienintelei kategorijai, gaunama tinkamai apibrėžta funkcija; uždari kvadratai, kuriuose telpa kategorijų taškai, vis tiek leidžia nustatyti atstumo viršutinį rėžį su nestriktąja nelygybe.

Išvados negalima sustiprinti iki d < √2/2 kiekvienam penkių taškų rinkiniui. Padėkite taškus keturiose kvadrato viršūnėse ir centre. Atstumai nuo centro iki viršūnių lygūs √2/2; atstumai tarp viršūnių yra 1 arba √2, todėl trumpiausias atstumas yra lygiai √2/2. Be to, kol nepateiktos taškų koordinatės, šis principas nenustato, kurie du taškai priklausys tai pačiai kategorijai.

Keturi taškai kvadrato viršūnėse priklauso keturioms skirtingoms kategorijoms, ir nė vienas atstumas tarp jų nėra ne didesnis kaip √2/2. Tai parodo, kodėl šiai garantijai reikia penkių taškų. Atstumo įrodymas taikomas bet kokiems taškams tolydžiame kvadrate; pavaizduoti baigtiniai atvejai iliustruoja taškų priskyrimą kategorijoms ir išvadą patvirtinančias poras, o ne įrodo bendrąjį rezultatą tikrinant atskirus pavyzdžius.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Penki objektai priskiriami penkioms kategorijoms. Ar paskirstymas būtinai turi būti injektyvus? Ar būtinai turi būti sutapimas? Pateikite savo atsakymą pagrindžiančių paskirstymų.

   Rodyti atsakymą ir paaiškinimą

   Nė vienas atvejis nėra būtinas. Objektų skaičiai (1, 1, 1, 1, 1) atitinka injektyvų paskirstymą; (2, 0, 1, 1, 1) atitinka paskirstymą su sutapimu.

   Abiejuose paskirstymuose yra penki objektai ir penkios kategorijos. Kad teorema garantuotų neinjektyvumą, turi būti n > m. Injektyvumui būtina sąlyga n ≤ m neįrodo, kad konkretus paskirstymas yra injektyvus.

2. Ką teiginiai su viršutine ir apatine sveikąja dalimi teigia, kai keturioms kategorijoms priskiriama nulis objektų ir kai vienai kategorijai priskiriami septyni objektai?

   Rodyti atsakymą ir paaiškinimą

   Kai objektų nėra, kiekvienoje kategorijoje jų skaičius yra 0, todėl abi ribos yra 0 ir jokios poros nėra. Kai kategorija viena, objektų skaičius joje yra lygiai 7.

   Abiem atvejais kategorijų aibė yra netuščia, todėl teiginiai apie kurią nors kategoriją yra prasmingi. Kai m = 1, abi suapvalintos vertės lygios n. Garantija, kai objektų nėra, nusako objektų skaičių tuščiose kategorijose, o ne objekto egzistavimą.

3. Raskite garantuojamas ribas, gaunamas apvalinant aukštyn ir žemyn, kai 25 objektų paskirstoma į šešias kategorijas. Pateikite subalansuotą paskirstymą, įrodantį, kad abi ribos yra tikslios.

   Rodyti atsakymą ir paaiškinimą

   Kurioje nors kategorijoje yra bent 5 objektų, o kurioje nors – ne daugiau kaip 4. Objektų skaičiai (5, 4, 4, 4, 4, 4) pasiekia šias ribas.

   25 = 6×4+1, todėl subalansuotai paskirsčius vienai kategorijai tenka 5 objektų, o likusioms penkioms – po 4. Didžiausias skaičius yra 5, o mažiausias – 4. Šie teiginiai yra apie tam tikras, galbūt skirtingas, kategorijas, o ne apie kiekvieną kategoriją.

4. Dvylika objektų paskirstyta į keturias kategorijas. Ar iš dalumo iš keturių būtinai išplaukia, kad kiekvienoje kategorijoje yra po tris objektus? Kokia papildoma viršutinė riba tai užtikrintų?

   Rodyti atsakymą ir paaiškinimą

   Ne: galimi objektų skaičiai (9, 1, 1, 1). Jei kiekvienoje kategorijoje objektų skaičius neviršija 3, jų suma 12 lemia, kad visi keturi skaičiai turi būti lygūs 3.

   Keturių skaičių, kurių kiekvienas neviršija trijų, didžiausia galima suma yra dvylika. Jei vienas būtų mažesnis, kiti negalėtų kompensuoti šio trūkumo neviršydami trijų. Kiekvienam skaičiui taikoma riba kartu su bendra suma įrodo lygybę; vien dalumas jos neįrodo.

5. Koks mažiausias bendras objektų skaičius užtikrina, kad vienoje iš keturių kategorijų bus bent penki objektai? Parodykite, kodėl vienu objektu mažiau nepakanka.

   Rodyti atsakymą ir paaiškinimą

   17 objektų užtikrina, kad kurioje nors kategorijoje bus bent penki. Kai bendras objektų skaičius yra 16, paskirstymas (4, 4, 4, 4) leidžia išvengti penkių objektų bet kurioje kategorijoje.

   Norint išvengti penkių objektų bet kurioje kategorijoje, kiekvienoje turi būti ne daugiau kaip keturi, taigi iš viso – ne daugiau kaip šešiolika. Septynioliktas objektas viršija šią griežtą talpos ribą. Pateiktas paskirstymas, leidžiantis išvengti penkių objektų bet kurioje kategorijoje, patvirtina, kad garantija negali galioti esant mažesniam bendram skaičiui.

6. Kiekvienoje iš keturių kategorijų turi būti nuo dviejų iki penkių objektų. Koks bendro objektų skaičiaus intervalas galimas, jei juos galima laisvai paskirstyti? Ką būtinai lemia bendri objektų skaičiai 7 ir 21?

   Rodyti atsakymą ir paaiškinimą

   Galimos bendrojo skaičiaus reikšmės yra visi sveikieji skaičiai nuo 8 iki 20 imtinai. Kai bendrasis skaičius yra 7, bent vienoje kategorijoje objektų yra mažiau nei 2; kai bendrasis skaičius yra 21, bent vienoje kategorijoje objektų yra daugiau nei 5.

   Pradėkite nuo dviejų objektų kiekvienoje kategorijoje – iš viso aštuonių – ir į kiekvieną kategoriją pridėkite iki trijų objektų. Taip gaunami visi tarpiniai bendrieji skaičiai. Septyni yra mažiau už mažiausią galimą sumą, o dvidešimt vienas viršija didžiausią galimą sumą. Kai suma lygi aštuoniems arba dvidešimčiai, pažeidimas nebūtinai įvyksta.

7. Vienas pradinis pasirinkimas turi tris tęsinius, o kitas – du. Kiek yra pilnų kelių? Atskirai: dvi grupės turi atitinkamai keturis ir tris objektus, iš kurių du yra bendri abiem grupėms. Kiek skirtingų objektų yra jų sąjungoje?

   Rodyti atsakymą ir paaiškinimą

   Yra 3+2 = 5 keliai. Sąjungoje yra 4+3−2 = 5 skirtingi objektai.

   Šakų skaičiai nevienodi, todėl padauginus du iš trijų priskaičiuojamas neegzistuojantis kelias. Skaičiuojant sąjungos objektus, bendri objektai įtraukiami į abiejų grupių bendruosius skaičius, todėl kiekvieną jų reikia vieną kartą atimti. Abiejuose uždaviniuose kiekvieną galutinį objektą skaičiuokite vieną kartą.

8. Kodėl tarp bet kurių aštuonių skirtingų sveikųjų skaičių yra du, kurių nenulinis skirtumas dalijasi iš septynių? Ar vietoj to galima daryti išvadą, kad jų suma dalijasi iš septynių?

   Rodyti atsakymą ir paaiškinimą

   Aštuonių objektų yra daugiau nei septynių liekanų kategorijų, todėl yra pora su ta pačia liekana ir nenuliniu skirtumu, kuris dalijasi iš 7. Išvada apie sumą iš to neišplaukia.

   Atimant vienodas liekanas, jos panaikinamos. Sudėjus būtų gauta dviguba tos liekanos reikšmė, kuri nebūtinai lygi nuliui moduliu septyni. Kadangi sveikųjų skaičių reikšmės skirtingos, jų skirtumas nenulinis; vien pasikartojančios pozicijos to neužtikrintų.

9. Ar trylikos žmonių grupėje, įskaitant jus, būtinai yra kas nors kitas, gimęs tą patį mėnesį kaip jūs? Kokį teiginį apie bendrą gimimo mėnesį galima garantuoti?

   Rodyti atsakymą ir paaiškinimą

   Jūsų gimimo mėnuo nebūtinai pasikartoja. Yra du žmonės, gimę tą patį mėnesį, tačiau jūs galite nepriklausyti šiai porai.

   Visi kiti dvylika galėtų būti gimę tą patį mėnesį, nesutampantį su jūsų gimimo mėnesiu, todėl nėra garantijos, kad konkrečioje kategorijoje bus antras narys. Trylika žmonių, priskirtų dvylikai galimų gimimo mėnesių, užtikrina, kad kuris nors mėnuo pasikartos, nepriklausomai nuo gimimo dienų tikimybių.

10. Kuriai kategorijai priklauso taškai (1/2, 1/4), (1/4, 1/2) ir (1/2, 1/2)? Ar pasirinkus bet kokius penkis taškus visada galima garantuoti atstumą, griežtai mažesnį už √2/2?

    Rodyti atsakymą ir paaiškinimą

    Jie priklauso atitinkamai kategorijoms 1, 2 ir 3. Ne: keturių kampų ir centro išdėstyme mažiausias atstumas yra lygiai √2/2.

    Kai koordinatė lygi intervalo viduriui, taškas priskiriamas didesnių koordinačių pusei, todėl priskyrimas yra vienareikšmis. Skaičiavimas tos pačios kategorijos taškams įrodo negriežtą ribą. Tikslus kampų ir centro išdėstymas paneigia visuotinę griežtą ribą, bet pasiekia negriežtą ribą.

Ką verta įsidėmėti

• Skaičiuokite baigtinės aibės skirtingus objektus, naudokite netuščią kategorijų šeimą ir kiekvieną objektą priskirkite tik vieną kartą.
• Kai n > m, bent du objektai būtinai patenka į tą pačią kategoriją. Iš injektyvumo išplaukia n ≤ m; atvirkštinis teiginys neapibūdina konkretaus priskyrimo.
• Bent vienoje kategorijoje objektų skaičius yra ne mažesnis nei ⌈n/m⌉, o bent vienoje – ne didesnis nei ⌊n/m⌋. Tolygiai paskirstyti objektų skaičiai rodo, kad abi visuotinės ribos yra tikslios.
• Kai bendras objektų skaičius viršija mU, bent vienoje kategorijoje jų skaičius būtinai viršija U; kai bendras skaičius mažesnis už mL, bent vienoje kategorijoje jų skaičius būtinai mažesnis už L. Vien lygybė nebūtinai lemia pažeidimą.
• Kiekviename taikyme nustatykite kategorijas ir priskyrimo taisyklę. Sąlygą tenkinančio pavyzdžio egzistavimas nenurodo jūsų kategorijos ar pasirinktos poros.