Ir pieejams neierobežots daudzums \(7\) un \(13\) centu pastmarku, kuras izmanto pasta sūtījumu apmaksāšanai. Diemžēl dažas summas nav iespējams apmaksāt tikai ar šīm pastmarkām (piemēram, ja sūtījums maksā \(6,\ 8\) vai \(25\) centus). Kāda ir lielākā summa, kuru nav iespējams apmaksāt izmantojot tikai šīs pastmarkas?
Parādīsim, ka \(71\) centu nav iespējams precīzi apmaksāt ar \(7\) un \(13\) centu pastmarkām. Šajā summā ir ne vairāk kā piecas \(13\) centu pastmarkas. Aplūkosim, kāda summa atkarībā no izmantoto \(13\) centu pastmarku skaita būtu jāapmaksā ar \(7\) centu pastmarkām:
| \(13\) centu pastmarku skaits |
Summa, kas apmaksāta ar \(13\) centu pastmarkām |
Summa, kas jāapmaksā ar \(7\) centu pastmarkām |
|---|---|---|
| \(0\) | \(0\) | \(71\) |
| \(1\) | \(13\) | \(58\) |
| \(2\) | \(26\) | \(45\) |
| \(3\) | \(39\) | \(32\) |
| \(4\) | \(52\) | \(19\) |
| \(5\) | \(65\) | \(6\) |
Nevienā no variantiem atlikusī summa nav \(7\) daudzkārtnis, tātad šo summu nav iespējams apmaksāt ar \(7\) centu pastmarkām. Tātad \(71\) centu nav iespējams precīzi apmaksāt ar \(7\) un \(13\) centu pastmarkām.
Pierādīsim, ka jebkuru lielāku summu ir iespējams samaksāt ar \(7\) un \(13\) centu pastmarkām.
Ievērosim, ka ja \(N\) centu apmaksāšanā ir izmantota vismaz viena \(13\) centu pastmarka, tad aizvietojot to ar divām \(7\) centu pastmarkām, varēs apmaksāt \(N+1\) centu. Šādu aizvietošanu apzīmēsim ar " \(A\) ".
Ja \(N\) centu apmaksāšanā ir izmantotas vismaz vienpadsmit \(7\) centu pastmarkas, tad aizvietojot tās ar sešām \(13\) centu pastmarkām, varēs apmaksāt \(N+1\) centu. Šādu aizvietošanu apzīmēsim ar " \(B\) ".
Ievērojam, ka \(72=1 \cdot 7+5 \cdot 13\) un
\[72 \stackrel{A}{\Rightarrow} 73 \stackrel{A}{\Rightarrow} 74 \stackrel{A}{\Rightarrow} 75 \stackrel{A}{\Rightarrow} 76 \stackrel{A}{\Rightarrow} 77 \stackrel{B}{\Rightarrow} 78.\]
Visas lielākās summas var iegūt izvēloties kādu no šīm summām un pievienojot nepieciešamo \(7\) centu pastmarku skaitu.