PS2: Problems 1, 2 » Solutions

[aranthe]

Here are the solutions to problems 1 and 2. I'll be posting 3/4 as soon as I have it annotated.

PS 2: Problem 1

# Initialize configuration variables
coefficients = 6, 9, 20
mcnuggets = range( 50, 56 )
terms = len(coefficients)
combos = [] # Holds list of combinations.

a = 0 # coefficient: 6
b = 0 # coefficient: 9
c = 0 # coefficient: 20

# Loop through the mcnuggets range.
for n in mcnuggets:

    ranges = [] # Holds test ranges.

    # Create test ranges for the coefficients for this value of n.
    for i in range(0, terms):
        limit =  int( n / coefficients[i] ) + 1
        i_range = range( 0, limit )
        ranges.append(i_range)

    n_combos = [] # Holds all combos for a given n

    # Loop through the test range.
    for a in ranges[0]:
        for b in ranges[1]:
            for c in ranges[2]:

                # Check to see if the sum of the terms is equal to n. 
                if (a*coefficients[0]) + (b*coefficients[1]) + (c*coefficients[2]) == n:

                    # If so, create an array of this combination.
                    combo = [ a, b, c ]

                    # Append it to the collection of combos for this n.
                    n_combos.append(combo)

    #Print combos for this n.
    print 'For n = ', n
    print 'Combos:', n_combos

PS 2: Problem 2

Theorem:If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some x, then it is possible to buy any number of McNuggets >= x, given that McNuggets come in 6, 9 and 20 packs.

Explain, in English, why this theorem is true.

The key is in the given: The smallest coefficient is 6. Once you find solutions for six consecutive amounts, every amount beyond the last one can be derived by adding 6-packs to one of the consecutive solutions.

In the abstract, the minimum number of consecutive solutions required to insure that every subsequent number has a solution is equal to the smallest coefficient of the terms.