### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,820 hits

Advertisements

Programming Enigma Puzzles

23 November 2016

Posted by on 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

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.Enigmatic Pizza CompanyThe 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

%d bloggers like this:

I looked at defining:

where:

so the number of different toppings for one pizza is:

choose(34, 11, 3).I came up with the following:

and the general case:

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:

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:

And for fewer than 10:

Adding them all together:

Here is the program:

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

Feedbackarticle 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: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:

Note that the

choose(n, k, m)function withm=1corresponds to theC(n, k)combinatorial function:and

choose(n, k, k)corresponds to the “multichoose” function: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.

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

MMa code to generate the list

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

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.

By the way, the

October 2012 puzzlein IBM Ponder This illustrates the use of generating polynomials.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 toppingaas:Similarly for all the other toppings, giving us the product:

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:

and 34 terms with exactly 1 topping:

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

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:Multiplying this out will give us the same number of terms of

x^nas there are pizzas with exactlyntoppings.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 ofx¹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):

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):

and then determine the coefficient of

x^100to give us the number of ways to give change for £1.I shall add some routines to the

enigma.pylibrary to make it easier to use this technique.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.