Matematické Fórum

Esperance · 04. 10. 2010 21:10

Ahoj, mohl by mi někdo poradit (a vysvětlit) řešení tohoto příkladu? Děkuju, byla bych moc vděčná

Nechť n je z množiny přirozených čísel (N). Dokažte, že mezi n+1 vybranými čísly z množiny {1,2,3.....2n} existuje dvojice a, b (a se nerovná b) tak, že a dělí b.

Olin · 04. 10. 2010 22:11

Jde o poměrně trikovou záležitost - je chytře využit tzv. Dirichletův princip (triviální pozorování, že když deset aut vjelo do devíti garáží, tak v nějaké garáži musí být aspoň dvě). Za tímto účelem doporučuji rozdělit množinu $\{1,\, 2,\, \dots,\, 2n\}$ na množiny $\{ 1,\, 1 \cdot 2^1,\, 1 \cdot 2^2,\, \dots \}$ , $\{ 3,\, 3 \cdot 2^1,\, 3 \cdot 2^2,\, \dots \}$ až po $\{ 2n-1,\, (2n-1) \cdot 2^1,\, (2n-1) \cdot 2^2,\, \dots \}$ (všechny tyto množiny jsou podmnožiny $\{1,\, 2,\, \dots,\, 2n\}$ , které s lichým číslem obsahují i všechny jeho možné násobky mocninou dvojky).

check_drummer · 05. 10. 2010 19:10

Rozdělme množinu {1,..,2n} na dvojice {i,2i} (i<=n). Dvojic je n, tedy při výběru n+1 čísel jistě nějaké dvě čísla padnou do stejné dvojice j,2j, což jsou hledaná a,b.

Pavel Brožek · 05. 10. 2010 19:14

↑ check_drummer:

Dvojic je sice n, ale nepokrývají celou množinu. Např. 2n-1 nebude v žádné dvojici.

check_drummer · 05. 10. 2010 21:23

↑ BrozekP:
Je to tak, dvojice totiž nejsou disjunktní, jak jsem si u večeře uvědomil. :-)

check_drummer · 05. 10. 2010 21:30

↑ Olin:
Jen formálně - poslední množina bude pro n>1 obsahovat jediné číslo 2n-1 - totiž (2n-1).2 > 2n.

Olin · 05. 10. 2010 21:35

↑ check_drummer:
To je samozřejmě pravda a takovýchto množin bude více. Mám-li zapsat přesně, o jaké množiny jde, pak půjde o

$\{k \cdot 2^m \, | \, m \in \mathbb{N}\cup\{0\} \, \wedge \, k \cdot 2^m \leq 2n\}$

kde $k = 1,\, 3,\, \dots,\, 2n-1$ .

Matematické Fórum

#1 04. 10. 2010 21:10

důkaz, diskrétní matematika

#2 04. 10. 2010 22:11

Re: důkaz, diskrétní matematika

#3 05. 10. 2010 19:10

Re: důkaz, diskrétní matematika

#4 05. 10. 2010 19:14

Re: důkaz, diskrétní matematika

#5 05. 10. 2010 21:23

Re: důkaz, diskrétní matematika

#6 05. 10. 2010 21:30

Re: důkaz, diskrétní matematika

#7 05. 10. 2010 21:35

Re: důkaz, diskrétní matematika

Zápatí