Mathematicator
Kombinace
Ahoj,



prosím o radu, kolika způsoby lze zaplatit částku 37 Kč, pouze mincemi v hodnotě 2 a 5 Kč. Nemohu na to přijít, vím že výsledek je 4, ale jak k němu přijít matematickým způsobem. Díky
Autor: Pavel Š. | Poslední aktivita: 9. 06. 2017 19:57 | Zobrazeno 238x
ikonka Tomáš B. | 8. 06. 2017 1:50

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.
ikonka Jakub K. | 9. 06. 2017 17:28

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 :)
ikonka Tomáš B. | 9. 06. 2017 19:57

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á.
Co si o tom myslíte vy?
Názory mohou psát jen přihlášení uživatelé. Pokud chcete napsat svůj názor, tak se prosím přihlašte z hlavní strany webu.
Informace
Toto je pouze testovací verze fóra a nemusí vždy fungovat správně, nicméně by základní funkčnost již měla být hotová. Budu rád za nahlášení jakékoli chyby a nápadů na zlepšení. V tomto pravém menu již brzy budou další doplňující ovládací prvky, které můžete navrhnout.


Mathematicator 2017 | Provozuje Marek Valášek | Technicky zajišťuje Jan Barášek | Obchodní podmínky