Matematické Fórum

nordec · 01. 03. 2010 15:17

Potřeboval bych poradit, jak dokázat, že pro libovolných n+1 přirozených čísel v intervalu <1;2n> existují dvě čísla, že jedno je násobek druhého?

Předpokládám, že tvrzení je pravdivé a možná by se dalo dokázat Dirichletovým principem, ale nevím jak.

Pavel · 01. 03. 2010 15:55 — Editoval Pavel (01. 03. 2010 19:56)

↑ nordec:

Vytvořme následujíc množiny

$A_1=\{1,2\},\nl A_2=\{2,4\},\nl A_3=\{3,6\},\nl \vdots\nl A_k=\{k,2k\},\nl \vdots\nl A_n=\{n,2n\}.$

To je n množin obsahující přirozená čísla od 1 do 2n. Z Dirichletova principu plyne, že mezi $n+1$ přirozenými čísly s požadovanou vlastností existují alespoň dvě, která patří do některé z množin $A_k$ . Tzn. jedno z nich je dvojnásobkem druhého.

ŘEŠENÍ JE ŠPATNĚ

nordec · 01. 03. 2010 17:49

A nevadí, že se jedno číslo vyskytuje ve více množinách?
$A_1=\{1,2\},\nlA_2=\{2,4\}$

Pokud takto umístíme 2n čísel do n množin, musí nějaké číslo přebývat (nebude v žádné z množin). Co když bude mezi n+1 čísel vybráno právě přebývající číslo?

Pavel · 01. 03. 2010 19:55 — Editoval Pavel (01. 03. 2010 20:21)

↑ nordec:

Beru zpět svou odpověď. To je tak, když si člověk nepřečte pořádně zadání :-)

Každé číslo mezi 1 a 2n lze vyjádřit jako součin mocniny 2 a lichého čísla, tj $\forall m\in\{1,2,3,\ldots,2n-1,2n\}\,\exists r\in\mathbb{N}_0\ :\ m=2^r\cdot q$ , kde $q$ je liché číslo mezi 1 a 2n. Avšak těchto lichých čísel je maximálně $n$ . Tzn. existují alespoň dvě čísla $m_1$ a $m_2$ mezi 1 a 2n, která jsou dělitelná q. Tzn. $m_1=2^s\cdot q$ a $m_2=2^tq$ , $s,t\in\mathbb{N}_0$ . Jedno z nich tedy dělí druhé.

nordec · 05. 03. 2010 12:49

↑ Pavel:
Trochu jsem nad tím popřemýšlel, než mi docvaklo, že $2^r$ nejsou VŠECHNA sudá čísla :)
Důkaz funguje! Díky moc.

Téma lze považovat za vyřešené.

Matematické Fórum

#1 01. 03. 2010 15:17

Kombinatorika - důkaz

#2 01. 03. 2010 15:55 — Editoval Pavel (01. 03. 2010 19:56)

Re: Kombinatorika - důkaz

#3 01. 03. 2010 17:49

Re: Kombinatorika - důkaz

#4 01. 03. 2010 19:55 — Editoval Pavel (01. 03. 2010 20:21)

Re: Kombinatorika - důkaz

#5 05. 03. 2010 12:49

Re: Kombinatorika - důkaz

Zápatí