Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this XKCD comic, a stick figure asks an NP-complete problem to order exactly 15.05 worth of appetizers out of a menu that includes the following list of prices: {2.15, 2.75, 3.35, 3.55, 4.20, 5.80}.

What is the mathematical name and procedure for this kind of problem, and how would you input something like this to WolframAlpha if possible?

NP-Complete: General solutions get you a 50% tip.

share|improve this question
6  
6  
I think this question is ok. Please consider this comment a vote against closing it. –  Srivatsan Jan 7 '12 at 14:27
    
i couldnt get the joke in the xkcd link apparently :( –  Bhargav Jan 7 '12 at 14:36
2  
Rather unfortunately, .01*IntegerPartitions[1505, All, {215, 275, 335, 355, 420, 580}] doesn't work in Alpha. –  J. M. Jan 7 '12 at 16:01
4  
The stick figure poses an instance of an NP-complete problem. NP-completeness is a property of problems (which in complexity theory is synonymous with classes of problems), not of problem instances. For every problem instance, there's a trivial polynomial-time algorithm to solve it, namely the one that simply prints the solution. –  joriki Jan 7 '12 at 16:07
show 2 more comments

1 Answer 1

up vote 10 down vote accepted

To count the number of solutions, enter series for 1/((1-x^(215/100))(1-x^(275/100))(1-x^(335/100))(1-x^(355/100))(1-x^(420/100))(1-x^(580/100))) at x=0 (or click here), then press "More Terms" about two dozen times until you get the coefficient for $x^{1505/100}=x^{301/20}$, which is $2$, so there are two solutions.

For a slightly smaller problem, you could also get the solutions themselves by entering series for 1/((1-a x^(215/100))(1-b x^(275/100))(1-c x^(335/100))(1-d x^(355/100))(1-e x^(420/100))(1-f x^(580/100))) at x=0 (or clicking here) and decoding the coefficient of $x^{1505/100}$. Unfortunately Wolfram|Alpha stops offering more terms at $x^{10}$, so the best we can do is to deduce from the coefficient $a^3d+ef$ of $x^{10}$ that there are two appetizer combinations for exactly $\$10$, namely $3$ mixed fruit and hot wings, or Mozzarella sticks and a sampler plate.

To see why this works, you can read up on the generating function for the partition function.

share|improve this answer
2  
SAGE says $(a^7+ad^2f)$ for 15$05 –  Myself Jan 7 '12 at 19:36
    
@Myself: That's a lot of mixed fruit! :-) Thanks! –  joriki Jan 7 '12 at 19:39
    
@Myself - Nice. In alternative notation, $7a = 15.05$ and $a+2d+f=15.05$, where the letters label the appetizer prices in the order they're given. –  r.e.s. Jan 8 '12 at 2:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.