Enigma 1723

Spoiler for New Scientist Enigma 1723: “Four Lots of Dots” (Follow the link to see the puzzle.)

A square is formed by four line segments; if you go around the perimeter of the square in one direction then each segment is in a different quadrant of the plane (where the first quadrant includes the +x axis and goes up to but doesn’t include the +y axis, and so on). The segment in the first quadrant starts at (x0y0) and ends at (x0+∆1y0+∆2). Being in the first quadrant, and the square having sides of nonzero length, means ∆1>0 and ∆2≥0. Then the other two vertices are (x0+∆2y0–∆1) and (x0+∆1+∆2y0+∆2∆1). The width (in the x direction) of the square is ∆1+∆2 as is its height (in the y direction). This means that if we have dots in an by n array the largest allowable value for ∆1+∆2 is (n–1). In that case there is only one way to make a square of that size in the array. If ∆1+∆2 is (n–2) then there are two horizontal and two vertical positions for the square, or a total of four such squares; if (n–3) there are nine such squares, and so forth.

So for instance, if n=4, we have 9 squares with ∆1=1, ∆2=0:

4 squares with ∆1=2, ∆2=0:

4 squares with ∆1=1, ∆2=1:

and 1 square each with ∆1=3, ∆2=0; ∆1=1, ∆2=2; and ∆1=2, ∆2=1:

for a total of 20.

In fact if you think about it, there will be:

  • 1 square each with ∆1=n–1, ∆2=0; ∆1=n–2, ∆2=1; ∆1=n–3, ∆2=2; … ∆1=1, ∆2=n–2
  • 4 squares each with ∆1=n–2, ∆2=0; ∆1=n–3, ∆2=1; ∆1=n–4, ∆2=2; … ∆1=1, ∆2=n–3
  • 9 squares each with ∆1=n–3, ∆2=0; ∆1=n–4, ∆2=1; ∆1=n–5, ∆2=2; … ∆1=1, ∆2=n–4

and so on. For n=2 this is just 1 x 1; for n=3, 1 x 2 + 4 x 1; for n=4, 1 x 3 + 4 x 2 + 9 x 1; and in general:

sum (i = 1 to n-1) [i2 x (ni)]

= n x sum (i = 1 to n-1) [i2] – sum (i = 1 to n-1) [i3]

As everyone knows (well, as everyone can Google), the first sum is (n–1)n(2n–1)/6 and the second is [(n-1)n/2]2. So the number of squares for an array of n by n dots is

N(n) = (n–1)n2(2n–1)/6 – [(n-1)n/2]2

For n = 2 to 10 this is:

N(2) = 1
N(3) = 6
N(4) = 20
N(5) = 50
N(6) = 105
N(7) = 196
N(8) = 336
N(9) = 540
N(10) = 825

and, to answer the Enigma, N(n) = 4n2 for n = 7.

Advertisements

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