Spiked Math Games  // Math Fail Blog  // Gauss Facts  // Spiked Math Forums  // Spiked Math Comics

# fact-002

MFT - Trivial fun - February 14, 2012
• Currently 4.6/5
• 1
• 2
• 3
• 4
• 5
Today's fact isn't really a fact, but more of a story! Math is aimed at an elementary school level.

Lol, at first I didn't even look at the numbers and just thought, that is the subset sum problem which is NP-hard, hence I didn't bother to think about it...

While it is a Subset Sum problem, and those are NP-hard, they can be solved in pseudo-polynomial time using Dynamic Programming. See standard algorithms textbooks (e.g., Cormen/Leiserson/Rivest/Stein, or Kleinberg/Tardos), Chapter on "Dynamic Programming". Since the numbers here are small, that would take basically no time. So you wouldn't need to brute force it, as Mike suggested.

I wonder whether you could sue the store if you could establish conclusively that there can never be a solution. Contests have to include ways in which the promised prizes can be allocated, as far as I know.

I'm sure as with any sweepstakes that a winning combination was possible. All the store would have to do would be to give out a few game pieces that contained numbers not divisible by 3. However, as I would imagine, these were probably rare to come by.

I kept getting a sum of 60, which made me realize that it was impossible.

So did the store ever have any pieces that weren't divisible by three? If not, that seems to be illegal to have a contest that's impossible to win. Or if not illegal, very dishonest.

Read up on Sam Loyd's "Boss" puzzle.

brilliant. i wish i had examine the numbers. you got the pie too quick !!! :)

While NP-hard, a set this small isn't difficult, and the idea that it is finding EXACTLY three makes it MUCH simpler than the full subset-sum problem ("Does ANY combination add up to X?"), because there's a lot less to check. I'll generalize it for any sum N:

First, do a sort to get the pieces in numerical order.
For each high piece "P" that is N/2 or greater, one at a time:
- Look at the pieces that are less than or equal to N-P.
- Find the sum of all 2 piece combinations, Ci, of that subset of pieces.
- Check if P+Ci = N for i = 1 to x.

Presumably, this procedure can be generalized, but as N increases or the rule is relaxed (3 pieces vs. any arbitrary number of pieces) that's what makes it NP-hard. Right?

I actually use something like this procedure at work every spring for the fiscal close, when I have to try to transfer an exact number of accounting transactions from one account to another, and I'm trying to use up exactly ALL of what remains in one budget line.

* or rather, while the number of pieces increases OR while N increases for some number of pieces. Oops.

Steve,

for large enough parameters, you will still get exponential time with your approach. Check out my response above - once you understand Dynamic Programming, you will find that it is a really beautiful way to deal with this problem whenever the individual numbers aren't too large (say, less than 1,000,000).

Trivial, all the given numbers are 0 mod 3, 50 is 2 mod 3, it's impossible.

Welcome to Spiked Math!

Hello my fellow math geeks. My name is Mike and I am the creator of Spiked Math Comics, a math comic dedicated to humor, educate and entertain the geek in you. Beware though, there might be some math involved :D

New to Spiked Math?
View the top comics.

New Feature: Browse the archives in quick view! Choose from a black, white or grey background.

Now you can discuss the comics in the

Apps

by Pablo and Leonardo

Android app
by Bryan

Available on:
Swoopy app

Other Sites: