Latvijā, tāpat kā visās eirozonas valstīs, apgrozībā ir \(1\); \(2\); \(5\); \(10\); \(20\) un \(50\) centu monētas. Pieņemsim, ka ir zināma no šīm monētām izveidotā naudas summa \(S\) un izmantoto monētu skaits \(M\). Daudzos gadījumos, zinot \(S\) un \(M\) vērtības, var viennozīmīgi noteikt izmantoto monētu komplektu. Piemēram, ja \(S=7\) un \(M=3\), tad ir izmantota viena piecu un divas viena centa monētas un citu variantu nav.
Kāda ir mazākā \(S\) vērtība, kurai var atrast tādu \(M\) vērtību, ka, zinot \(S\) un \(M\) vērtības, izmantoto monētu komplektu viennozīmīgi nav iespējams noteikt?
Mazākā \(S\) vērtība ir \(8\), tai atbilst \(M=4\) un atšķirīgie monētu komplekti ir \(5+1+1+1\) un \(2+2+2+2\).
Pamatosim, ka mazākām \(S\) vērtībām šāda \(M\) vērtība neeksistē. Ievērosim, ka nevar izveidot summu \(S\), ja monētu skaits \(M\) ir lielāks nekā \(S\). Tātad pietiek apskatīt visus gadījumus, kad \(M \leq S < 8\).
Ja, piemēram \(S=7\) un \(M=7\), tad \(7 = 1+1+1+1+1+1+1\) un nav citu veidu, kā samaksāt summu 7 ar 7 monētām. Arī citiem \(S\) un \(M\) samaksāšanas veids ir viens vienīgs (vai neeksistē vispār).
| \(S\) | \(M=1\) | \(M=2\) | \(M=3\) | \(M=4\) | \(M=5\) | \(M=6\) |
|---|---|---|---|---|---|---|
| \(1\) | \(1\) | nav | nav | nav | nav | nav |
| \(2\) | \(2\) | \(1+1\) | nav | nav | nav | nav |
| \(3\) | nav | \(2+1\) | \(1+1+1\) | nav | nav | nav |
| \(4\) | nav | \(2+2\) | \(2+1+1\) | \(1+1+1+1\) | nav | nav |
| \(5\) | \(5\) | nav | \(2+2+1\) | \(2+1+1+1\) | \(1+1+1+1+1\) | nav |
| \(6\) | nav | \(5+1\) | \(2+2+2\) | \(2+2+1+1\) | \(2+1+1+1+1\) | \(1+1+1+1+1+1\) |
| \(7\) | nav | \(5+2\) | \(5+1+1\) | \(2+2+2+1\) | \(2+2+1+1+1\) | \(2+1+1+1+1+1\) |
Visos aplūkotajos gadījumos saderīgos \(S\) un \(M\) pāros monētu komplektu varēja noteikt viennozīmīgi, tādēļ \(S=8\) ir mazākā iespējamā \(S\) vērtība.