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?

Friday, October 21, 2011

Update On My Bosch SHE33M02UC Dishwasher

I wrote in an update last year about having second thoughts about my Bosch SHE33M02UC dishwasher. One of the problems I mentioned in that update was the fact that soap residue was building up in the dishwasher, and causing all kinds of problems. The finish of the inside walls was completely obscured by a thick layer of white soap scum, and the sprinkler arms were getting clogged with bits of soap such that water could not come out of the sprinklers to clean the dishes.

I was quick to blame these problems on the dishwasher itself. I still think the other problems mentioned in my previous post are demerits for the dishwasher. However, the soap scum problem is not actually a dishwasher problem. It turns out, the soap scum problem is, in fact, a detergent problem!

You see, I was using a liquid detergent made by Palmolive called Palmolive Eco Gel. I was Googling around for a solution to these soap scum problems when I ran across a raft of reviews for this dishwasher detergent. And they all say the same thing: avoid this thing like the plague because it clogs up dishwashers with soap scum! You can read a lot of reviews here. And I completely believe those reviews because my experience has been identical to that of these reviewers.

It turns out that my experience with my dishwasher was the norm rather than an exception. This dishwasher detergent is formulated in such a way that it leaves behind thick layers of residue in any dishwasher it is used in. My Bosch dishwasher was working perfectly fine, it was the detergent that was killing it.

It was a revelation that I had never even considered! Obviously, I knew dishwasher detergents were all different from one another, but I thought that at the very least, they would all clean up after themselves just as they are designed to clean up dishes in the dishwasher. Turns out, my assumptions were wrong. This dishwasher detergent is BAD! Bad for your dishes, bad for your dishwasher, bad for your plumbing, bad for your peace of mind.

My conspiracy theory regarding this dishwasher detergent is that this product is the cheapest dishwasher detergent out there for a reason: dishwasher manufacturers contributed money to its formulation, and they are actively subsidizing its production, marketing and sales so that it can be sold cheap to unsuspecting consumers. Then their dishwashers go bad, and they are forced to buy new ones. And guess who they have to go to get new dishwashers?

Well, the story has a reasonably good ending, at least for me, though. Based on all my Googling, I managed to clean up my dishwasher quite well. If I had continued using the bad detergent, I probably would have damaged my dishwasher beyond repair, and might have had to get a new one. It might also have damaged my kitchen plumbing, forcing me to make more expensive repairs. I have no idea what people did in the days before the internet to identify insidious problems like this.

In case you are wondering what I did to clean up my dishwasher until it was as good as new, read on.

First thing to do is to stop using this bad dishwasher detergent. I threw out 2 full bottles of it unused, and switched to a powder detergent. You see, unintuitive as it may seem, the consensus is that liquid detergents leave a lot more soap scum behind in dishwashers and on dishes than powder detergents. The new detergent is more expensive, but at least it does what a detergent is supposed to do instead of sabotaging your appliances when you are not paying attention!

Next, I removed the sprinkler arms from the dishwasher and cleaned them out under the sink so that there were no soap particles stuck inside them to cause them to clog up. I had to use tweezers to get rid of some of the soap scum sticking to the sprinkler holes in the arms. I also cleaned out the filters at the bottom of the dishwasher (which were also clogged with soap scum and were quite disgusting to look at before being cleaned).

Next, I cleaned out the dishwasher by running it empty several times. I used CLR, Limeaway and white vinegar in generous quantities (just pour them in the dishwasher tub before closing the dishwasher and turning it on) during these empty runs to dissolve and wash away the soap scum. During these empty runs, use the highest temperature option of the dishwasher.

After the first couple of empty runs, you may notice that the sprinkler arms get clogged again. This is because the soap scum sticking to the insides of the dishwasher and the inside of the sprinkler arm itself gets partially dissolved, and comes off in chunks. Some of the smaller chunks can then get sucked into the sprinkler arms and again cause clogs. So, watch out for this, and clean out the sprinkler arms as needed. Take out the filters and clean them out also after these empty runs.

Third, I got a product called Dishwasher Magic and used it a couple of times on my dishwasher. This product comes in a sealed plastic container with a wax plug. You can't open the container to see what it contains. You just put it upside down in the silverware basket of your dishwasher and turn the dishwasher on at its highest temperature setting. During the high-temperature wash (minimum of 125 degrees Fahrenheit), the wax plug melts, and the cleaner inside the package works its magic inside the dishwasher.

I don't usually fall for gimmicks like Dishwasher Magic. But this product is actually not a gimmick. Lots of people swear by this product, and my experience with this product has made me a believer too. I now have a stock of Dishwasher Magic ready at hand to use every once in a while (the manufacturer recommends using it every month, but once in 6 months or so should be plenty from what I can see).

I have read on the internet that the main ingredient in Dishwasher Magic is citric acid. Vinegar is diluted acetic acid. So, both are acids, but I think Dishwasher Magic is more concentrated. Could be the reason why the package can not be opened, but is sealed with a wax plug that only opens up inside a hot dishwasher. Dishwasher Magic is also a disinfectant that kills salmonella, E.Coli and other gram-negative bacteria.

So, what is the state of my dishwasher after all these changes and clean-up efforts on my part? I am happy to report that my dishwasher is working perfectly since I cleaned it up. The inside is sparkling once again, with no visible soap scum anywhere. The sprinkler arms are clear of gunk, and the dishes come out well-washed without any problems. The filters are also much cleaner and I am sure the dishwasher motor and other components are working much better because they are pushing and pumping clean water through clean filters instead of working against clogged up filters and internal and external plumbing.

I am glad I did the research necessary to identify the problem as well as an effective and cheap solution. If you are facing problems with soap scum and other problems with your dishwasher, stop and look at everything that goes into the dishwasher. It is easy to blame the dishwasher for these problems, but the culprit could be something else entirely. I hope you catch the problem before it is too late, and save yourself the expense of a new dishwasher and/or new plumbing. Try the solutions that worked for me if nothing else worked. If something else worked, please do others a favor by posting comments about what worked so that everybody benefits from your wisdom and experience. Good luck!

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.

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