Kombinace

Dá se to řešit dvěma způsoby, podle toho, o jaké úrovni matematiky se bavíme.

Na střední škole si sestrojíš Diofantickou rovnici, kterou vyřešíš: 2k + 5l = 37

k, l >= 0

řešení (k, l): (1, 7), (6, 5), (11, 3), (16, 1)

I když je to v tomhle případě snadné, mohli jsme to řešit rychleji, pokud si uvědomíme:

1. 37 = 35 + 2
2. nsn(2, 5) = 10 & NSD(2, 35) = 1

Takže můžeme upravit rovnici do tvaru 2 + 5l + nsn(2, 5)*m = 37 5l + 10m = 35

l + 2m = 7

l, m >= 0

řešení (l, m): (1, 3), (3, 2), (5, 1), (7, 0)

Na vysoké škole můžeš použít teorii čísel:

nsn(2, 5) = 10 37 ≡ 7 ≡ 2 + 5 (mod 10)

úloha má 4 řešení, protože 37 = 10k + 2x + 5y a 0 <= k < 4

Jestli mému řešení nerozumíš nebo si říkáš, že to musí jít lépe, tak tě zklamu.

Úlohy, které vedou na Diofantické rovnice jsou velice složité, a žádný "vzoreček" neexistuje.

Nevím teda na jakou střední školu jste chodil vy, Tomáši, ale já jsem za 4 roky na gymplu nikdy neslyšel o nějaké Diofantické rovnici. Nechápu proč to dělat takhle složitě.

1. způsob = 1 x 5 Kč + 16 x 2 Kč
2. způsob = 3 x 5 Kč + 11 x 2 Kč
3. způsob = 5 x 5 Kč + 6 x 2 Kč
4. způsob = 7 x 5 Kč + 1 x 2 Kč

Např.: 2 x 5 Kč být nemůže jelikož zbylých 27 Kč dvou korunami nezaplatíte atd. atd.

To znamená, že si musíte vzít vždy tolik pěti korun, aby zbylo sudé číslo, které jste schopni doplatit dvou korunami.

Není tedy vůbec potřeba to řešit zdlouhavě přes rovnici, stačí jenom zapojit mozek a pár vteřin času :)

Ahoj Jakube, taky na gympl a Diofantickou rovnici jsem viděl :-)

Nutno říct, že vím o studentech, kteří se v rámci přípravy na MO učí i teorii čísel a zvládli by výpočet druhým způsobem.

Na některých školách, bohužel, učitelé nejdou za rámec osnov, já měl na učitele naopak štěstí.

A proč to dělat složitě?

Protože se Pavel ptal, jak to spočítat "matematicky".

Diofantické rovnice jsou třída úloh, na které stačí látka střední školy a pokud na ně jde zadání převést, víme s čím máme tu čest.

Neboli, pokud vím, že Diofantická rovnice řeší úlohu a naopak řešení úlohy dává výsledek rovnice, vím, jestli je úloha jednoduchá nebo ne. A tyhle rovnice jsou pekelně složité na výpočet.

Tohle zadání sice můžeme řešit selským rozumem, ale stačí jenom trochu zvednout hodnoty nebo přidat další mince a úloha se stává prakticky neřešitelnou. Postup pro její řešení se nazývá celočíselné lineární programování, které spadá do NP-těžkých úloh. To jsou nejsložitější problémy, jaké známe.

Z toho si můžeme odvodit, že selský rozum je správný způsob, jak úlohu řešit.

A ještě lepší je vědět, že pokud selký rozum nezabere, je stejná úloha příliš složitá.