• API
• FAQ
• Tools
• Archive
SHARE
TWEET  Untitled a guest Feb 7th, 2015 24 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top