Home > AP Math > Description

AP Math

Ends: 25 Dec 2021 15:00
Now: 17 Oct 2021 15:16

AZsPCs | AP Math | Description

The Elevator Pitch

Select as many cells as possible from a hexagonal grid without including any three that form an arithmetic progression.


The Details

Three cells in a hexagonal grid are said to form an arithmetic progression if one of them is exactly midway between the other two. The following example demonstrates three arithmetic progressions.

A regular hexagonal grid containing 3 arithmetic progressions

In this contest you are asked, given a positive integer n, to select as many cells as you can from an order n regular hexagonal grid, with no three selected cells forming an arithmetic progression. Consider the following examples for n = 3:

A regular hexagonal grid with 7 cells selected
Okay
A regular hexagonal grid with 8 cells selected
Better
A regular hexagonal grid with an arithmetic progression
Invalid

The first example has 7 cells selected. The second is better because it has 8 selected. The third contains an arithmetic progression and is therefore invalid.

Submit your best solution for each of the 25 values of n in {2, 6, 11, 18, 27, 38, 50, 65, 81, 98, 118, 139, 162, 187, 214, 242, 273, 305, 338, 374, 411, 450, 491, 534, 578}.

For each value of n you may submit more than one solution, but only your best solution will count.

See How to Enter, below, for instructions on how to submit solutions.

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

This contest was inspired by Patrick Honner's Quanta Magazine article, To Win This Numbers Game, Learn to Avoid Math Patterns.


How to Enter

Paste your solutions into the appropriate box on the Submit page and click Submit Entry. Format your solutions according to the following instructions:

  • First, note that the cells in each row of a grid are indexed beginning with 0. For example, here are the indexes for the grid of order 4:
The order 4 regular hexagonal grid with cell indexes indicated
  • Then represent each row of your grid as a set of the indexes of its selected cells.

  • Finally, represent the grid itself as a list of these sets.

  • To submit more than one grid at a time, separate them with semicolons. Do not put a semicolon after your last grid.

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

For example, consider these two grids:

A regular hexagonal grid with 7 cells selected
A regular hexagonal grid with 8 cells selected
To submit them together you would enter:

{}, {1,3}, {1,2,4}, {1}, {2}; {2}, {1,3}, {2}, {1,3}, {1,2}


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 grid (that is, the one having the most cells selected). Your "raw score" for that n is the number of selected cells.

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

  • 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 we modify the contest by asking you to submit grids for only three values of n: 3, 4 and 5. Further suppose that we have 3 entrants: Elon, Jeff and Richard.

We begin by counting the selected cells in each submitted grid:

n = 3 n = 4 n = 5
Elon 7 18 20
Jeff 10 12 25
Richard 12 15 16

Next, we note the highest raw score for each value of n:

n = 3 n = 4 n = 5
Highest Raw Score 12 18 25

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

n = 3 n = 4 n = 5 Contest Score
Elon 7 / 12 = .583 18 / 18 = 1.000 20 / 25 = .800 2.383
Jeff 10 / 12 = .833 12 / 18 = .667 25 / 25 = 1.000 2.500
Richard 12 / 12 = 1.000 15 / 18 = .833 16 / 25 = .640 2.473

Jeff has the highest contest score and therefore is the winner.


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 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 resign from it and start submitting grids 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 name and registered email address. It is important that no team member submit any entries to this contest until I notify you that the team has been created.

    • 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.

    • Unless you are satisfied with the defaults, also let me know what team name and team location you would like to use on the standings page. Note that if all team members are from the same organization, the organization name can be included in the location, e.g., "Olaf Academy, Oslo, Norway".
      – For name, the default is "{last-name-1} / {last-name-2} / ... / {last-name-n}".
      – For location, the default is the smallest geographic entity common to all team member locations.

    Note: Teams are contest-specific. Joining a team for this contest does not affect your participation in other contests.

  • May I write a program that submits entries by bypassing my browser?

    Yes.

  • May I programmatically download the standings page at regular intervals? How frequently would be reasonable?

    Yes, you may programmatically download the standings page at regular intervals. Since the standings page is cached in memory, please feel free to download it as often as once per second. If you want to download the standings page more frequently than that, please contact me first.

  • I've written a little program that draws hexagonal grids, allows the user to manually select some cells, and then indicates which remaining cells would form an arithmetic progression if selected. May I distribute the executable to other contestants?

    No. This is a programming contest and writing useful tools is something a programmer should be able to do for himself. That alone would be sufficient reason to disallow the distribution of such tools, but consider also that you would be disadvantaging those who either don't hear about your tool or can't run your executable in their environment.

  • 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.