Miķelis ir izgudrojis spēli, kurā nepieciešama spēļu nauda - miķelīši. No \(1,\ 2,\ 3,\ 5,\ 10,\ 20,\ 25\) un \(50\) miķelīšu naudaszīmēm Miķelis grib izvēlēties četru veidu naudaszīmes tā, lai jebkuru summu no \(1\) līdz \(70\) miķelīšem varētu izveidot, izmantojot ne vairāk kā sešas banknotes. Atrast vienu šādu četru naudaszīmju komplektu!
Miķelim jāizvēlas naudaszīmes \(1,\ 3,\ 10\) un \(25\). Ievērojam, ka visas summas līdz \(4\) var iegūt ar ne vairāk kā divām banknotēm un visas summas no \(5\) līdz \(9\) - ar ne vairāk kā četrām banknotēm (pie tam četras banknotes vajadzīgas tikai summai \(8\)). Tātad visas summas no \(10\) līdz \(19\) var iegūt ar ne vairāk kā piecām banknotēm kā \(x+10\), kur \(0 \leq x \leq 9\), pie tam piecas banknotes vajadzīgas tikai, lai iegūtu summu \(18\). Visas summas no \(20\) līdz \(24\) var iegūt ar ne vairāk kā četrām banknotēm kā \(x+10+10\), kur \(0 \leq x \leq 4\).
\(1=1\)
\(2=1+1\)
\(3=3\)
\(4=1+3\)
\(5=1+1+3\)
\(6=3+3\)
\(7=1+3+3\)
\(8=1+1+3+3=3+3+3\)
\(9=18=1+1+3+3+10\)
\(10=10\)
\(11=1+10\)
\(12=1+1+10\)
\(13=3+10\)
\(14=1+3+10\)
\(15=1+1+3+10\)
\(16=3+3+10\)
\(17=1+3+3+10\)
\(18=1+1+3+3+10\)
\(19=3+3+3+10\)
\(20=10+10\)
\(21=1+10+10\)
\(22=1+1+10+10\)
\(23=3+10+10\)
\(24=1+3+10+10\)
Tad visas pārējās summas ar ne vairāk kā sešām banknotēm var iegūt kā \(x+25\) vai \(x+25+25\), kur \(0 \leq x<24\), izņemot summu \(68\), ko var iegūt kā \(68=25+10+10+10+10+3\).
Piezīme. Ar naudaszīmēm \(1,\ 3,\ 10\) un \(25\) var izveidot jebkuru summu no \(1\) līdz \(91\). Nākamais labākais komplekts ir \(1,\ 2,\ 10,\ 25\), bet ar to var izveidot summas no \(1\) līdz \(67\).