How would you input xkcd.com/287 into WolframAlpha?

1.1k Views Asked by At

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.

1

There are 1 best solutions below

3
On BEST ANSWER

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.