Home > Delacorte Numbers > Description

Delacorte Numbers

What are Delacorte Numbers?

Take an m × n rectangle and divide it into an array of unit cells. Then number the cells, in any order you wish, from 1 to mn. For example, if your rectangle is 2 × 3, it might look like this after you've numbered it:

4 1 3
6 5 2

The Delacorte number is an integer-valued property of such a rectangle. It is computed as follows.

For each distinct pair of integers (a, b) in the rectangle, calculate Da,b using the formula

Da,b = gcd(a, b) × distance2(a, b)

where gcd(a, b) is the greatest common divisor of integers a and b, and distance(a, b) is the physical distance (within the rectangle) from integer a to integer b.

The Delacorte number for the rectangle is the sum of all the Da,b.

For example, for the rectangle above the calculation of its Delacorte number looks like this:

a b gcd(a, b) distance2(a, b) Da,b = gcd(a, b) × distance2(a, b)
1 2 1 2 2
1 3 1 1 1
1 4 1 1 1
1 5 1 1 1
1 6 1 2 2
2 3 1 1 1
2 4 2 5 10
2 5 1 1 1
2 6 2 4 8
3 4 1 4 4
3 5 1 2 2
3 6 3 5 15
4 5 1 2 2
4 6 2 1 2
5 6 1 1 1
Delacorte number 53


The Contest

For each integer n from 3 to 27 submit two n × n squares numbered with the integers from 1 to n2. One of the squares should have the largest Delacorte number you can make; the other should have the smallest. See How to Enter, below, for instructions on how to submit your squares.

For each value of n you can submit more than two squares if you wish, but we will count only your two most extreme squares – that is, only the square with the largest Delacorte number and the square with the smallest.

See The Scoring System, below, to learn how we determine the winner.

My thanks to Marcos Donnantuoni, whose "multiples graph" inspired this contest.


The Prizes

First prize is a $500 gift certificate redeemable at Bathsheba Sculpture. Second prize is a $100 gift certificate.


How to Enter

Just paste your squares into the large box on the Submit page and click the Submit Entry button. Format your squares as follows:

  • An individual square consists of a comma-delimited list of rows.

  • Each row consists of a comma-delimited list of integers, enclosed in parentheses.

  • If you would like to submit more than one square at a time (either for the same value of n or for different values) separate them with semicolons. Do not put a semicolon after your last square.

  • Include spaces and line breaks anywhere you like (except within a number) to improve readability.

For example, if you were permitted to submit the non-square example above, you might enter: (4,1,3), (6,5,2)

Do not submit squares under more than one account. This is important. Do not submit squares under more than one account.


The Scoring System

The entrant with the highest contest score wins. Here's how we calculate your contest score:

  • For each of the 25 possible values of n, we identify the square you submitted with the largest Delacorte number and the one with the smallest. The difference between these two Delacorte numbers is your raw score for that n.

  • For each of the 25 possible values of n, we also identify the square with the largest Delacorte number submitted by any entrant and the square with the smallest Delacorte number submitted by any entrant. The difference between those two numbers is the conjectural best for that n.

  • Then, for each n, we calculate your subscore for that n by dividing your raw score by the conjectural best.

  • Finally, we calculate your contest score by adding up your 25 subscores.

Let's walk through a simplified example. Suppose that we modify the contest by asking you to submit squares of only 3 sizes: 3 × 3, 4 × 4 and 5 × 5.

Further suppose that we have 3 entrants (Heisenberg, Pinkman and Crystal) and that these are their most extreme Delacorte numbers and their raw scores:

3 × 3 4 × 4 5 × 5
MinMaxRaw
Score
MinMaxRaw
Score
MinMaxRaw
Score
Heisenberg 13418753 11212071950 39334501568
Pinkman 14520863 9751716741 404952951246
Crystal 12017555 10831908825 413560061871

We note the conjectural best for each problem, as follows:

3 × 3 4 × 4 5 × 5
MinMaxConjectural
Best
MinMaxConjectural
Best
MinMaxConjectural
Best
All Entrants 12020888 97520711096 393360062073

Finally, we compute the subscores and contest score for each entrant:

3 × 3 4 × 4 5 × 5 Contest Score
Heisenberg 53 / 88 = 0.6023 950 / 1096 = 0.8668   568 / 2073 = 0.2740 1.7431
Pinkman 63 / 88 = 0.7159 741 / 1096 = 0.6761 1246 / 2073 = 0.6011 1.9931
Crystal 55 / 88 = 0.6250 825 / 1096 = 0.7527 1871 / 2073 = 0.9026 2.2803

If two entrants have the same contest score, we break the tie by giving preference to the entrant whose last improvement was submitted least recently.


Getting Your Questions Answered

First, check the FAQ section below. If you can't find the information you need there, send your question to the discussion group. If your question is of a personal nature, and not of general interest, send an email directly to Al Zimmermann.


The Discussion Group

If you think you might enter the contest, you should join the contest discussion group. You can join either by sending a blank email here or by visiting the group on Yahoo!. The discussion group serves two purposes. First, it allows contestants to ask for clarifications to the rules. Be aware that sometimes these requests result in changes to the rules, and the first place those changes are announced is in the discussion group. Second, the discussion group allows contestants to interact with each other regarding programming techniques, results and anything else relevant to the contest.


My Lawyer Would Want Me To Say This

I reserve the right to discontinue the contest at any time. I reserve the right to disqualify any entry or entrant for any reason that suits me. I reserve the right to interpret the rules as I see fit. I reserve the right to change the contest rules in mid-contest. In all matters contest-related, my word is final.


Frequently Asked Questions

  • Can I enter the contest more than once, using different accounts?

    No. Submitting squares from more than one account is not permitted. In fact, just having more than one account is against the rules.

  • Can teams enter the contest?

    Yes. But a team can only be formed by those who have not already entered the contest as individuals. Once you enter as an individual, team membership is no longer open to you. Likewise, once you've joined a team you can't break away and start submitting squares on your own behalf. If you would like to form a team, please email me.

  • Can I write a program that bypasses my browser and submits squares directly to AZsPCs over the Internet?

    Yes and no. If your program keeps track of your submissions and only submits improved squares, yes. Otherwise, no. For the Son of Darts contest a few years ago, there was one participant who wrote a program to exhaustively generate all possible solutions and submit every one of them. Within two weeks he'd submitted over a million entries. The AZsPCs database had grown to 10 times its normal size and this fellow was single-handedly responsible for 90% of the entries in the database. Please compute responsibly.

  • What information about my squares can I share in the discussion group?

    There are two types of information that you are forbidden to post. The first is specific squares. The second is code. You may post scores, so if you want to tell everyone that you got a raw score of 1,598,259 for n = 20 (whether true or not), go right ahead. You may also discuss the algorithms you are using.

  • How can I find out what my individual subscores are?

    You can't. I know this is frustrating, but it's a long standing policy that isn't going to change. Over the years it's been hotly debated in the discussion group and the contest administrator appears to have very strong feelings on the matter. You're going to have to learn to live with it. And I'd think twice before raising the issue yet again.

  • After I submit a square, the scorer shows me the square's "canonical representation". What is that?

    After the scorer calculates your Delacorte number it rotates and reflects your square in order to create a standard (or "canonical") representation of the square. Having canonical representations makes it easier to notice when two seemingly different squares are fundamentally the same. This is particularly useful at the end of the contest when the best squares become public.