Home > Non-Coplanar Points > Description

Non-Coplanar Points

The Problem

On March 20, 2014 Ed Pegg reported on mathpuzzle.com, "There are 38 ways to pick 13 points from a 5 × 5 × 5 grid so that no four points are in a plane. There is a unique solution for 8 points from 3 × 3 × 3, and 232 solutions for 10 points from 4 × 4 × 4."

For example, no 4 of these points from a 4 × 4 × 4 grid are coplanar:

(1,3,1), (3,2,2), (3,3,3), (1,0,3), (0,3,2), (0,1,3), (0,0,1), (2,0,1), (1,1,0), (3,2,0)

What is the largest number of points you can choose from an n × n × n grid so that no 4 are coplanar?

The Contest

For each value of n, where n is one of the first 25 primes, submit the largest set of points you can find in an n × n × n grid so that no 4 points are in a plane.

The first 25 primes are { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }.

See How to Enter, below, for instructions on how to submit a set of points.

For each value of n you can submit more than one set of points if you wish, but only your largest will count.

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

The Prizes

First prize is a $500 credit at Bathsheba Sculpture. Second prize is a $100 credit.

How to Enter

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

  • An individual set consists of a comma-delimited list of points.

  • Each point consists of a comma-delimited list of 3 unsigned integers, enclosed in parentheses.

  • To submit more than one set of points at a time (for different values of n) separate them with semicolons. Do not put a semicolon after your last set of points.

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

We will infer the size of your grid from the largest coordinate. Specifically, if the largest coordinate is x, we take n to be x + 1.

For example, if you were permitted to submit points for a 4 × 4 × 4 grid, you could submit the example from above by entering: (1,3,1), (3,2,2), (3,3,3), (1,0,3), (0,3,2), (0,1,3), (0,0,1), (2,0,1), (1,1,0), (3,2,0)

Do not create more than one account for submitting solutions. This is important. Do not create more than one account for submitting solutions.

The Scoring System

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

  • For each of the 25 values of n, we find your best solution. Your "raw score" for that n is the square of the number of points in that best solution.

  • For each of the 25 values of n, we compute a "subscore" from 0 to 1. We do this by dividing that n's raw score by the highest raw score for that n across all entrants.

  • Your contest score is the sum of your 25 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 the contest asks you to submit solutions only for n = 4, 6 and 8.

Further suppose that we have 3 entrants (Oscar, Edgar and Hugo) and that the sizes of their best solutions are as follows:

4 × 4 × 4 6 × 6 × 6 8 × 8 × 8
Oscar 5 12 18
Edgar 10 11 17
Hugo 7 15 16

Their raw scores are therefore:

4 × 4 × 4 6 × 6 × 6 8 × 8 × 8
Oscar 25 144 324
Edgar 100 121 289
Hugo 49 225 256

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

4 × 4 × 4 6 × 6 × 6 8 × 8 × 8
Largest Raw Score 100 225 324

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

4 × 4 × 4 6 × 6 × 6 8 × 8 × 8 Contest Score
Oscar 25 / 100 = 0.250 144 / 225 = 0.640 324 / 324 = 1.000 1.890
Edgar 100 / 100 = 1.000 121 / 225 = 0.538 289 / 324 = 0.892 2.430
Hugo 49 / 100 = 0.490 225 / 225 = 1.000 256 / 324 = 0.790 2.280

Edgar 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

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.

You do not need to have a Yahoo account to join the group.

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. 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 to the contest on your own behalf.

    If you would like to form a team, please follow these instructions:

    • If they do not already exist, create individual accounts for each team member. Do not create a second account for any team member who already has one.

    • Let me know each team member's registered email address. It is important that no team member submit any entries to the contest until I notify you that the team has been created and that it is okay to begin submitting.

    • After I’ve created the team, team members can submit entries to the contest from their individual accounts. The contest engine automatically intercepts these entries and diverts them to the team account. The team is listed on the standings page.

    • Note: Teams are contest-specific. Joining a team for this contest does not affect your participation in other contests.
  • Can I write a program that submits entries by bypassing my browser?

    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 individual was single-handedly responsible for 90% of the entries in the database. 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

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

  • 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 rotates and reflects your solution in order to create a standard (or "canonical") representation. Representing solutions canonically 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.