Matematické Fórum

fmfiain · 03. 05. 2019 12:22

Dobrý deň,
čítam si 3. príklad z: https://cs.wikipedia.org/wiki/Dirichletův_princip
a vôbec ho nedokážem pochopiť. Pomôže mi s tým niekto?

Ďakujem za odpoveď.

vlado_bb · 03. 05. 2019 12:44

↑ fmfiain: To je pomerne nejasne formulovana otazka, mne sa napriklad problem zda vysvetleny velmi jasne. Ktorej vete v texte nerozumies?

vanok · 03. 05. 2019 17:28

Ahoj ↑ fmfiain:,
Mala uvaha.
Z daneho prikladu n° 3 je jasne ak priradis kazdemu z n ludi danej skupiny, cislo jeho znamosti ( ktore je jedno z cisliel 1,2,3,...,n-1) tak je jasne ze aspon z nich budu mat priradene take iste cislo.

STACI?

fmfiain · 03. 05. 2019 18:27

↑ vanok:
Dobrý deň,
dokázal by si to preformulovať na holuby a chlieviky?

Ďakujem za odpoveď.

fmfiain · 03. 05. 2019 18:44

↑ vanok:
Dobrý deň,
už so to pochopil. Zabudol som na okrajové podmienky:
nemůže zároveň existovat skupina, kde by byl někdo, kdo zná všechny ostatní a skupina, kde by byl někdo, kdo nezná nikoho.

Čiže $n-1$ chlievikov a $n$ holubov.

vanok · 03. 05. 2019 20:05

👍

fmfiain

Dobrý deň,
len si chcem overiť príklad 4 z #1:

Počet stien je 16.
Počet vrcholov je 9.
Počet neorientovaný hrán je (podľa Eulerovho vsťahu) 16 + 9 - 2 = 23.
Počet orientovaných hrán (polhrany) je 23 * 2 = 46.
Ak by sme uvažovali (sporom), že žiaden vrchol nemá viac ako 5 orientovaných hrán, dostali by sme maximálny počet hrán pre všetky vrcholy 5 * 9 = 45. A to je spor s predpokladom.

Opäť by som to previedol na 45 chlievikov a 46 holubov.

vanok · 04. 05. 2019 17:43 — Editoval vanok (04. 05. 2019 17:46)

Ak chces mozes si aj tu prestudovat dalsie dokazy a aj vyriesit dve cvicenia, na tvoju temu ↑ fmfiain:,
http://zimmer.csufresno.edu/~larryc/pro … nhole.html
( je to z angl. verzie).

fmfiain · 04. 05. 2019 17:48

Dobrý deň,
ešte by som dodal, že to delenia na orientované hrany v #7 je preto, aby sme mohli dvom bodom priradiť tú istú hranu.

fmfiain · 04. 05. 2019 19:26

↑ vanok:
Dobrý deň,
v tom tvojom prvom príklade (#8) je počet chlievikov N - 1 a počet holubov N. Aspoň dve budú mať rovnaké modulo N - 1.

fmfiain · 04. 05. 2019 19:55

↑ vanok:
Dobrý deň,
v tom tvojom druhom príklade (#8) je počet chlievikov N a počet holubov je $\sum_{i = 1}^{N}a_{i}$ . Keďže sa celé čísla (holuby) môžu opakovať, tak $(a_{1} + ... + a_{N})\mod(N) = 0$ , kde $a_{1} = ... = a_{N} = 1$ .

Nie som si istý čí som toto správne pochopil.

vanok · 04. 05. 2019 21:55

Ahoj ↑ fmfiain:,
Ano aj tak sa to povedat.
A z toho maj nakoniec ten za ver, ktory je na konci prveho prikladu zvorazneny.

vanok · 04. 05. 2019 22:02

↑ fmfiain:,
Na tomto priklade musis este porozmyslat.
Co pises nie je presne.
Treba uvazovat o cislach $b_1,...,b_N$ , ktore su prvky z $\Bbb {Z_N}$ .

fmfiain · 05. 05. 2019 07:25

↑ vanok:
Dobrý deň,
je jasné, že sa jedná o $b_1,...,b_N$ chlievikov a $\Bbb {Z_N}$ holubov. Každý z holubov je označený nejakým číslom zo $\Bbb {Z_N}$ . Pri súčte čísiel holubov mi vyjde, že ak sa môžu holuby opakovať, tak najmenšie číslo, ktoré dostaneme je súčet jednotiek, teda N. Teda $b_{i} = b_{j}$ ak $i < j$ .
Teda minimálne v jednom chlieviku sú dva holuby.

vanok · 05. 05. 2019 12:46 — Editoval vanok (05. 05. 2019 14:43)

Ahoj ↑ fmfiain:,
Presnejsie,
ak jedno z cisiel $b_i$ je nula v $\Bbb Z_N$ tak problem je vyrieseny; ( vidis preco?)
v opacnom pripade cisla $b_i$ ( je ich N) mozu byt nejaky nenulovy prvok s $\Bbb Z _N$ ( tych je N-1). A tak aspon dve musia byt rovnake. ....Dokonci to sam!

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

fmfiain

↑ vanok:
Dobrý deň,
ak som to pochopil, tak máme N čísel, ktoré sú všetky kladné ( $a_{i}$ ). Ak máme zvyšok po delení týchto čísel 0, deliteľnosť mám vyriešenú. Ak ale zvyšok po delení je od 1 po N, tak .... A tu už to nechápem.
Edit: Už mi to došlo: Tých $b_{i}$ je N, teda ak aj nemáme 0 hneď pri prvom čísle, tak aj $b_{N}$ obsahuje 0, kde $a_{N} = N$ .

vanok · 06. 05. 2019 11:00 — Editoval vanok (06. 05. 2019 12:56)

Ahoj ↑ fmfiain:,
Tak ten prvy pripad si pochopil.
Ak na opak ziadny z bi nie je je nulovy:
Tak potom mas N cisiel bi a N-1 moznosti hodnot, ktore mozu zobrat, to znamena, ze aspon dve bi musia byt rovnake ( to ti zarucuje Dirichlet)
Povedzme,ze bi=bj a i>j
Vyjadri teraz bi- bj : je to sucet cisiel $a_i+a_{i-1}+...+a_{j+1}=0(mod N)$
Co to znamena?

fmfiain · 06. 05. 2019 15:10

↑ vanok:
Dobrý deň,
rozumiem, že ak majú dva rôzne indexy rovnakú hodnotu, tak ich rozdiel je rovný 0.
Teraz mi zaplo. My už nemáme medzi číslami $b_{i} = 0$ , tak že to posledné číslo je od 1 po N-1.
A preto mám vždy dve čísla rovnaké s rôznym indexom.

vanok · 06. 05. 2019 15:26

Ahoj ↑ fmfiain:,
Ano. To presne tak funguje.

Matematické Fórum

#1 03. 05. 2019 12:22

Dirichletov princíp

#2 03. 05. 2019 12:44

Re: Dirichletov princíp

#3 03. 05. 2019 17:28

Re: Dirichletov princíp

#4 03. 05. 2019 18:27

Re: Dirichletov princíp

#5 03. 05. 2019 18:44

Re: Dirichletov princíp

#6 03. 05. 2019 20:05

Re: Dirichletov princíp

#7 04. 05. 2019 17:27 — Editoval fmfiain (04. 05. 2019 17:35)

Re: Dirichletov princíp

#8 04. 05. 2019 17:43 — Editoval vanok (04. 05. 2019 17:46)

Re: Dirichletov princíp

#9 04. 05. 2019 17:48

Re: Dirichletov princíp

#10 04. 05. 2019 19:26

Re: Dirichletov princíp

#11 04. 05. 2019 19:55

Re: Dirichletov princíp

#12 04. 05. 2019 21:55

Re: Dirichletov princíp

#13 04. 05. 2019 22:02

Re: Dirichletov princíp

#14 05. 05. 2019 07:25

Re: Dirichletov princíp

#15 05. 05. 2019 12:46 — Editoval vanok (05. 05. 2019 14:43)

Re: Dirichletov princíp

#16 06. 05. 2019 08:52 — Editoval fmfiain (06. 05. 2019 09:01)

Re: Dirichletov princíp

#17 06. 05. 2019 11:00 — Editoval vanok (06. 05. 2019 12:56)

Re: Dirichletov princíp

#18 06. 05. 2019 15:10

Re: Dirichletov princíp

#19 06. 05. 2019 15:26

Re: Dirichletov princíp

Zápatí