# Scotty's Pizzeria claims to offer 8000 different large pizzas. What is the smallest number of toppings Scotty must offer?This is permutations and combinations. I dont know how you can apply that in...

Scotty's Pizzeria claims to offer 8000 different large pizzas. What is the smallest number of toppings Scotty must offer?

This is permutations and combinations. I dont know how you can apply that in this question! PLEASE HELP!

*print*Print*list*Cite

### 2 Answers

8000 different pizzas means that they offer different combination of topping on each pizza. They need to have a minimum of n veriety of topping to make up at least 8000 different pizza.

toppings would be r1, r2, r3,....,rn

of course topings could not be counted more thatn once in each pizza where order does not matter, so you are looking at a Combination rule where n is the the things to choose from.

the question did not specify how many topings the combination includes so we need to sum all combinations from one topping, two toppings,...., n toppings

the formula would be :

nC1+nC2+nC3+...+nCn= 8000

but,

nC0+ nC1+....+nCn = 2^n

1+ nc1+nC2+nC3+....+nCn= 2^n

nC1+nC2+...+nCn= 2^n - 1 = 8000

2^n = 8001

but 2^13 = 8192

then they have to have at least 13 toppings to exceed the 8000 veriety they claim they have.

Approximately 8000 is different varieties offered could be a combination of different n basic types. From these n basic types we could make a combination one type, combianation of 2 types, combination of 3 types etc.

So the total different types of combinations that could be offered is a sum like:

nC1+nC2+nC3+nC4+......+nCn = (1+1)^n = 8000.Or

2^n -1 = 8001, as nC0+nC1+nC2+nC3+....nCn = (1+1)^n = 2^n and nC0 = 1

But 2^13 = 8192.

So n = 13 is the minimum different types Scotty's could offer.