11
$\begingroup$

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.

  • 6
    http://en.wikipedia.org/wiki/Knapsack_problem2012-01-07
  • 6
    I think this question is ok. Please consider this comment a vote against closing it.2012-01-07
  • 0
    i couldnt get the joke in the xkcd link apparently :(2012-01-07
  • 2
    Rather unfortunately, `.01*IntegerPartitions[1505, All, {215, 275, 335, 355, 420, 580}]` doesn't work in Alpha.2012-01-07
  • 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.2012-01-07
  • 0
    @joriki: Did you intend to write "which in complexity theory is synonymous with classes of problem instances"?2012-01-07
  • 0
    @Srivatsan: Ah, yes, that would have been much clearer :-) I guess I meant that "problems" in complexity theory is synonymous with "classes of problems" in everyday language.2012-01-07

1 Answers 1

13

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.

  • 3
    SAGE says $(a^7+ad^2f)$ for 15$052012-01-07
  • 0
    @Myself: That's a lot of mixed fruit! :-) Thanks!2012-01-07
  • 0
    @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.2012-01-08