Enigmatic Code

Programming Enigma Puzzles

Pizza Puzzle

This puzzle is inspired by a combinatorial problem that surfaced in the Feedback section of New Scientist in early 2011. (See issues #2794 and  #2798), and was brought to my attention by Hugh Casement. [link]

Here is the puzzle:

When ordering a pizza from the Enigmatic Pizza Company you can specify the toppings on your pizza. There are 34 possible toppings to choose from, and you can have up to 11 toppings on your pizza. But you can have no more than three helpings of any individual topping.

The most basic pizza available would be one with no toppings at all. And a fully loaded veggie pizza might have 3 helpings of cherry tomatoes, 3 helpings of mixed peppers, 3 helpings of jalapeño peppers and 2 helpings of mozzarella cheese, using up all 11 toppings.

What is the total number of different pizza combinations that are available?

Advertisements

8 responses to “Pizza Puzzle

  1. Jim Randell 23 November 2016 at 9:52 am

    I looked at defining:

    choose(n, k, m)

    where:

    n = the number of values available (toppings)
    k = the number of slots to fill
    m = maximum number of times a value can be used

    so the number of different toppings for one pizza is: choose(34, 11, 3).

    I came up with the following:

    choose(n, 0, m) = 1
    choose(0, k, m) = 0 [k > 0]
    choose(n, 1, m) = n [n > 0, m > 0]

    and the general case:

    choose(n, k, m) = sum(choose(n – 1, k – i, m) for i = 0 to min(k, m))

    I don’t have a closed formula for calculating this, but it can be implemented directly as a computer program.

    The code runs in 50ms and gives us:

    choose(34, 11, 3) = 7,039,463,632

    but that’s if all slots are filled. I suppose we might put fewer than 11 toppings on.

    If we consider using only 10 of the slots:

    choose(34, 10, 3) = 1,806,739,396

    And for fewer than 10:

    choose(34, 9, 3) = 428,844,856
    choose(34, 8, 3) = 93,303,276
    choose(34, 7, 3) = 18,400,800
    choose(34, 6, 3) = 3,242,393
    choose(34, 5, 3) = 500,786
    choose(34, 4, 3) = 66,011
    choose(34, 3, 3) = 7,140
    choose(34, 2, 3) = 595
    choose(34, 1, 3) = 34
    choose(34, 0, 3) = 1

    Adding them all together:

    sum(choose(34, i, 3) for i = 0 to 11) = 9,390,568,920

    Here is the program:

    from enigma import irange, cached, arg, printf
    
    # count the number of (unordered) combinations with repetition
    # n - number of values
    # k - number of slots to fill
    # m - max number of occurrences of each value
    @cached
    def _choose(n, k, m):
      # if there are 0 slots to fill we can do that in 1 way
      if k == 0: return 1
      # if there are no values there are no ways
      if n == 0: return 0
      # if there is 1 slot to fill we can do that in n ways
      if k == 1: return n
      # otherwise we can fill 0 - m slots with the first value
      return sum(_choose(n - 1, k - i, m) for i in irange(0, min(k, m)))
    
    # if m is None, we can use as many occurrences as we like (multichoose)
    def choose(n, k, m=None):
      if m is None: m = k
      return _choose(n, k, m)
    
    # command line arguments
    N = arg(34, 0, int)
    K = arg(11, 1, int)
    M = arg( 3, 2, int)
    printf("N={N} K={K} M={M}")
    
    # find all solutions with up to K slots
    t = 0
    for k in irange(0, K):
      x = choose(N, k, M)
      printf("choose({N}, {k}, {M}) = {x}")
      t += x
    printf("total = {t}")
    

    So, if I’ve worked it out right, this is the total number of different kinds of pizza we could make.

    Solution: The total number of pizza combinations available is 9,390,568,920.

    I’d be interested to hear from anyone who can verify that this is indeed the solution, or can up with a closed formula for choose(n, m, k) (perhaps using the Inclusion-Exclusion Principle, or Generating Functions).


    The Feedback article that inspired this problem is about investigating the claim of a pizza company that “more than 1.8 billion pizza combinations” are available using this method.

    The quoted figure is very close to choose(34, 10, 3) = 1,806,739,396, which is the number of pizza combinations if exactly 10 topping options are used (but no more than 3 servings of any of the individual 34 available toppings can be used). But if we were to allow not all the slots to be used we get:

    sum(choose(34, i, 3) for i = 0 to 10) = 2,351,105,288

    There is also the additional complication of specifying a pizza as two “half-pizzas”, each of which can be specified as above.

    This would give a total number of different combinations for one pizza as:

    T(sum(choose(34, i, 3) for i = 0 to 11)) = 44,091,392,325,330,267,660

    Note that the choose(n, k, m) function with m=1 corresponds to the C(n, k) combinatorial function:

    choose(n, k, 1) = C(n, k) = n! / k!(n − k)!

    and choose(n, k, k) corresponds to the “multichoose” function:

    choose(n, k, k) = M(n, k) = C(n + k − 1, k) = (n + k − 1)! / k!(n − 1)!

  2. arthurvause 25 November 2016 at 9:39 am

    Here are two variants of a solution using generating polynomials. The first solution sums the combinations for each of 0,1,..11 toppings. The second intruduces a “no flavour” topping which can have up to 11 helpings on a pizza.

    # polynomial multiplication
    def mult(a,b):
      prod = [0]*(len(a)+len(b)-1)
      for i,v in enumerate(a):
        for j,w in enumerate(b):
          prod[i+j] += v*w
      return prod
    
    # generating polynomial 1+x+x^2+x^3
    a=[1,1,1,1]
    for i in xrange(33):
      a = mult(a,[1,1,1,1])
    print "combinations for each of 0,1,2,,11 toppings", a[:12]
    print "total combinations for 0,1,2,,11 toppings", sum(a[:12])
    
    a=[1,1,1,1]
    for i in xrange(33):
      a = mult(a,[1,1,1,1])
    # generator for a fictitious "no flavour" topping  1+x+x^2+x^3 + ... + x^11
    a = mult(a,[1]*12)  
    print "total combinations for 11 toppings, including a 'no flavour' topping", a[11]  
    
  3. Paul 25 November 2016 at 9:57 am

    They are the coefficients of the generating function (1+x+x^2+x^3)^34, which gives the following:-

    1
    34
    595
    7140
    66011
    500786
    3242393
    18400800
    93303276
    428844856
    1806739396
    7039463632
    25548426676
    86887295256
    278281163196
    842918860256
    2423475652202
    6634470805556
    17341148802846
    43380805158856
    104084976799870
    239976458448628
    532562712473226
    1139331051928416
    2352859144971660
    4696140231374136
    9069162213979428
    16963345961804176
    30758965447699060
    54114045013193176
    92439326336974716
    153431242064263328
    247603544155029095
    388721046695453966

    • Paul 25 November 2016 at 10:02 am

      MMa code to generate the list

      Column[CoefficientList[Series[(1+x+x^2+x^3)^34,{x,0,34}],x]]

      • Paul 25 November 2016 at 4:13 pm

        And in general we have the coefficients of (1+x^2 + x^3 + … x^n)^t

        where “n” is the max number of toppings and “t” is max possible toppings to choose from.

        I have tested the theory and it seems sound.

        P.C.

  4. arthurvause 27 November 2016 at 8:41 am

    By the way, the October 2012 puzzle in IBM Ponder This illustrates the use of generating polynomials.

  5. Jim Randell 27 November 2016 at 1:38 pm

    Thanks for the solutions involving generating functions. It’s not a technique I’m used to (although my initial searches did seem to indicate that it might be a way to attack this problem), but I’ve read up a bit about them and it seems to be a very useful technique.

    Below are my notes (mostly for my own benefit, but could possibly help explain the technique to someone else who is new to it too).

    If we have toppings a, b, c, …, then we can represent using up to three of topping a as:

    (a⁰ + a¹ + a² + a³)

    Similarly for all the other toppings, giving us the product:

    (a⁰ + a¹ + a² + a³)(b⁰ + b¹ + b² + b³)(c⁰ + c¹ + c² + c³)…

    which if we multiplied out the product would give us a lot of terms, each one representing a different combination of toppings for a pizza.

    So, there will be 1 term with a total of zero toppings:

    a⁰b⁰c⁰…

    and 34 terms with exactly 1 topping:

    a¹b⁰c⁰…, a⁰b¹c⁰…, a⁰b⁰c¹…, …

    and so-on until we arrive at the terms with exactly 11 toppings, for example (without the zero exponents this time):

    a³b³c³d², …

    If we can count the number of terms with exponents that sum to 11, we would find the number of different pizzas with exactly 11 toppings.

    By setting x = a = b = c = … we can consider the polynominal:

    (x⁰ + x¹ + x² + x³)³⁴

    Multiplying this out will give us the same number of terms of x^n as there are pizzas with exactly n toppings.

    So we can find the number of pizzas with exactly 11 toppings by determining the co-efficient of x¹¹ in the product.

    At this point we can turn to a computer to do the tedious multiplication for us. We can consider a polynomial to be represented by a list, with element 0 containing the co-efficient of x⁰, element 1 containing the co-efficient of and so forth. For example, we would represent (1 + 5x − 7x² + 13x³) as [1, 5, −7, 13].

    We can then write code to multiply out two such polynomials (which gives us code very similar to that posted by Arthur above):

    from enigma import printf
    
    # mutliply two polynomials
    def poly_mul(p, q):
      r = [0] * (len(p) + len(q) - 1)
      for (j, b) in enumerate(q):
        for (i, a) in enumerate(p):
          r[i + j] += a * b
      return r
    
    # raise a polynomial to a positive integer power
    def poly_pow(p, n):
      r = [1]
      for _ in range(n):
        r = poly_mul(r, p)
      return r
    
    # consider the polynomial (x^0 + x^1 + x^2 + x^3)
    p = [1, 1, 1, 1]
    
    # raise it to the 34th power
    r = poly_pow(p, 34)
    
    # the coefficient of x^11 gives us the number of pizzas with exactly
    # 11 toppings
    printf("{n} pizzas with exactly 11 toppings", n=r[11])
    
    # summing the first 12 coefficients gives us the number of pizzas with
    # up to 11 toppings
    printf("{n} pizzas with up to 11 toppings", n=sum(r[:12]))
    

    If the restrictions of toppings were less uniform (e.g. you were only allowed two helpings of some toppings, but up to four of others), the generating polynomial could be adjusted accordingly.

    The same approach can be used for other combination based problems.

    For example, determining how many different ways there are to make change for £1 given 1p, 2p, 5p, 10p, 20p and 50p coins.

    We can consider multiplying together the following polynomials (one for each denomination of coin):

    (x^0 + x^1 + x^2 + … + x^100)
    (x^0 + x^2 + x^4 + … + x^100)
    (x^0 + x^5 + x^10 + … + x^100)
    (x^0 + x^10 + x^20 + … + x^100)
    (x^0 + x^20 + x^40 + … + x^100)
    (x^0 + x^50 + x^100)

    and then determine the coefficient of x^100 to give us the number of ways to give change for £1.

    # make a polynomial from (exponent, coefficient) pairs
    # (we can use enumerate() to reverse the process)
    def poly_new(ps):
      p = []
      for (e, c) in ps:
        if c == 0: continue
        x = e + 1 - len(p)
        if x > 0: p.extend([0] * x)
        p[e] += c
      return p
    
    # multiply together a collection of polynomials
    def poly_multiply(p, *qs):
      r = p
      for q in qs:
        r = poly_mul(r, q)
      return r
    
    
    # denominations and amount
    ds = (1, 2, 5, 10, 20, 50)
    amount = 100
    
    ps = list(poly_new((n, 1) for n in irange(0, amount, step=d)) for d in ds)
    r = poly_multiply(*ps)
    
    printf("{n} ways to make change for {amount}p", n=r[amount])
    

    I shall add some routines to the enigma.py library to make it easier to use this technique.

    • Tessa Fullwood 12 December 2016 at 8:42 pm

      This way calculates the combinations for each set of n toppings, with n <= 11.

      For a set of n toppings, n<=11, there are C(34,n) ways of assembling a set of toppings.

      If there is a single helping of each topping then this gives 1 combination. If one topping has 2 helpings then this adds C(n, 1) combinations. If two toppings have 2 helpings then this results in C(n,2) extra combinations. If two toppings have 2 helpings and one topping has 3 helpings, then this adds C(n,2) * C(n-2,1) combinations.

      These can be extended, using the limit, that total helpings do not exceed 11. The limit applies for 4<= n <= 11.

      Totalling up the added combinations with n from 1 to 11, multiplied by the number of ways of assembling a set also results in the total above of 9390568920.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: