Matematická indukce Počítání s procenty Zlehka kombinatoriky MB101 – 1. demonstrovaná cvičení Důkazy matematických tvrzení Masarykova univerzita Fakulta informatiky 21.9. 2010 Matematická indukce Počítání s procenty Zlehka kombinatoriky Plán přednášky 1 Matematická indukce 2 Počítání s procenty 3 Zlehka kombinatoriky Matematická indukce Počítání s procenty Zlehka kombinatoriky Princip matematické indukce Mějme tvrzení T(n) závislé na přirozeném číslu n. Pokud dokážeme 1 Pro nějaké přirozené k0 platí tvrzení T(k0), 2 Pro libovolné přirozené k ≥ k0 platí implikace T(k) ⇒ T(k + 1), pak tvrzení T(n) platí pro libovolné přirozené n ≥ k0. Matematická indukce Počítání s procenty Zlehka kombinatoriky Princip matematické indukce Mějme tvrzení T(n) závislé na přirozeném číslu n. Pokud dokážeme 1 Pro nějaké přirozené k0 platí tvrzení T(k0), 2 Pro libovolné přirozené k ≥ k0 platí implikace T(k) ⇒ T(k + 1), pak tvrzení T(n) platí pro libovolné přirozené n ≥ k0. Ukažte, že n i=1 i2 = n(n + 1)(2n + 1) 6 . Matematická indukce Počítání s procenty Zlehka kombinatoriky 1 Na kolik nejvíce částí dělí rovinu n přímek? Matematická indukce Počítání s procenty Zlehka kombinatoriky 1 Na kolik nejvíce částí dělí rovinu n přímek? 2 Na kolik nejvíce částí dělí prostor n rovin? 3 Všechna přirozená čísla jsou si rovna. Matematická indukce Počítání s procenty Zlehka kombinatoriky Plán přednášky 1 Matematická indukce 2 Počítání s procenty 3 Zlehka kombinatoriky Matematická indukce Počítání s procenty Zlehka kombinatoriky Příklad Mirek si chce koupit nové auto. Auto stojí 300 000 Kč. Mirek by chtěl auto koupit na měsíční splátky. Prodávající společnost mu nabízí půjčku na koupi auta s roční úrokovou mírou 6%. Mirek by chtěl auto splatit za tři roky. Jak vysoká bude měsíční splátka? (první splátku zaplatí po měsíci od koupě) Matematická indukce Počítání s procenty Zlehka kombinatoriky Příklad Mirek si chce koupit nové auto. Auto stojí 300 000 Kč. Mirek by chtěl auto koupit na měsíční splátky. Prodávající společnost mu nabízí půjčku na koupi auta s roční úrokovou mírou 6%. Mirek by chtěl auto splatit za tři roky. Jak vysoká bude měsíční splátka? (první splátku zaplatí po měsíci od koupě) Jak dlouho bude splácet, chce-li měsíčně splácet 2000 Kč? Matematická indukce Počítání s procenty Zlehka kombinatoriky Plán přednášky 1 Matematická indukce 2 Počítání s procenty 3 Zlehka kombinatoriky Matematická indukce Počítání s procenty Zlehka kombinatoriky Příklad Kolika různými způsoby může vypadat pořadí týmů v tabulce hokejové extraligy? Matematická indukce Počítání s procenty Zlehka kombinatoriky Příklad Kolika různými způsoby může vypadat pořadí týmů v tabulce hokejové extraligy? Příklad Kolika způsoby lze vybrat z osmi obyvatel domu tříčlenný domovní výbor, který se skládá z předsedy, místopředsedy a pokladníka? Matematická indukce Počítání s procenty Zlehka kombinatoriky Příklad Kolika různými způsoby může vypadat pořadí týmů v tabulce hokejové extraligy? Příklad Kolika způsoby lze vybrat z osmi obyvatel domu tříčlenný domovní výbor, který se skládá z předsedy, místopředsedy a pokladníka? Příklad Kolika způsoby můžeme vytvořit čtyři smíšené páry z deseti chlapců a osmi dívek? Matematická indukce Počítání s procenty Zlehka kombinatoriky Příklad Kolika různými způsoby může vypadat pořadí týmů v tabulce hokejové extraligy? Příklad Kolika způsoby lze vybrat z osmi obyvatel domu tříčlenný domovní výbor, který se skládá z předsedy, místopředsedy a pokladníka? Příklad Kolika způsoby můžeme vytvořit čtyři smíšené páry z deseti chlapců a osmi dívek? Příklad Kolik existuje různých řešení rovnice x1 + x2 + x3 = 100 v množině kladných celých čísel?