- 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.

SHARE

TWEET

# Untitled

a guest
Feb 7th, 2015
17
Never

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.