Advertisement
Guest User

Untitled

a guest
Feb 7th, 2015
273
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.76 KB | None | 0 0
  1. to prove: all n >= 44 are McNugget numbers.
  2.  
  3. let M(n) be the "McNugget trace" of a McNugget number: the combination of 6, 9, and 20 which sums to n.
  4.  
  5. base cases:
  6. 44 is a McNugget number: M(44) = 20 + 6 + 6 + 6 + 6.
  7. 45 is a McNugget number: M(45) = 9 + 9 + 9 + 6 + 6 + 6.
  8. 46 is a McNugget number: M(46) = 20 + 20 + 6.
  9. 47 is a McNugget number: M(47) = 20 + 9 + 9 + 9.
  10. 48 is a McNugget number: M(48) = 6 * 8.
  11. 49 is a McNugget number: M(49) = 20 + 20 + 9.
  12.  
  13. inductive step:
  14. if m is a McNugget number, then n = m + 6 * k (for all k >= 0) is a McNugget number: M(n) = M(m) + 6 * k.
  15.  
  16. all n >= 50 are congruent to 44, 45, 46, 47, 48, or 49 (modulo 6), and thus can be written as n = m + 6 * k where m is one of the base cases.
  17. therefore, all n >= 44 are McNugget numbers.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement