postzegels

Opgave - CanMO 1974 vraag 6

Een onuitputbare voorraad van postzegels van 8 cent en van 15 cent zijn voorhanden. Sommige waarden kunnen met deze twee postzegels niet bereikt worden (bijvoorbeeld 7 cent, of 29 cent). Wat is het grootste onbereikbare bedrag met deze twee postzegels? Verklaar je antwoord.

Oplossing

Als we dus $x$ postzegels van $8$ cent nemen en $y$ van $15$ cent,waarbij $x,y$ natuurlijke getallen zijn, kunnen we geen brief voor $97$ cent versturen, $\frac{97}{8}$ heeft rest 1 of $97 \equiv 1 \pmod{8}$, $15 \equiv 7 \pmod{8}$, $8\equiv 0\pmod{8}$, $15y\equiv 1 \pmod{8}$ moet dus, dus moet $y\equiv 7 \pmod{8}$ en hebben we minimum $105$ cent opgeplakt, dit gaat dus niet.

Voor grotere bedragen lukt het altijd:
$$98= 6*15+8$$ $$99= 5*15 + 3*8$$ $$100=4*15 + 5*8$$ $$101= 3*15+7*8$$ $$102= 2*15 + 9*8$$ $$103=1*15 + 11*8$$ $$104= 13*8$$ $$105= 7*15,$$
voor grotere getallen kun je gewoon $8$ toevoegen bij één van bovenstaande. Het gevraagde antwoord is dus $97$.