# Looking for a better answer, if there is one (Puzzle)

#### Creamsteak

##### New Member
I've worked out a solution to a problem, but I was wondering if there might be a better way to do this. I'm using a computer to calculate these numbers, so I'm essentially looking to make a better algorithm to solve the problem, or if there's a better way to get the answer without having to go through long repetitive processes, that would help as well.

I'm probably a total 'noob' when it comes to these things, so if I seem a little confused or don't use appropriate terminology, it's because I don't know any better.

Because I want to avoid confusion, I'll introduce a couple simpler problems first. Neither of these problems are statistics issues, they are just there for examples really.

Case 1 (2x2)
Let's say you have a matrix with two columns and two rows. That gives it four internal cells. The numbers inside can be any number, but for these purposes we don't need a lot of numbers. Just four will do.

Code:
1|2
3|4
Our goal is to pick one value for each row and one value for each column, such that when you add together all of the values, we get the largest possible sum. Each pick must be exclusive, so you cannot pick any number twice.

For the 2x2, the solution is 1+2+3+4. For row 1, we can pick either 1 or 2. For row 2, we can only pick 3 or 4. We cannot pick 1 & 3 together because then there would be no value for column 1 to pick. We cannot pick 2 & 4 together because then there would be no value for column 2 to pick. So for rows, we are going to get 1 & 4 or 2 & 3. And for columns, we get whatever was left.

That's a long explanation though for a simple solution. In reality, we will always get a sum of 10, because we always pick all values. The main point of the 2x2 is just to show what's going on, and how the rules interact.

Case 2 (3x3)
In the 3x3 case, it's just a slightly larger matrix. Three columns and three rows make nine cells. I will simply use the values 1 to 9, but in theory you could have any numbers in any order.

Code:
1|2|3
4|5|6
7|8|9
In the 3x3, we can't just sum up the values because with 3 columns and 3 rows, we will only be using 6 cells. In the case above, there are a few solutions, but one I've found to outperform all others.

Because we are only going to pick 6 values, we are not picking 3. Because we want the sum of the picked values to be the highest, we want the sum of the unpicked values to be the lowest. This is fairly obvious, and shouldn't require any explanation.

However, if we pick 1, 2, and 3 as our 'unpicked' values, we are going to run into a problem. We won't be able to pick a value for row1, because we 'unpicked' all the values in that row.

What ends up being best is to take the 3 lowest values, unless they are 3 in a row, then take the 2 lowest, and the 4th lowest value. This works great and is fairly fast at solving this.

Stats Question 1: Let's say I randomly generate a matrix with values between 3 and 18 by rolling 3 six-sided dice. I generate nine such sets, and that makes up the matrix. What I want to know, is what is the mean value of the 'best picks' in the matrix. I have a computer running right now to calculate this, but it's going to take it about 6 days to finish. The computers no speed demon, and I could potentially get more performance, but I'm fine waiting on the numbers. That is, unless there's something obvious I'm missing that would give me an estimate of that average.

I know the value is greater than the mean of 3d6, but less than the max. It's something > 10.5 obviously, but not by a lot.

Case 4 (4x4)
So for the 2x2, the solution is the sum. For the 3x3, the fastest way I've found is to grab the 3 or 4 lowest values and pick everything else. In both cases, there's some 'simplification' that can be performed to make solving these problems easier.

For a 4x4 matrix, I have no easy tricks so far. My most effective solution has been to go through each and every possible pick order, and then take the highest total. What I mean by that is I go through 8! different possible orders, and take the highest value. Col 1, Col 2, Col 3, Col4, Row 1, Row 2, Row 3, Row 4, then Col 1, Col 2, Col 3, Col4, Row 1, Row 2, Row 4, Row 3. This continues till the end.

There's a very minor shortcut wherein you exit out if you ever get a value that is equal to the sum of the largest 8 values, but that's not really consequential in terms of computational speed. I actually found the program ran faster without checking, so I removed that case.

The same computer can solve 5,000 3x3s or 1 4x4 in about the same time. Further complicating things... the problem I'm trying to solve is also slightly more complex for the 4x4.

Stat Question 2: I want to find the average value for the 4x4 matrix where each cell contains the value of the sum of 4 different 4 sided dice. Using my above algorithm to find answers, and using the same methodology of the 3x3, it would take my same computer 1.5 billion YEARS to finish and give me back the average.

In this case it's fairly obvious to me that the average is > 10, because you're going to pick 'more larger numbers' than smaller numbers... but once again, I'm not sure by how much.

I'm sure there's more clarification I can make if necessary... Thanks to anyone that feels like responding.

#### gciriani

##### New Member
I do not think this puzzle has much to do with statistics. It believe it pertains to combinatorial math and matrix theory.