Matematické Fórum

DAVEOV · 04. 12. 2008 23:32

Zdravim, nevim jestli to tady uz nekdo psal nebo ne, ale potreboval bych pomoct s dvema lehkymi priklady, sem vdecny za jakoukoli radu...

Kombinatorika
Dokažte, že pro všechna přirozená čísla n>10 je 2n větší než n3.

Teorie grafů
Ve výpočetním clusteru je zapojeno 2m+1 počítačů, každý je propojen kabelem s alespoň m dalšími počítači. Ukažte, že celá síť je jistě souvislá. Platí tvrzení i pro cluster s 2m+2 počítači? Své rozhodnutí dokažte.

Marian · 04. 12. 2008 23:52 — Editoval Marian (05. 12. 2008 00:43)

↑ DAVEOV:

Budu dokazovat úlohu první několika metodami

1. Matematická indukce
Ověříme platnost indukčního předpokladu pro n=10 (1024=2^10>10^3=1000 - O.K.). Předpokládejme, že nerovnost platí pro nějaké fixní přirozené číslo n>10. Dokážeme, že nerovnost platí i pro číslo n+1. Předpokládáme tedy, že platí ... (první řádek je předpoklad, zbytek jsou úpravy)

Stačí nyní ukázat, že platí nerovnost označená otazníkem. Jedná se o nerovnost mezi dvěma kubickými polynomy. Dokážu tuto nerovnost třeba takto (provádím ekvivalentní úpravy):

A pokud budeme za čísla n uvažovat hodnoty větší než 10 (což chceme), bude poslední řádek platit. To se zdůvodní celkem snadno, neboť platí snadno ověřitelný odhad $10>4+2+1>\sqrt[3]{4}+\sqrt[3]{2}+1$ . Vykonané úpravy byly ekvivalentní, proto platí nerovnost $2n^3>(n+1)^3,\qquad n>10$ . Tím je důkaz matematickou indukcí hotov!

2. Vlastnost funkce
Úlohu lze dokazovat třeba i tak, že původní nerovnost zlogaritmujeme (což je ekvivalentní úprava v našem případě):

Víme (dosazením), že nerovnost (jak původní, tak transformovaná ekvivalentními úpravami) platí pro n=10. Pokud položíme
$f(x):=x\cdot\ln 2-3\cdot\ln x ,\quad x>0,$
a pokud se nám podaří dokázat, že funkce je od jistého čísla x_0 rostoucí, přičemž 0<x_0<10, pak bude pro všechna x>10 platit f(x)>f(10)>0, tedy
$x\cdot\ln 2-3\cdot\ln x>0$ - a to chceme. Proto se spočte nejprve derivace f'(x):
$f'(x)=\ln 2-\frac{3}{x}.$
Rovnice $\ln 2-\frac{3}{x}=0$ má jediné řešení, totiž $x=\frac{3}{\ln 2}$ . Odtud je vidět, že za x_0 mohu vzít třeba číslo 3, protože platí $0<\frac{3}{\ln 2}<10$ . Podle výše uvedeného je původní tvrzení dokázáno.

3. Použití jiné funkce
Mohl bys postupovat i tak, že napíšeš

Položíš $f(x):=x^{\frac{1}{x}}=e^{\frac{\ln x}{x}}$ . Spočteš derivaci a ukážeš, že funkce je klesjící pro x>e. Protože původní nerovnost platí pro x=10, je jasné, že platí i pro všechna x, resp. n větší než 10.

jelena · 05. 12. 2008 00:14 — Editoval jelena (05. 12. 2008 00:34)

↑ Marian:

Zdravím, Mariane :-)

na několik metod se těším.

Kolegovi ↑ DAVEOV: doporučim, aby se pokusil využit tlačítko "Hledat"

a kolegu Kondra moc zdravím a navrhuji na udělení titulu "Komenský diskrétní matematiky pro informatiky VSB".

Editace :-) vědela jsem, proč se mám těšít :-)

DAVEOV · 05. 12. 2008 00:38

↑ Marian:

Hm solidni prace, sam sem skoncil nekde na zacatku :D Dost obsahla odpoved, takze dekuji pekne:)
Druhy priklad sem vyhledal a reseni uz nasel.
Akorat mala chybka asi u vypoctu pomoci funkce na tretim radku nema byt n*ln*2 - 3ln*n?

Pavel · 05. 12. 2008 11:59

↑ Marian:

Ještě bych doplnil jeden důkaz matematickou indukcí. Stačí dokázat, že

$2^{10+k}>(10+k)^3,\qquad k\in\mathbb N$

Pro k=1 to zřejmě platí. Nechť nerovnost platí pro k. Pak

$2^{10+k+1}=2\cdot 2^{10+k}>2(10+k)^3=(10\sqrt[3]{2}+k\sqrt[3]{2})^3>(10\cdot 1.2+1.2k)^3>(11+k)^3=(10+k+1)^3$

Marian · 05. 12. 2008 13:45

↑ Pavel:

Ano, jsem si toho vědom. Měl jsem popsaného dost papíru, ale rozhodl jsem se pro méně tradiční alternativy řešení. Díky za doplnění.

Matematické Fórum

#1 04. 12. 2008 23:32

Ulohy z diskretni matematiky

#2 04. 12. 2008 23:52 — Editoval Marian (05. 12. 2008 00:43)

Re: Ulohy z diskretni matematiky

#3 05. 12. 2008 00:14 — Editoval jelena (05. 12. 2008 00:34)

Re: Ulohy z diskretni matematiky

#4 05. 12. 2008 00:38

Re: Ulohy z diskretni matematiky

#5 05. 12. 2008 11:59

Re: Ulohy z diskretni matematiky

#6 05. 12. 2008 13:45

Re: Ulohy z diskretni matematiky

Zápatí