Home > Sums and Products II > Description

Sums and Products II



Introduction

Given a set of numbers, we can list all the results that can come from picking two numbers from the set and then either adding them together or multiplying them.

For example, if we start with {1, 2, 3} the possible results are 1, 2, 2, 3, 3, 4, 4, 4, 5, 6, 6 and 9. Note that some results are duplicated because they can be formed in more than one way – 4, for example, is 2+2, 2×2 and 1+3.

For this contest, we are interested only in sets where there are no duplicated results from such pairwise additions and mulitplications. For example, starting with {3, 5, 8, 9} we get the twenty distinct numbers 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 24, 25, 27, 40, 45, 64, 72 and 81. So this set interests us.


The Contest

For each of the 30 values of n listed below, submit (see How to Enter, below) a set of n positive integers where there are no duplicated results from pairwise additions and multiplications. And, importantly, for each n, try to minimize the largest number in the set you submit.

For example, consider the sets A = {3, 5, 8, 9} and B = {1, 3, 7, 12}. Each set generates pairwise additions and mulitplications without duplicated results. But the largest number in A is smaller than the largest number in B, so set A is a better solution.

The 30 values of n are 5, 11, 23, 47, 101, 211, 307, 401, 503, 601, 701, 809, 907, 1009, 1103, 1201, 1301, 1409, 1511, 1601, 1709, 1801, 1901, 2003, 2111, 2203, 2309, 2411, 2503 and 5003.

You can submit more than one solution for each value of n, but if you do we count only your best solution. There is no penalty for submitting multiple solutions for the same problem.

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


The Prizes

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


How to Enter

Paste your solutions into the large box on the Submit page and click the Submit Entry button. Format your solutions as follows:

  • Each solution is a comma-delimited list of numbers. These are the positive integers in your starting set.

  • Submit multiple solutions (for different values of n) at the same time by separating them with semicolons. Do not put a semicolon after your last solution.

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

For example, if you were allowed to submit solutions for n = 3 and n = 4, you could submit two of the examples from above as follows: 1, 2, 3;
3, 5 ,8, 9

Do not submit entries under more than one account. This is important. Do not submit entries 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 30 values of n, we determine a raw score. The raw score is the largest number in the best solution you submitted for that n. (Recall that the best solutions are those whose largest numbers are small.)

  • For each of the 30 values of n, we compute a subscore from 0 to 1 by dividing your raw score for that n into the smallest raw score of any entrant for that n.

  • Your contest score is the sum of your 30 subscores.

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.

Let's walk through a simplified example. Suppose that we reduce the contest to only 3 values of n: 5, 11 and 23.

Further suppose that we have 3 entrants (Charles, William and George) and that their raw scores are as follows:

5 numbers 11 numbers 23 numbers
Charles 19 54 507
William 72 41 256
George 30 90 107

We note the smallest raw score for each value of n, as follows:

5 numbers 11 numbers 23 numbers
Smallest Raw Score 19 41 107

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

5 numbers 11 numbers 23 numbers Contest Score
Charles 19 / 19 = 1.0000 41 / 54 = 0.7593 107 / 507 = 0.2110 1.9703
William 19 / 72 = 0.2639 41 / 41 = 1.0000 107 / 256 = 0.4180 1.6819
George 19 / 30 = 0.6333 41 / 90 = 0.4556 107 / 107 = 1.000 2.0889

George has the highest contest score and therefore wins.


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

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 teams enter the contest?

    Yes, teams of exactly two people are allowed. 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 solutions 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 solutions directly to AZsPCs?

    Yes and no. If your program keeps track of your submissions and only submits improved solutions, 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 and the AZsPCs database had grown to 10 times its normal size. Please compute responsibly.

  • What topics are appropriate for the discussion group?

    With only one exception, if it's related to AZsPCs then it's fine to talk about it in the discussion group. The exception is spoilers. Spoilers include:

    • specific solutions
    • detailed algorithms
    • any calculation of the best raw scores

    If you are not sure if something would be considered a spoiler, ask me.

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

    You can't. I know this is frustrating, but it's a longstanding 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.

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

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