Reply
Wed 22 Sep, 2004 06:06 pm
A local salad bar has a 30 item line up. The owner advertises over a billion combinations.
How many combinations are there on this salad bar?
A patron can take a salad of 1 to 30 items, the order that items are added does not matter, so consider tomatoes and lettuce the same as lettuce and tomatoes, which would only count as one combination.
It's the 30th item that puts it over a billion. Adding the last item doubles the number of combinations.
I think the answer would be 2^30 - 1 = 1,073,741,823.
You have to subtract 1 because otherwise you are counting the null set which would be an empty plate.
Actually on second thought I'm wrong.
Hmmm.
I'm counting lettuce and tomatoes as seperate from tomatoes and lettuce.
No you're not. You got it right. For every combination, each item is either included (1) or not (0). So there are 2^N combinations. In this case, one of them is invalid: no ingredients.
That was the same count I had.
Actually on third thought I agree with you guys.
I was thinking,
and the combinations may be even more
if you consider various weights of each item could be a diferant combination.
Item not there
1/4 pound
1/2 pound
3/4 pound
1 pound
Just a few more.
5^30 - 1 (931,322,574,615,478,515,624)
vs.
2^30 - 1 (1,073,741,823).
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace