Programming Contest

DARTS


The contest has ended. The results are available here.


THE DARTS PROBLEM

Suppose that we have a dartboard that is divided into N areas. Each area has a positive integer value associated with it. You have three darts and you throw each of them at the dartboard. Each dart either lands in one of the board's N areas or misses the board altogether. Your score is the sum of the values for the areas in which the darts land. A dart that misses the board contributes nothing to your score. If multiple darts land in the same area, you accumulate the value for that area multiple times.

For example, suppose N = 5 and the dartboard areas have values (1, 2, 4, 7, 11). If your three darts land in areas 2, 4 and 11 you score 17 points. If one dart misses the board and the other two land in area 7 you score 14 points.

The Darts Problem is this: for a given N, determine what values should be associated with its N areas in order to maximize the smallest unattainable score.

For example, again suppose that N = 5 and that the 5 areas have values (1, 2, 4, 7, 11). Then the smallest unattainable score is 27. (That is, we can attain scores 0 through 26 but not 27.) But we can do better than 27. If we change the values on the dartboard to (1, 4, 6, 14, 15) then the smallest unattainable score is 37.

THE CONTEST

Send us (see HOW TO ENTER, below) your best solutions to the Darts Problem for values of N from 1 to 25. The winning entry will be the one with the best solution for N = 1. In case of a tie (which is pretty likely) the tie will be broken by comparing solutions for N = 2. Continued ties will be broken by considering solutions for successively higher values of N. In the unlikely event of a tie after N = 25, the winner will be selected at random from among those tied.

THE PRIZES

First prize: One hundred dollars.
Second prize: Choice of either WinFax or Norton Anti-Virus (provided courtesy of John Pilge).

HOW TO ENTER

Send an email containing your entry to bitzenbeitz@aol.com before Noon EDT on October 1, 2001. Put just the word DARTS in the subject line. The body of the email should be formatted as follows.

The first line should contain your solution for N = 1. The second line should contain your solution for N = 2. And so forth through N = 25. Each such solution should be expressed as a list of N comma-delimited integers in ascending order representing the values on the dartboard. After your last solution leave a blank line. After that blank line provide your name and address. Your name and address can be in any human-readable format.

Scoring will be done by computer, so be careful in composing your email.

You may enter as often as you like, but only your best entry is eligible to win a prize.

IF YOU HAVE QUESTIONS

If you have questions, check the FREQUENTLY ASKED QUESTIONS section, below. If your questions aren't answered there, send them to alzimmerma@aol.com.  If you would like to receive copies of the questions I receive and of the responses (which could contain clarifications and/or corrections to the rules) send a request to the same address.

FREQUENTLY ASKED QUESTIONS

Can I assign the same value to more than one area of the dartboard?

Yes. Multiple areas of the dartboard can have identical values. There is no requirement that each area have a unique value.

In the example given, where N=5 and the dartboard areas have values (1, 2, 4, 7, 11), I can score 33 by landing all three darts in area 11. So why is 27 the smallest unattainable score and not 34?

It is not true that the smallest unattainable score is exactly one more than the largest attainable score. In the example, 33 is the largest attainable score. But there are a few scores smaller than 33 that are unattainable. To see that 27 is unattainable, try to figure out where the 3 darts should land to score 27 points - you'll find that it can't be done.

Can you give an example of a valid entry?

Sure. Here's my pet parrot's entry. (She's a real birdbrain, so her solution isn't very good. She's a mediocre typist too (mostly she just hunts and pecks), but she formatted this perfectly.)

1
1,4
1,4,7
1,4,7,10
1,4,7,10,13
1,4,7,10,13,16
1,4,7,10,13,16,19
1,4,7,10,13,16,19,22
1,4,7,10,13,16,19,22,25
1,4,7,10,13,16,19,22,25,28
1,4,7,10,13,16,19,22,25,28,31
1,4,7,10,13,16,19,22,25,28,31,34
1,4,7,10,13,16,19,22,25,28,31,34,37
1,4,7,10,13,16,19,22,25,28,31,34,37,40
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70
1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70,73

Harpo Zimmermann
14 Aviary Lane
Macaw, ME 01101

How will I know that you've received my entry?

When an entry is received it is immediately (that is, usually within 24 hours) processed by the automated Parser/Scorer and a confirmation is sent back to the submitter. If the entry is valid, the confirmation contains the 25 Smallest Unattainable Scores calculated by the Scorer. If the entry is invalid, the confirmation explains why the Parser rejected it.

My email software automatically inserts line breaks in long lines. Will this cause my entry to be rejected?

Here at Darts Contest Galactic Headquarters we are a forgiving lot. If the Parser/Scorer rejects an entry but the submitter's intent is clear, we'll probably (depending on the effort involved) repair the entry. In particular, we will always fix spurious line breaks inserted by your email software.


Darts Contest Results Al Zimmermann's Programming Contests