Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- to prove: all n >= 44 are McNugget numbers.
- let M(n) be the "McNugget trace" of a McNugget number: the combination of 6, 9, and 20 which sums to n.
- base cases:
- 44 is a McNugget number: M(44) = 20 + 6 + 6 + 6 + 6.
- 45 is a McNugget number: M(45) = 9 + 9 + 9 + 6 + 6 + 6.
- 46 is a McNugget number: M(46) = 20 + 20 + 6.
- 47 is a McNugget number: M(47) = 20 + 9 + 9 + 9.
- 48 is a McNugget number: M(48) = 6 * 8.
- 49 is a McNugget number: M(49) = 20 + 20 + 9.
- inductive step:
- 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.
- 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.
- therefore, all n >= 44 are McNugget numbers.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement