Search The Web

Today's Headlines

Wednesday, October 26, 2011

I Have An Answer To My Question, But Not A Solution To My Puzzle

Last week, I wrote up a blog post about starting with 7 sets of 11 numbers each (multiples of 10 from 0 through 100), and trying to find the number of ways to choose one number from each set such that the sum of the numbers is 100. I have spent time thinking about this problem, and doing some research on it on and off for the past week or so.

Based on what I have seen so far, and what I have been able to think of by myself, it is not an easy problem. I did not expect it to be trivial, but it turns out it is a lot harder than I gave it credit for. I eventually did manage to find the answer to my specific question. That is to say, given 7 sets of 11 numbers (multiples of 10 from 0 through 100), I know how many ways exist of combining one number from each of the sets such that they all add up to 100. However, I am not any closer to a general solution to my puzzle than I was a week back.

My first stop once I conceived of the puzzle was to check on Google. I used several combinations of search terms, but did not come up with any results initially. Knowing what to search for is sometimes half the battle when it comes to using the web to research something! In this case, I did eventually hit upon the right search terms. And this led me to an article on Wikipedia devoted to the Partition Function.

Essentially, a partition of a positive integer is a way of writing that positive integer as a sum of other positive integers. The number of ways of "partitioning" the given integer, n, is represented by the function p(n). There is also another function p(k,n), which indicates the number of ways in which the integer n can be partitioned such that the minimum integer used to create n in any of the sums is at least equal to k.

Moreover, there is a recursive relationship that allows one to calculate p(n). The trick is to use the following relationships and slowly work your way through the entire problem. The relationships are:

p(k,n) = 0 if k>n (this is obviously true since you can not get a set of positive integers to add up to n if each of them is greater than n)
p(k,n) = 1 if k=n
p(k,n) = p(k+1,n) + p(k,n-k)

When we want to calculate p(n) in general, what we really want to calculate is p(1,n) since we are allowed to use all integers starting from 1.

Using the relationships above, for instance, one would calculate p(4) as below:

p(4) = p(1,4)
p(1,4) = p(2,4) + p(1,3)
p(2,4) = p(3,4) + p(2,2)
p(3,4) = p(4,4) + p(3,1)
Thus, p(2,4) = p(4,4) + p(2,2) + p(3,1) = 1 + 1 + 0 = 2 (this is obviously true since the number of combinations of positive integers that add up to 4 such that each integer is greater than or equal to 2 are either 2+2 or 4).

Similarly p(1,3) can be broken down as below:

p(1,3) = p(2,3) + p(1,2)
p(2,3) = p(3,3) + p(2,1) = 1
p(1,2) = p(2,2) + p(1,1) = 1 + 1 = 2

Thus, p(1,3) = 3.

Thus p(4) = 3 + 2 = 5.

This is true since we can actually enumerate the answer to this problem. The sets of numbers that add up to 4 are (1,1,1,1), (2,1,1), (3,1), (4) and (2,2). Actually, the partition problem gives us only combinations, not permutations. Thus (3,1) is considered the same as (1,3).

The partition function increases tremendously as you go out further and further. Here are some values of partition functions:
p(1)    1
p(2) 2
P(3) 3
p(4) 5
p(5) 7
p(6) 11
p(7) 15
p(8) 22
p(9) 30
p(10) 42
p(11) 56
p(12) 77
p(13) 101
p(14) 135
p(15) 176
p(16) 231
p(17) 297
p(18) 385
p(19) 490
p(20) 627
p(21) 792
p(22) 1002
p(23) 1255
p(24) 1575
p(25) 1958
...
p(100) 190569292
p(1000) 2.4x10^31

Partitions of numbers
A graph of the function with just the first 25 points plotted looks as shown on the left. It starts off slowly, but the rate of growth increases as you move along, making the numbers grow literally "off the chart" as you move to the right.

So far, so good. In fact, if my puzzle had been worded exactly as the partition function is defined, all would be well. Unfortunately, my puzzle is not worded the same way. First of all, my puzzle had the number of sets of numbers pre-defined. Moreover, the contents of these sets were also pre-defined. Also, I wanted each combination of numbers to include one and only one number from each set, and I wanted all permutations, not just combinations. Thus, in my puzzle, (1,3) is definitely different from (3,1).

Unfortunately, there seems to be no generalized problem defined the same way as my puzzle. This can be considered either good or bad. The good thing is that, I can now name this puzzle after myself! The bad thing is that no great intellects have applied themselves to the solution of this problem. Given the level of my intellect, if nobody else does work on my puzzle, it will remain unsolved for all of eternity!

Now, before I leave you, I will provide you with some numerical answers to my puzzle. Arriving at these was quite easy using computers. All I had to do was create a table with 11 elements (multiples of 10 from 0 through 100). Then, using self-joins, I was able to create all permutations of these numbers that add up to 100. Depending on how many times I self-joined this table to itself, I can find the number of ways to make 100 using 2 sets, 3 sets, etc.

Before you get carried away though, a word of warning: I ran these queries on a pretty powerful server that has enough number-crunching power and memory to make it without crashing. Cartesian self-joins like the one I was doing are quite capable of bringing even powerful computer systems down to their knees, so you have to be careful with them.

Here are the results from my computer runs. The number on the left represents the number of sets I used, and the number on the right represents the number of permutations that are possible using one number from each of the sets.
1    1
2 11
3 66
4 286
5 1001
6 3003
7 8008
8 19448
9 43758
10 92378

Sets adding up to 100
The server ran for over an hour to find the answer to the 10-set problem, and I did not dare try to find the answer for the 11-set problem. A graph of these numbers is shown on the left.

The numerical answer is all well and good, but unfortunately, I am yet to come up with any pattern in the answer that will allow me to generalize an answer to the puzzle. Hence the title of this blog post: I have an answer, but not a solution. Essentially, my original problem was to find the number of permutations when number of sets is 7. And the answer is 8008.

Now, what would be the answer if I had 21 elements in each set (multiples of 10 from 0 to 200), had 12 sets, and wanted the sum to be 250? I have no clue. I have no idea how to systematically go about calculating it. Yes, I can do it laboriously if forced to. And if I have a sufficiently powerful computer at my disposal, I can arrive at the answer without having to exert my brain cells.

The question is, is there a way to arrive at the answer without enormous and tedious mental labor, or trillions of computer operations?

No comments:

Visitors Country Map

Free counters!

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: -
please wait...
 
spell the word:

Search The Web