posted by Jane on .
Luigi sells one size of pizza but he claims that his selection of toppings allows for :more than 4000 different choices." What is the smallest number of toppings Luigi could offer?
That depends upon the maximum number of toppings per slice. With N varieties of topping, and the total number of chosen toppings running from 0 to N, the possible number of toppings is
1 + N + N*(N-1)/2! + N(N-1)(N-2)/3! + .. + N + 1
The series continues for each N until you end up with last terms of N and 1. Try various value of N unti you exceed 4000 for the series sum.
For N = 10, the number of possibilities is
1 + 10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1 = 1024. This happens to equal 2^10. Although I have not proived it, the number of possible topping combinations with N toppings appears to ne 2^N. With 12 toppings, 4096 combinations are possible.