## Saturday, October 15, 2011

### A Puzzle I Can't Get My Head Around

I was working with a colleague of mine on a simple SQL query to create all combinations of values from 7 tables. This is a standard cartesian join between the tables, and it was taken care of relatively quickly. But this led to a puzzling situation the solution to which I still don't have.

Let me set up the problem first. There are seven buckets of numbers. Each bucket has 11 numbers in it. They are the multiples of 10 from 0 to 100 (0, 10, 20, 30, 40, 50, 60, 70, 80, 90 and 100). I have to pick one and only one number from each of the buckets.

How many combinations of numbers are possible? Any high-schooler will be able to tell me that there are 11^7 such combinations. So far, so good.

Now, for the puzzle. I now want to produce only combinations (each combination still has to include one number from each of the 7 buckets) that add up to 100. So, feasible combinations could include (100, 0, 0, 0, 0, 0, 0), (10, 10, 10, 10, 10, 10, 40), and so on. Infeasible combinations would include ones such as (100, 10, 20, 30, 40, 50, 60), (0, 0, 0, 0, 0, 0, 10), etc.

So, how many feasible combinations are there? That is the relatively simple form of the puzzle.

The generalized form of the puzzle is much harder: Given n buckets of numbers, and the contents of each of these buckets, and the requirement that a combination include one and only one number from each of the buckets, how many combinations exist that add up to x (or are less than x, or are greater than x, or lie between x and y, and so on and so forth).

I have googled for this a little bit, and found some web pages that refer to the subset-sum problem. But this does not seem to be exactly that kind of problem since I don't have a single set, but n different sets, and I want to choose one number from each set.

I know that when n (the number of sets) is 1 or 2, then the problem is quite trivial, and all solutions can be explicitly enumerated and counted. But I am having problems extending any mental construct that can be used to arrive at the solution to a problem involving more than 2 sets.

If someone knows about this kind of problem and can point me to a solution or at least a discussion of this kind of problem I would appreciate it. Thank you.

Kavitha said...

Hi there,
It was hard to find your name to address you from this add-ful page. Here is what I think about the problem,

The most important driving factor here is the condition that sum should be x. So you may come up with a condition that product may be p, or etcetera etcetera. That changes the way we arrive at solution. In the present condition, taking the sum (x) as the basis to come up with a solution.

x can be satisfied by a single number in each bucket. lets say x=30, then every bucket has 30 in it (10..100)

So its a probability of getting x in a bucket of m unique numbers = 1/m
This probability is true for all the n buckets we get x (1/m)*n times

probability of getting x out of 2 buckets and not picking x from any of them?
it is the probability of all those numbers, that add up to x , now this depends on the "nature" of our collection how granular or how discrete they are.

Example : if sum =30 then 10+20, 20+10, but if sum=40, 10+30, 30+10 and 20+20. So the satifying number of combination will vary depending on the discretion of our collection relating to the condition itself.

I think applying these theories of permutation, combination and probability mulitiple times you may arrive at the solution to your particular problem, but I am afraid its hard to consider it a generic prob.

Disclaimer: My thinking could be limited to my mathematical ability. So I may be finding it hard to abstract them from specific values.

--

I read most of your maths blogs and do appreciate your intellect and interest to share your knowledge with your readers.

thanks,
Kavitha.

Blogannath said...

Thank you for chiming in, Kavitha. You are the first (and so far, only) person to have expressed their thoughts on this puzzle.

You are absolutely correct that it would simply be a matter of time to sit down and explicitly enumerate all the possibilities once the contents of the sets are known, and the conditions (add up to x, product should be x, etc.) are known. In fact, unless the contents of the sets are determined probabilistically, there is no probability involved in the problem at all. But, as you rightly point out, thinking about it in generalized terms is where the problem arises. I will put together a blog post with my thoughts on this very soon.

Thank you very much for your interest in this post, and my other math-related posts.

## Content From TheFreeDictionary.com

In the News

Article of the Day

This Day in History

Today's Birthday

Quote of the Day

Word of the Day

Match Up
 Match each word in the left column with its synonym on the right. When finished, click Answer to see the results. Good luck!

Hangman

Spelling Bee
difficulty level:
score: -