24 October 2008

Will Hunting, is that you?

Mysteries: Was Palin's $150,000 Even Actually Spent on Clothes?

Consider also the $4,902.45 charge at Atelier New York, a high-end men’s store, presumably for Ms. Palin’s husband, Todd, the famous First Dude.

Karlo Steel, an owner there, said he had gone through the store’s receipts for September, twice, and found no sales that matched that amount, nor any combination of sales that added up to the total."
Really, Karlo Steel? You solved the subset sum problem?

(Via The DCeiver.)


  1. RE: Subset sum solution

    You are assuming that the store had a large number of sales that day. They may have only had a dozen or so receipts.

  2. Well, true, I am making assumptions about the number of sales. But the shopkeeper claims to have checked the receipts for the entire month, which I'll really low-ball at one sale per day. The naive algorithm, O(2^n), gives on the order of a billion possibilities to check. There's a better algorithm that runs in O(n*2^(n/2)), but that still gives us 983040 possibilities.

    My memory is shaky on this, but I think there's also a dynamic programming algorithm that is exponential in the number of bits needed to express the sum of the whole set. This should also produce hundreds of thousands of iterations, though we need more assumptions about the total monthly revenue of the store to be sure. Regardless, I suspect that dynamic programming is above Mr Steel.