I don’t think this is right. For p = 2, you get 2/3. For p = 3 you get 3.375.
OK, I wrote the code to explicitly count the number of pizzas, and it’s 1330, just like I said. I’ve posted my code below for review (and yes, I know that the left pointer is wasted space, but for a program like this, who cares?).
class TreeNode
{
public:
TreeNode();
virtual ~TreeNode();
TreeNode* GetLeft() { return m_Left; }
TreeNode* GetRight() { return m_Right; }
void SetLeft( TreeNode* Left ) { m_Left = Left; }
void SetRight( TreeNode* Right ) { m_Right = Right; }
void GetValue( int& First, int& Second, int& Third );
void SetValue( int First, int Second, int Third );
void Insert( int First, int Second, int Third );
int GetCount();
private:
int m_First;
int m_Second;
int m_Third;
TreeNode* m_Left;
TreeNode* m_Right;
bool m_Set;
};
class Tree
{
public:
Tree();
virtual ~Tree();
int GetCount();
void Insert( int First, int Second, int Third );
private:
TreeNode* m_Root;
};
TreeNode::TreeNode() :
m_First( 0 ),
m_Second( 0 ),
m_Third( 0 ),
m_Left( 0 ),
m_Right( 0 ),
m_Set( false )
{
}
TreeNode::~TreeNode()
{
if ( m_Left )
delete m_Left;
if ( m_Right )
delete m_Right;
}
int TreeNode::GetCount()
{
return 1 + ( m_Left ? m_Left->GetCount() : 0 ) + ( m_Right ? m_Right->GetCount() : 0 );
}
void TreeNode::GetValue( int& First, int& Second, int& Third )
{
First = m_First;
Second = m_Second;
Third = m_Third;
}
void TreeNode::SetValue( int First, int Second, int Third )
{
m_First = First;
m_Second = Second;
m_Third = Third;
}
void TreeNode::Insert( int First, int Second, int Third )
{
if ( !m_Set )
{
SetValue( First, Second, Third );
m_Set = true;
return;
}
bool Left = true;
if ( First == m_First )
if ( Second == m_Second )
if ( Third == m_Third )
return;
else if ( Third > m_Third )
Left = false;
else if ( Second > m_Second )
Left = false;
else if ( First > m_First )
Left = false;
if ( Left )
{
if ( !m_Left )
m_Left = new TreeNode;
if ( m_Left )
m_Left->Insert( First, Second, Third );
}
else
{
if ( !m_Right )
m_Right = new TreeNode;
if ( m_Right )
m_Right->Insert( First, Second, Third );
}
}
Tree::Tree() :
m_Root( 0 )
{
}
Tree::~Tree()
{
if ( m_Root )
delete m_Root;
}
int Tree::GetCount()
{
return ( m_Root ? m_Root->GetCount() : 0 );
}
void Tree::Insert( int First, int Second, int Third )
{
int temp = 0;
int A[3] = { First, Second, Third };
for ( int i = 0; i < 3; ++i )
{
for ( int j = i + 1; j < 3; ++j )
{
if ( A* > A[j] )
{
temp = A*;
A* = A[j];
A[j] = temp;
}
}
}
if ( !m_Root )
m_Root = new TreeNode;
if ( m_Root )
m_Root->Insert( A[0], A[1], A[2] );
}
int main()
{
int toppings = 18;
Tree T;
// 3 toppings
for ( int i = 0; i < toppings; ++i )
for ( int j = 0; j < toppings; ++j )
for ( int k = 0; k < toppings; ++k )
T.Insert( i, j, k );
// 2 toppings
for ( i = 0; i < toppings; ++i )
for ( int j = 0; j < toppings; ++j )
T.Insert( i, j, -1 );
// 1 topping
for ( i = 0; i < toppings; ++i )
T.Insert( i, -1, -1 );
// 0 toppings
T.Insert( -1, -1, -1 );
int Count = T.GetCount();
return 0;
}
Yet another reason why I love the Straight Dope.
No, it isn’t. If you don’t allow repetitions, the number is [sub]p[/sub]C[sub]4[/sub], which works out to be p(p - 1)(p - 2)(p - 3)/4!, which is always an integer.
For no repetitions, the number is [sub]p + 3[/sub]C[sub]4[/sub], which is equal to p(p[sup]2[/sup] - 1)(p[sup]2[/sup] - 4)(p[sup]2[/sup] - 9)/4!. Again, that’s always an integer.
Oops. [sub]p + 3[/sub]C[sub]4[/sub] = p(p + 1)(p + 2)(p + 3)/4!, not the monster I gave earlier.
With p = 1330, that’s equal to 3,143,142,497,880.
:smack:
Forgot to divide by 4! again. It’s really 130,964,270,745.
I ran the code for p = 17 and got 1140. Adding the 7 specialty pizzas gives 1147, so I think we’re in agreement on counting toppings. And your formula for counting pizza combinations, p(p + 1)(p + 2)(p + 3)/4! is also right, I think. It works for p = 1, 2 or 5, which is good enough for me[sup]*[/sup]. I thought that you had said that the formula was p[sup]4[/sup]/4!, which does not work.
So, following from your logic as I understand it, if I take rfgdxm’s numbers that there are only 17 available toppings for this deal, along with the 7 specialty pizzas, and we allow an order to be 1, 2, 3, or 4 pizzas, there would be [sub]1150[/sub]C[sub]4[/sub] + [sub]1149[/sub]C[sub]3[/sub] + [sub]1148[/sub]C[sub]2[/sub] + 1147 = 72,748,465,824 different orders.
[sup]*[/sup]Mathematician’s proof that all odd numbers are prime: “1 is prime, 3 is prime, 5 is prime, 7 is prime, while the rest can be proved by induction and is left as an excercise for the reader.”
I don’t think we’re justified in assuming no duplicate pizzas. If one person wants meat and another wants vegetables, then you could just order half-and-half, true… But what if you have four people, and two want meat, one wants veggies, and one wants Hawaiian? That would have to be a 4forAll, and it has a duplicate.
Meanwhile, Punoqllads, to finish the joke:
Physicist’s proof that all odd numbers are prime: 3 is prime, 5 is prime, 7 is prime, 9 is an experimental error, 11 is prime, 13 is prime…
Engineer’s proof that all odd numbers are prime: 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime…
Just for the record, I chose my original assumptions so that I would get a lower bound on the number of combinations (barring any Occam’s-razor-defying constraints in the problem.) Since this lower bound was much bigger than Ms. Simpson’s number, the question in the OP was answered. (“No.”)
Anyway, carry on…
Good point. So what you need to do is exclude all combinations which include 2 of one pizza and 2 of another. I, however, have no idea how to do that.
ultrafilter’s formula does take into account the chance of a duplicate pizza. In fact, for p < 4, duplicate pizzas must occur.
The generalization appearing in print, possibly. Real mathematicians were calling out the advertizers of the Rubik’s Cube almost as soon as it was produced for their error.
For those of you who don’t already know, it was roughly on the order of “McDonald’s: More than 2 served.”