Atrisinājums

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.

Atrisinājums

Šķirojam atkarībā no tā, cik \(13\) centu pastmarkas lietotas

• \(0\cdot{}13 + 7a\) - dalot ar \(7\), atlikums ir \(0\)
• \(1\cdot{}13 + 7a\) - dalot ar \(7\), atlikums ir \(6\)
• \(2\cdot{}13 + 7a\) - dalot ar \(7\), atlikums ir \(5\)
• \(3\cdot{}13 + 7a\) - dalot ar \(7\), atlikums ir \(4\)
• \(4\cdot{}13 + 7a\) - dalot ar \(7\), atlikums ir \(3\)
• \(5\cdot{}13 + 7a\) - dalot ar \(7\), atlikums ir \(2\)
• \(6\cdot{}13 + 7a\) - dalot ar \(7\), atlikums ir \(1\)

Secinājums: Lai nomaksātu \(8, 15, 22, 29, 36, 43, 50, 57, 64, 71, 78, \ldots\) centus, vajag vismaz sešas \(13\) centu markas. Mazākā šāda summa ir \(6\cdot{}13 = 78\).
Tātad summu \(71\), kas šajā virknē ir tieši pirms \(78\) (un arī dod atlikumu \(1\), dalot ar \(7\)), nevarēs nomaksāt, jo, lietojot mazāk par sešām \(13\)-centu markām, nevar iegūt atlikumu \(1\), dalot ar \(7\).