Dirichlet' printsiip

Pane kastidesse rohkem asju, kui on kaste, ja mõnda kasti satub neid kaks. Selles kogu printsiip seisnebki. Kunst peitub kastide valimises. Siin on kolm ülesannet, kus kastid on peidetud. Vali ise arvud või värvi seosed ja leht näitab, milline kast üle ajab.

Näidisarvutus — Dirichlet' printsiip

Arvud kastides	kattumine on vältimatu
Kaht arvu sisaldav kast	5 \| 10
kast 9	9
kast 11	11
kast 13	13
kast 15	15

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Dirichlet' printsiip

Dirichlet' printsiip: kui N asja pannakse k kasti ja N > k, siis on mingis kastis vähemalt kaks asja. Täpsemalt, mingis kastis on vähemalt ⌈N/k⌉ asja ehk vähim täisarv, mis on vähemalt N/k.

Mida iga sümbol tähendab

N: paigutatud asjade arv
k: kastide arv
⌈N/k⌉: N/k ümardatuna üles: vähim asjade arv, mis peab kõige täiemasse kasti minema

Kust valem tuleb

Miks ⌈N/k⌉. Kui igas kastis oleks vähem kui N/k asja, mahutaksid kõik k kasti kokku vähem kui k × N/k = N asja, ometi on seal kõik N asja. Seega peab mingis kastis olema vähemalt N/k asja. Kuna asjade arv on täisarv, on seal neid vähemalt ⌈N/k⌉. Viis seost kahes värvis annavad ⌈5/2⌉ = 3 ühte värvi seost; kuusteist seost kolmes värvis annavad ⌈16/3⌉ = 6.
Kastide valimine jaguvuse korral. Iga täisarvu saab täpselt ühel viisil esitada paaritu arvu ja kahe astme korrutisena, m × 2ᵃ; paiguta see kasti m. Kaks arvu samas kastis on m × 2ᵃ ja m × 2ᵇ (kus a < b) ning esimene jagab teist. Paaritud arvud vahemikus 1 kuni 2n on 1, 3, …, 2n − 1, mis teeb n kasti. Seega sunnivad n + 1 valikut kaks arvu samasse kasti. See piir on täpne: n + 1, …, 2n moodustavad n arvu, igaüks eraldi kastis. Ükski ei jaga teist, sest isegi vähima arvu kahekordistamisel ületame 2n piiri.
Võrdsetest summadest ühisosata rühmadeni. Kaks erinevat sama summaga rühma A ja B võivad sisaldada ühiseid arve. Eemalda need mõlemast: iga summa väheneb sama palju ja summad jäävad võrdseks. Kumbki rühm ei muutu tühjaks, sest kui A asuks täielikult B sees, oleks B summa suurem, kuna kõik arvud on positiivsed. Alles jääb kaks ühisosata mittetühja rühma, mille summad on võrdsed, ja just seda leht joonistabki.

Üheksa arvu 1 kuni 16: üks jagab alati teist 🖖

Kirjuta iga arv paaritu arvu ja kahe astme korrutisena: 12 = 3 × 4, 10 = 5 × 2. Sama paaritu osaga arvud lähevad samasse kasti ning väiksem jagab suuremat, sest need erinevad vaid kahe astme võrra. Arvude 1 kuni 16 seas on kaheksa paaritut arvu ja seega kaheksa kasti. Üheksa valikut paigutavad kaks arvu samasse kasti. Vajuta 9 kuni 16, et näha kaheksat arvu, mis sellest pääsevad, asudes igaüks ise kastis. See õnnestub vaid 10 juhul 12 870-st võimalikust kaheksasest valikust. Seejärel vajuta 9 kuni 16 ja 5. Kõik 11 440 üheksast arvust koosnevat valikut sisaldavad jaguvat paari ning kastid tõestavad seda ilma ühtegi valikut läbi proovimata.

Kuue inimese seas on kolm omavahelist sõpra või kolm võõrast 🖖

Vajuta Kuus inimest ja vaata 1. inimest. Tema viis seost on kahes värvis, seega vähemalt kolmel neist on sama värv. Oletame, et nad on sõbrad. Kui mingid kaks neist kolmest on omavahel sõbrad, moodustavad nad koos 1. inimesega kolme omavahelise sõbra rühma. Kui ükski pole, on need kolm omavahelised võõrad. Mõlemal juhul tekib kolmnurk, kusjuures see arutluskäik ei sõltu konkreetsest värvimisest. Viis inimest saavad seda vältida, kui sõbrad on paigutatud mööda viisnurga serva ja võõrad diagonaalidele. Viie inimese seoste 1024 värvimisviisist vaid 12 väldivad ühevärvilist kolmnurka ning igaüks neist vastab mingit pidi asetsevale viisnurgale. Kuue inimese 32 768 variandist ei suuda seda ükski. Greenwood ja Gleason esitasid selle arutluskäigu 1955. aastal.

Kümme kahekohalist arvu peidavad alati kaht võrdset summat, nagu ka üheksa 🖖

Vajuta Kümme arvu. Kümme erinevat kahekohalist arvu moodustavad 2¹⁰ − 1 = 1023 mittetühja rühma ning rühma summa saab olla vaid vahemikus 10 kuni 90 + 91 + … + 99 = 945, mis teeb kokku 936 väärtust. Seega peab kahel rühmal olema sama summa. Jäta ühised arvud välja ning summad on endiselt võrdsed, rühmad aga täiesti eraldiseisvad. See oli 1972. aasta rahvusvahelise matemaatikaolümpiaadi esimene ülesanne. Üheksa erineva arvu korral on 511 rühma maksimaalselt 846 summa vastu ja loendamine ei ütle midagi. Tõde on loendamisest peenem: üheksa arvu, mille iga rühma summa on erinev, nõuavad, et üks neist oleks vähemalt 161 (J. P. Grossmani arvutus). Seega üheksa kahekohalist arvu kattuvad samuti alati. Kaheksa saavad pääseda, vajuta Kaheksa pääsejat.

Ülesanne täielikult lahendatud

Mitu inimest on vaja, et kolme värvi korral tekiks ühevärviline kolmnurk? 4 sammu
Iga inimpaar on nüüd sõbrad, võõrad või rivaalid: kahe värvi asemel on kolm. Mitu inimest tagab kolmiku, kes on omavahel seotud üheainsa värviga?

Ava see ülesanne tööriistas
1. Kahe värviga algab lehe arutluskäik ühe inimese seostest:
  
  $6 people : 5 links, 2 colours \Rightarrow ⌈ \frac{5}{2} ⌉ = 3 share a colour$
2. Kolme värvi korral võtame ühe inimese 17 hulgast. Tema 16 seost jagunevad kolme värvi vahel:
  
  $17 people : 16 links, 3 colours \Rightarrow ⌈ \frac{16}{3} ⌉ = 6 share a colour$
3. Kui mingid kaks nende kuue seast on seotud sama värviga, moodustavad nad koos esimese inimesega ühevärvilise kolmnurga:
  
  $a link of that colour among the 6 \Rightarrow a triangle through person 1$
4. Kui ei ole, kasutavad need kuus vaid kaht ülejäänud värvi ning lehe kuueliikmeline pidu juba tagab seal kolmnurga tekkimise:
  
  $no such link \Rightarrow the 6 use 2 colours \Rightarrow a triangle, since R (3, 3) = 6$
Vastus

Seitsmeteistkümnest inimesest piisab alati. Greenwood ja Gleason näitasid 1955. aastal, et kuueteistkümnest ei piisa: nad värvisid 16 inimese seosed kolme värviga nii, et ühtegi ühevärvilist kolmnurka ei tekkinud. Nelja värvi puhul vastust ei teata; see jääb arvude 51 ja 62 vahele.

$R (3, 3, 3) = 17; 51 \leq R (3, 3, 3, 3) \leq 62$

Õpitee

Tõestusmeetodid

Allikad (5)

The party problem solved exactly as this page solves it, the pentagon with red sides and blue diagonals for five and one person's five links for six, and Theorem 4, three colours need exactly 17 people, which is the worked problem: R. E. Greenwood and A. M. Gleason, "Combinatorial Relations and Chromatic Graphs", Canadian Journal of Mathematics 7, 1–7 (1955).
The equal-sums problem as it was set, ten distinct two-digit numbers, with the count of 1,023 groups against sums of at most 945: 14th International Mathematical Olympiad, 1972, Problem 1; problem and solution in J. Scholes's IMO archive (Kalva).
Why nine two-digit numbers cannot escape either: nine numbers with all their subset sums different need one at least as large as 161: OEIS Foundation, "A276661: Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum", The On-Line Encyclopedia of Integer Sequences.
Three colours are settled at 17; four are not, and the answer lies between 51 and 62: OEIS Foundation, "A003323: Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's", The On-Line Encyclopedia of Integer Sequences.
The principle stated and used, including its generalised form, ⌈N/k⌉ in some box: E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §15.8, The Pigeonhole Principle.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.