Chicken McNugget problem

[arnulf]

At McDonalds you can order Chicken McNuggets in boxes of 6, 9, and 20. What is the largest number such that you can not order any combination of the above to achieve exactly the number you want?

[Austad]

43

EDIT: Glemte at du sikkert vil ha en forklaring også.

Ved å kjøpe en pakke med 6 eller 9 mcnuggets vil man kunne få et antall mcnuggets på formen 3k, k>=2. 20 er på formen 3k+2 og dermed kan vi ved kjøp av en 20-pakning og en 6pakning/9-pakning oppnå alle antall mcnuggets på formen 3k+2>=26. Ved kjøp av av to 20-pakninger oppnår vi alle antall på formen 3k+1 hvis antallet er større enn 46 (2*20). Nå er det åpenbart at 43 er det største tallet man ikke kan oppnå, fordi det er det største tallet på formen 3k+1 som er under 46. =)

[arnulf]

Takk skal du ha! (: