Graphs

A graph is a set of vertices and a set of edges, where each edge connects two of the vertices. In the following example of a graph, the vertices are represented by circles and the edges by lines. There are 4 vertices and 5 edges.

A graph (let's say it has e edges) with the following properties is called a gracefully labeled graph:

• Each vertex is labeled with a different member of the set {0, 1, …, e}.
• The smallest vertex label is 0.
• Each edge is labeled with a different member of the set {1, 2, …, e}.
• Each edge's label is the absolute difference of the labels of its endpoints.

This is an example of a gracefully labeled graph:

Many thanks to Elina Robeva whose paper "An Extensive Survey of Graceful Trees" introduced me to gracefully labeled graphs and to Hanhong Xue who introduced me to Ms. Robeva's paper.

The Contest

For each of the 25 prime numbers n less than 100 (that is, for n = 2, 3, 5, ..., 97) submit the gracefully labeled graph with n vertices which has the largest number of edges you can find. There are thus 25 distinct problems for which you are asked to submit solutions. See How to Enter, below, for instructions on how to submit your solutions.

You can submit more than one solution for the same problem, but if you do we count only your best solution (that is, the one with the greatest number of edges). 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 your choice of any item or items from Bathsheba Sculpture worth up to $500.

Second prize is your choice of any item or items from Bathsheba Sculpture worth up to $100.

How to Enter

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

• An individual graph consists of a comma-delimited list of edges.
• Each edge consists of a comma-separated pair of vertex labels, enclosed in parentheses.
• Submit multiple graphs (for different values of n) in a single entry by separating them with semicolons. Do not put a semicolon after your last graph.
• Include spaces and line breaks anywhere you like (except within a number) to improve readability.

For example, to submit the gracefully labeled graph given above, you might enter: (2,0), (0,4), (0,5), (2,5), (5,4)

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

The Scoring System

We give a raw score to each solution you submit. The raw score is the number of edges in your graph. For instance, if you were allowed to submit solutions for n = 4, the above example would receive a raw score of 5.

Each time you submit a solution we will merge it with your prior solutions, if any. The result will be a virtual entry containing your best solutions for each of the 25 problems. We will give each of these 25 solutions a subscore from 0 to 1 and their sum will be your contest score.

We calculate subscores for the individual solutions as follows. If your solution has the highest raw score that was submitted for that problem, we give it 1 point; otherwise we give it only a fraction of a point. The fraction is the solution's raw score divided by the highest raw score submitted by anyone for that same problem.

Let's walk through a simplified example. Suppose that we modify the contest by asking you to submit graphs for values of n from 8 through 10 -- that is, to submit gracefully labeled graphs with 8, 9 and 10 vertices.

Further suppose that we have 3 entrants (Sophia, Tristan and Lucille) and that their best solutions have raw scores as follows:

We note the highest raw score for each problem, as follows:

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

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 groups.io. 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 entries from more than one account is not permitted.

Can teams enter the contest?

Collaboration is allowed. However, only one of the collaborators may register. If two contestants are found to have collaborated, even if this occurred before one or both registered, both will be disqualified.

Can I write a program that submits solutions for me?

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. 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 solutions can I share in the discussion group?

There are two types of information that you are forbidden to post. The first is specific solutions. The second is code. You may post scores, so if you want to tell everyone that you got a raw score of 99 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 solution, the scorer shows me the solution's "canonical representation". What is that?

After the scorer calculates your raw score it re-orders the edges of your graph, re-orders the vertices attached to each edge, and may perform other transformations in order to create a standard (or "canonical") representation of the graph. Having canonical representations makes it easier to notice when two seemingly different solutions are fundamentally the same. This is particularly useful at the end of the contest when the best solutions become public.