A Simple Math Puzzle

Give the Comptroller the day off and tell Millie to start again. All those sales invoices should have been credited to sales, except for the 'credit' notes which should be debited to sales. You have no idea how much each person owes you, and the auditor is going to give you so much grief over the slush fund entry, that it's worth paying dear Mildred overtime.

Either that, or create a phantom customer and stick the 300K in there. One entry, two beer please.

Would you fly out of the country?

 

I don't think she has to back anything out of Receivables. She just has to take the money out of the CEO slush fund and put that back into Receivables, which should have gotten the whole million to begin with.

Disclaimer: I know nothing about accounting, and really don't know what I'm talking about here. But if a million was supposed to go into receivables, and instead only 700 K went there, and the other 300 K went into the slush fund, all you gotta do is take the 300 K out of the slush fund and put it back into receivables where it belonged in the first place. No?

 

"Given as set of 100 integers, find every possible subset which sums to 300,000." Since I didn't state positive integers, there can be both positive and negative numbers in the set of 100.

Not being an elegant person, I can't think of an elegant solution. I can find a brute force solution though. Just form every combination of 1..99 numbers and sum them. I think that would be:

1 + 100 + 100!/(98!)(2!) + 100!/(97!)(3!) + 100!/(96!)(4!) + ...

combinations sets to test.

 

<div class='quotetop'>QUOTE(airportkid @ May 24 2007, 06:34 PM) [snapback]449497[/snapback]</div>

First you tell us it's "A simple math puzzle," and now you tell us it's "apparently, very difficult."

But now I have another question: If the issue is that a mistake was made, how come you're trying to cover it up by finding some arbitrary set of entries that happen to add up to the right amount so you can diddle with them? Why not just say a mistake was made, enter a note to that effect, and then move the incorrectly-entered items to where they belong?

Okay, so the point is it's a math puzzle. With no information about any of the numbers, find a sub-set that adds up to 300,000.

I give up.

I'm reminded of the joke where you ask someone "What's one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one and one?"

It doesn't work in writing because you can count the "one"s. But if you say it really fast they can't keep track and then you can tell them they can't even do simple math.

And aren't slush funds shady, if not illegal, by definition?

 

Here's a simple, somewhat elegant solution - only fit for a computer to implement, though.

First, select a random, evenly distributed subset of numbers that "comes close" to the target. It's important that this subset be evenly distributed across the entire range of numbers.

Next, create a grid where the subset, plus 0, is on top, and the non-subset, plus 0, is on the side, and fill in the difference between the values in the grid.

Now, pick a random subset of numbers from the grid, such that no two numbers comes from the same row or column, with an exception for the 0 row and column (since that represents removing or adding a number).

Finally, you recurse along this method, each time creating your grid based on the new subset. Due to the element of randomness, you should reach a situation where the target number is in the grid, providing you with your final solution. While it is possible that this method could take a very long time, on average it should be fairly quick.

As an example, lets take the following 10 numbers and try to make 30:
-5, -3, -2, 2, 5, 6, 8, 9, 12, 16

The total number of possible combinations to try would be 10!, or 3,628,800.

Random subset: -5, -2, 5, 6, 9, 16 = 29
New goal: 1
Grid:
0 -5 -2 5 6 9 16
0 5 2 -5 -6 -9 -16
-3 -3 2 -1 -8 -9 -12 -19
2 2 7 4 -3 -4 -7 -14
8 8 13 10 3 2 -1 -8
12 12 17 14 7 6 3 -4

random subset: (5, 0), (-2, 2), (9, 12) = 2
New goal: -1
Grid:
0 -5 2 6 12 16
0 5 -2 -6 -12 -16
-3 -3 2 -5 -9 -15 -19
-2 -2 3 -4 -8 -14 -18
5 5 10 3 -1 -7 -11
8 8 13 6 2 -4 -8
9 9 14 7 3 -3 -7

From this, we can see clearly the solution: (6, 5), giving us a final solution of: -5, 2, 5, 12, 16 this may not be the solution we would come up with instinctively, but it works!

 

I'd export the whole set of entries, pull them into excel, and make the computer sum up all the possible combinations. If there's an answer, excel can find it

EDIT: also known as brute force for excel users =)

 

This question reminds me a lot of the graph problems i studied back in school... I would think there's a solution similar to Dijkstra’s Algorithm... it'll take a bit of hard thinking to figure something out, though.

 

Here's your elegant solution:

Look at this as a least significant digit problem. Sort the values by their least significant digit (then the second, then the third, etc). Think of these now as 10 different buckets, each with a different significant digit 0-9.

You've just reduced your search space from 100 to 10... look for combinations of these 10 buckets that add up to the desired least significant digit, ignoring (for now) carryover. Start with combinations of 2, then three, then 4, etc.

For each combination, you then have a smaller subset of the total to search. When you start with 2, you'll have two lists to chose from. take each value pairwise and see if it's a match. In this way, you can immediately cut your search down in size from a brute force method by an approximate factor of 10 (assuming an even distribution).

A similar method of further grouping and classifying further down the line can be applied to further reduce your search space.

This would still require quite a bit of computation, but if it really can reduce the run time by this large a factor, it would reduce weeks down to days, days down to hours, and hours down to minutes.

*edit*
I just realized i forgot negative numbers. For those, factor them into the bucket that would represent 10-the digit in question... so -10,304 would be factored into bucket 6 for the least significant digit. This way when it's matched in with something, you'll end up with something like 4-4 = 0 instead of 4+6 = 10

 

For those wondering, the inspiration for this method came from a common sorting algorithm called radix sort: http://en.wikipedia.org/wiki/Radix_sort

 

I tried to see the sense of humour, but I took it as an accounting problem. I knew it wasn't simple, because 100 entries have to be corrected for the accounts receivable susidiary ledger to be accurate. I should have known that an elegant, creative, sexy accountant with a well-developed funny bone was only a fantasy. B)

 

as an added "speed factor" to my above solution, you could start by adding the highest values in each bucket for a given set and see if it's even possible to get up to your desired value, bailing out if it's not, saving you a large number of searches. In a similar way, you could then compare the summation of the lowest values to give you a range to ensure that your range covers the target... if not, then bail and move on to the next set of buckets.

 

It's too bad http://www.buyyourfriendadrink.com is only available in NYC right now - it would save you a flight :lol:

As far as beer goes, the darker the better

 

Okay. Well, in the spirit of the problem, here's my one last attempt at what I hope might be the best solution: Burn the accounting books, shred the backup hard drives to cover your trail, convert the whole million into 20-dollar bills (harder to trace than 100's) and retire to Playa del Carmen.

 

How'd it work out for you?

 

If this is real life (and you're not going for mathematical efficiency), then here's some working code that finds the combination of values equalling the total specified in the desiredAmount variable.

It's essentially just a brute force method using recursion. I'm sure it can be algorithmically optimized, but it will get the job done in milliseconds.

If you have no idea how to read/compile this code and don't know someone who can, PM me so I can tell you how to email me your data and I'll run it through my little program and get your answer.


C# Console App Code:

class Program
{
static void Main(string[] args)
{
//change this to whatever desired amount you want
decimal desiredAmount = 2493.14m;

//load all the possible amounts into a storage structure
//(this would come from your accounting system)
List<decimal> allAmounts = new List<decimal>(
new decimal[] { 1.25m, 2000.00m, 500.45m, -10.00m, 2.69m } );

List<decimal> combinationEquallingTotal = GetCombination(desiredAmount, allAmounts);

if (combinationEquallingTotal != null)
{
Console.WriteLine("Combination found for {0}!", desiredAmount);
foreach (decimal decimalInCombination in combinationEquallingTotal)
Console.Write(decimalInCombination + " ");
}
else
Console.Write("No combination found for {0}.", desiredAmount);

Console.ReadKey();
}

static List<decimal> GetCombination(
decimal desiredAmount,
List<decimal> allAmounts)
{
return GetPossibleCombination(desiredAmount, 0.00m, allAmounts, new List<decimal>());
}

static List<decimal> GetPossibleCombination(
decimal desiredAmount,
decimal workingAmount,
List<decimal> availableAmounts,
List<decimal> currentlyUsedAmounts)
{
for (int i = 0; i < availableAmounts.Count; i++)
{
//copy the available amounts list
List<decimal> copyOfAvailable = new List<decimal>(availableAmounts);
//copy the currently used amount list
List<decimal> copyOfUsed = new List<decimal>(currentlyUsedAmounts);

decimal amountToAdd = copyOfAvailable;
//add this value to the "used" list
copyOfUsed.Add(amountToAdd);
//remove it from the "available" list
copyOfAvailable.RemoveAt(i);

decimal newAmount = workingAmount + amountToAdd;
if (newAmount == desiredAmount)
//we found a combination!
return copyOfUsed;

//call the function recursively if we want to try adding some of the remaining values
List<decimal> possibleCombination =
GetPossibleCombination(
desiredAmount,
newAmount,
copyOfAvailable,
copyOfUsed);

if (possibleCombination != null)
return possibleCombination;
}

return null;
}
}