Enigma 1759

Spoiler for New Scientist Enigma 1759: “Cell count” (Follow the link to see the puzzle.)

I can’t see an easy way to do this by hand, but it can be done in a spreadsheet; the key is to figure out the needed formula.

Consider just the upper right quadrant; of course the number of cells crossed for the whole circle will be 4 times the number for the quadrant. Now consider each increment along the x axis from 0 to 1 to 2 to … to r, the radius. When x goes to (x+1), y goes from √(r2x2) to √(r2–(x+1)2). The number of cells passed through in this column is 1 greater than the number of times the circle crosses a horizontal line (not counting lines started or ended on). Think about it hard enough and you realize the number of cells crossed in the file starting at x is:

√(r2x2)√(r2–(x+1)2)

where xand xare respectively the ceiling and floor functions. Multiply that by 4 and sum over all x from 0 to r–1 and you have the number of cells crossed.

So put that into a spreadsheet and graph the result:

chart_1For a radius of less than 50, the only place the number of cells decreases when the radius increases is in going from radius 24 (188 cells) to 25 (180 cells).

Advertisements

7 thoughts on “Enigma 1759

  1. The number of squares is an arithmetic progression of form 8 x (radius – t) – 4, where t is the count of Pythagorean triples where the hypotenuse equals the given radius.

    Given this, the answer will be the only radius less than fifty that has more than one Pythagorean triple. 25 has 2: 15,20,25 and 7,24,25.

    This gives an answer of 180 (matches your graph, though not your text).

  2. Thanks for spotting the typo. I fixed it above.

    I think it’s fairly obvious the solution must have to do with Pythagorean triples. But the derivation of your formula isn’t immediately obvious to me — though empirically it certainly works.

  3. If you draw a grid and start shading squares on any path from the top left square to the bottom right, and if every step is to the right of or beneath the previous, you will have shaded Width+Height-1 squares.

    In the top right quarter of our circle this will be 2r-1, though every Pythagorean triple means the path in the grid above will miss one square as the path jumps diagonally. The quarter must have 2r-2t-1 shaded squares, the circle 8r-8t-4 squares.

  4. Ah, that makes it clear. It’s taxicab geometry; any taxicab path between two points that doesn’t reverse itself is the same length. But at a Pythogorean triple the taxicab can go diagonally and save a step. Thanks.

  5. Hi guys.

    I used your formula to make a list of the total cells crossed. But I find that the drop comes between 24 and 25 so that the answer should be 25. Is this just a typo on your part, or did I miss something. My list seems to be good for all radiuses from 1 to 5 (found by making circles on paper in practice)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s