Matematické Fórum

green19 · 14. 10. 2012 23:45

Ahojte, pomohli by ste mi prosim s jednym dokazom na Dirichletov princip? Druzstvo odohra 45 zapasov za 30 dni. Kazdy den odohra aspon 1 zapas. Dokazte, ze urcite existuju po sebe nasledujuce dni, pocas ktorych druzstvo odohralo presne 14 zapasov.

Brano · 15. 10. 2012 00:45 — Editoval Brano (15. 10. 2012 00:46)

Najprv skusme, tak ze dodam iba zaciatok.
Nech $n(k)$ je pocet zapasov odohratych od zaciatku mesiaca az po k-ty den a $r(k)$ je zvysok $n(k)$ po deleni 14. Co sa da z Dirichletovho principu povedat o $r(k)$ ?

green19 · 16. 10. 2012 15:36

[re]p308533|Brano[/re
Napisala som trochu zle zadanie, druzstvo odohra najviac 45 zapasov a aspon 1 za den

Brano · 16. 10. 2012 17:25

↑ green19:
v poriadku - to nic nemeni na mojej rade, tych (najviac) 45 zapasov sa vyuzije az v dalsom kroku

green19 · 16. 10. 2012 22:06

Ja neviem, neskusime nejaku inu napovedu? :D

Brano · 16. 10. 2012 23:28 — Editoval Brano (16. 10. 2012 23:47)

skusme rozvinut tu prvu :)
moznych zvyskov po deleni 14 je kolko? (0,1,2 .... 13) - to budu nase priehradky v holubniku
kolko mame dni (resp clenov postupnosti $r(k)$ ?) - to budu nasi holubkovia
o akom najvacsom cisle $p$ vies povedat, ze za kazdych okolnosti existuje priehradka v ktorej sedi aspon $p$ holubkov?

vanok · 17. 10. 2012 11:59 — Editoval vanok (17. 10. 2012 13:22)

Ahoj green19,
Akoze tento problem, je trochu delikatny,(pre ludi, co nemaju zvyk z takymito problemamy) dam ti tu"modelove" riesenie
Pouzijem podla kolegu ↑ Brano: $n(k)$ toto znacenie.
Vieme, podla textu problemu, ze
$1 \le n(1) < n(2) < ... < n(k) \le 45$
ako aj
$k_{max}=30$

Uvazujme teraz postupnost $n(k)+14$ , a tak plati

$15 \le n(1) +14< n(2) +14< ... < n(k)+14$
Preto
$n(1),...,n(k), n(1)+14,... , n(k)+14$ , kde $n(k) \le 45+14=59$
tvori konecnu postupnost kardinality $2k$ .

To znamena, ze pre $k_{max}$ , mame v poslednej postupnosti $60$ clenov, z ktorych najvadci je $\le 59$ , preto podla Diriclet-oveho priehrakoveho principu, existuju, v tejto postupnosti (aspon)dva rovnake cleny.

Autor skryl část textu. Zobrazit/skrýt!

To znamena ze existuju $i,j$ take, ze $n(j)=n(i)+14$ .

Brano · 17. 10. 2012 13:44 — Editoval Brano (17. 10. 2012 14:27)

↑ vanok:
hmm ... toto je trochu elegantnejsie ako riesenie co som mal na mysli

edit: naozaj velmi elegantne :-) ale len tak pre zaujimavost - nedalo by sa pouzit, ak by sme chceli dokazat, ze v niekolkych po sebe iducich dnoch odohrali prave 23 zapasov

vanok · 17. 10. 2012 14:53 — Editoval vanok (17. 10. 2012 14:54)

↑ Brano:
Zda sa mi, ze 14 je maximalna limita v tomto probleme ( to pretoze maximum prvkov v tej postupnosti dlzky 60, je ohraniceny cislom 59)
No ale ak zmenis, jeho parametre, mozes sa dostat aj k 23.
Mna k tomuto rieseniu, doviedol podobny tento ( trocha koplikovanejsi) problem

Hrac sachu, hra aspon jednu partiu sachu za den, ale nie viac ako 10 za tyzden, dokazte, ze existuje "spojita" perioda dni ked odohra presne 21 partii

ktory som riesil ( uz dost davno).
Komplikovanejsie je v nom, ze treba urcit minimalny pocet dni, aby sa dal pouzit Diriclet.
V oboch problemoch je okrem , Diriclet-a, nutne pouzit trik, ze kazda z oboch ("malych") postupnosti ma vsetky prvky nerovnake medzi sebou.

A urcite by zaujimalo kolegov tvoje riesenie, tak nevahaj a daj ho tu do formy...

Brano · 17. 10. 2012 15:39

Mal som na mysli, ze ostatne cisla by ostali rovnake, len by tam bolo treba najst interval s 23 zapasmi. Podme to skusit.

Mame $n(k)$ ako postupnost zapasov odohranych do dna $k$ a $r(k)$ je postupnost zvyskov po deleni - $n(k)$ delim 23.

Postupnost $r(k)$ nadobuda hodnoty z mnoziny $\{0,1,2,...,22\}$ ale pocet clenov tej postupnosti je 30, cize pre vhodne $k<l$ musi platit $r(k)=r(l)=r$ , teda $n(k)=23x+r$ a $n(l)=23y+r$ , kde $x,y$ su cele. Ale kedze $0<n(k)<n(l)\le 45$ tak $x=0$ a $y=1$ , cize $n(l)-n(k)=23$ . QED.

Ked sa vsak toto adaptuje na tych 14 zapasov, tak je to trochu komplikovanejsie - najde sa zvysok co sa opakuje tri krat, cize tam mam nejake $x,y,z$ ale vsetky vyjdu najviac 3, cize 2 musia byt po sebe iduce.

Mozme hladat $x$ zapasov v rade pre max $M$ zapasov pocas $d$ dni s tym, ze kazdy den sa hra aspon 1 zapas (cize $d\le M$ ). Mne sa zda, ze toto
$1\le \left[\frac{M}{x}\right]<2\left[\frac{d-1}{x}\right]$
je postacujuca podmienka, ale zrejme nieje nutna (staci zobrat $d=M$ ). Teda ta prva nerovnost je ocividne nutna o tej druhej sa bavime.