Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 15. 06. 2008 20:39

powa
Zelenáč
Příspěvky: 2
Reputace:   
 

Ramseyovy věty

Ahoj, prosím o pomoct s těmito příklady:

1) Dokažte pomocí Ramseyovy věty, že pro každé t \in N existuje N \in N takové,
že v množině {1, 2, . . . ,N} libovolně obarvené t barvami existují čísla x, y, z
taková, že jsou všechna jedné barvy a platí x + y = z.

2) Dokažte, že pro každé k \in N existuje N \in N takové, že libovolná N-prvková
posloupnost reálných čísel obsahuje neklesající nebo nerostoucí podposloupnost délky k.

Offline

 

#2 15. 06. 2008 22:32

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4246
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
 

Re: Ramseyovy věty

Tzv. Ramseyova věta v kombinatorice (ve zjednodušené podobě) říká následovné pro každá přirozená k,c>0: Obarvíme-li každou dvojici prvků dostatečně veliké konečné množiny X jednou z c barev, pak nalezneme k-prvkovou podmnožinu K této X takovou, že všechny dvojice prvků z K dostaly stejnou barvu.

1) Dvojici (a,b) obarvěme barvou, kterou je obarveno |a-b|. Dvojice (a,a) obarvíme zeleně. Dle Ramseyovy věty najdeme trojici a,b,c takovou, že dvojice (a,b),(a,c),(b,c) mají stejnou barvu. Bez újmy na obecnosti a<b<c. To ale znamená, že x=b-a, y=c-b a z=c-a mají stejnou barvu, čímž jsme hotovi.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

#3 15. 06. 2008 22:53

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4246
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
 

Re: Ramseyovy věty

2) postupujme indukcí, řekněme, že pro k už jsme takové N(k) našli a hledejme N(k+1) pro k+1. Ukažme, že N(k+1)=N(k)(N(k)+1) stačí. Máme tak N(k)+1 bloků tvořených N(k) prvky. Z prvního bloku vybereme monotoónní (BÚNO nerostoucí) posloupnost délky k. Kdybychom pak z nějakého dalšího bloku vybrali neklesající posloupnost délky k, měli bychom vyhráno (porovnáním posledního prvku nerostoucí a prvního prvku neklesající posloupnosti docházíme k tomu, že v obou případech lze jednu posloupnost protáhnout). Pokud se nám toto nepovede, víme, že z každého bloku vybereme posloupnost nerostoucí. Vybrali jsme tedy k+1 nerostoucích posloupností, snadno ale nahlédneme, že jejich poslední prvky musí tvořit neklesající posloupnost délky k+1.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson