Oh One Fun

Contest Home | Standings

Part A

Part B
Starts 7:00 PM CST, 2/26/05 Starts 7:00 PM CST, 2/26/05
Ends 11:59 PM CDT, 4/3/05 Ends 11:59 PM CDT, 4/3/05
First Prize $75 First Prize $75
Second Prize $50 Second Prize $50
Third Prize $25 Third Prize $25
Thanks to Tomas for providing some of the prize money!

THE PROBLEM

This problem deals with (0-1) square matrices. For part A of the problem your goal is to find the (0-1) matrix of size N with the largest determinant, with an additional bonus for sparsity. For part B of the problem, your goal is to find a system of N linear equations for which the solution has a variable as close to 1 as possible without actually being 1.

Part A

The determinant of a matrix has many applications, and sometimes it is useful to know how big a determinant can be for a certain family of matrices. In Part A, you will submit square matrices with between 10 and 59 rows, inclusive. Your goal is to maximize the absolute value of the determinant of the matrices divided by the square of the number of 1's in the matrix.

For example, the 4x4 matrix below has a determinant of 3, and 9 1's for a score of 3/81.
1011
1100
0110
0101
One (inefficient) way to calculate the determinant is to use a recursive algorithm. For each element in the first row, remove the row and column that the element is in. This gives you a matrix with one less row and one less column. You then recursively calculate the determinant of that matrix, and multiply it by the value of the removed element, alternating between adding and subtracting this product to the total sum. For example, the above matrix has a determinant of:
1*
100
110
101
 -0*
100
010
001
 +1*
110
010
011
 -1*
110
011
010
The base case is a 1x1 matrix, whose determinant is simply the value of its single element. If you were to work the above determinant out the rest of the way, it comes to 1 - 0 + 1 - (-1) = 3.

Determinants have a number of interesting properties, and you can read more about them on MathWorld. There are much faster ways to calculate the determinant than the one described above.

Part B

Consider a system of linear equations where each variable has a coefficient of either 0 or 1, and the sum of the variables is also either 0 or 1. For example,
x1+x3 = 1
x2+x3 = 1
x1+x2 = 0

One way to represent such a system of equations is as a matrix with N rows and N+1 columns, where the last column represents the constants on the right hand side of the above equations. For example, the above system would be represented as:
1011
0111
1100
Considering only systems of equations that have a single solution, the solution always consists of an assignment of rational numbers to each xi.

In part B of the problem, your goal is to find a system of linear equations that has a single solution and for which some xi is as close to 1 as possible without actually being 1. For example, the system of equations above has one solution – x3 = 1 and x1 = x2 = 0, so x1 and x2 are each 1 away from the target of 1. Again, you may submit for 10 ≤ N ≤ 59.

SCORING

Parts A and B will be scored independently. For each part, your final score will be the sum of your scores for each value of N. If you do not submit for a particular value of N, you will receive a 0 for that value of N. For part A, your score for a particular value of N will be equal to the determinant of your matrix divided the square of the number of 1's in the matrix, divided by the best score of any competitor. Hence the best total score you could get over all N is 50. Similarly, if your submission for part B has a solution whose closest variable is K, your score will be abs((best-1)/(K-1)) where best is the best over all submissions, for that particular N.

SUBMITTING

Once you have registered, submitting is easy. Simply go to the submission page and follow the instructions there. Both parts A and B are submitted in the same way, by providing a sequence of zeros and ones in row major order. For example, to submit the matrix example from part B, you would submit: 
    101101111100
Upon submission your matrices will be automatically scored and the results page will be automatically updated.

RESULTS

The results page will contain a summary of the standings and is automatically updated whenever new submissions are received. To add some suspense, the results page will be fixed 3 days before the end of the contest, and will not be updated until the conclusion.

TIES

Ties will be broken in favor of submission time, with preference given to the person who improved his score longest ago.

FAQ

I submitted, but the number of submissions didn't go up on the results page.
The count only increases when you submit an entry that improves your score. Furthermore, your scores are initialized to 0 for part A and 1 for part B, so if you don't do better than those, your count will start out at 0, even though you'll show up in the results page.
I'm having problems submitting, or have found a bug in the system. What should I do?
Send an email to contest@worlddesigncenter.com, and I'll do my best to get things straightened out.
It takes a long time for me to get results back once I submit.
If you submit a lot of matrices at once, it may take a long time for the page to load while your entries are being processed. If it is taking so long that your request is timing out, try submitting fewer entries at once. If you still have problems, email me and I'll try to figure out whats going on.
Can we discuss the problem?
By all means. Of course, if you do, you'll be helping the competition. I have set up a Discussion Forum to discuss anything contest related.
Contest Home | Standings