Side 1 av 1
Chicken McNugget problem
Lagt inn: 31/01-2010 00:15
av 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?
Lagt inn: 31/01-2010 00:27
av 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. =)
Lagt inn: 31/01-2010 11:05
av arnulf
Takk skal du ha! (: