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.

  • 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.

  • 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