Enigma 1760

Spoiler for New Scientist Enigma 1759: “Squares and cubes” (Follow the link to see the puzzle.)

The number which is both a square and a cube must be a sixth power: 2⁶ = 8² = 4³ = 64, or 3⁶ = 27² = 9³ = 729.

Note that the only cubes with 2 or 3 digits are 27, 64, 125, 216, 343, 512, and 729.

Try 64 at 6 down. Then 6 across must be a square: 625 or 676. If 625 then 5 down has middle digit 5 which means it’s 256. Then 7 across can only be 64, which duplicates. If 6 across is 676 then there is no possibility for 2 down. So 6 down is not 64.

Try 64 at 3 down. Then 4 across is 144, 324, 484, or 784. If 144 then 2 down must be 216 or 512. The former leaves nothing for 1 across; the latter forces 1 across to be 25. 5 down must be 441 or 484 (400 is ruled out because we don’t allow a leading zero for 7 across), but no 3-digit cube ends with 8 so it’d have to be 441. Then 7 across must be 16, 6 across is 324, and 6 down is 36. If 4 across is 324 the middle digit of 2 down is 3, but there are no 3-digit squares or cubes with 3 as the middle digit. If 4 across is 484 or 784 then 5 down is 841 and 7 across is 16. In the 484 case 2 down must be 144 or 441 or 841, none of which leaves anything for 6 across. In the 784 case 2 down must be 576 or 676 either of which leaves nothing for 6 across.

The other possibilities are 729 at 2 down or 5 down. 5 down doesn’t work because it leaves nothing for 7 across.

With 729 at 2 down, 6 across can only be 196, with 6 down being 16. Then 5 down must be 169, 361, or 961. The first leaves nothing for 7 across while the latter two leave only 16, which duplicates.

So there is indeed only one solution:

2	5		6
	1	4	4
3	2	4
6		1	6

Advertisements

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 (x0, y0) and ends at (x0+∆1, y0+∆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+∆2, y0–∆1) and (x0+∆1+∆2, y0+∆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 n 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) [i² x (n–i)]

= n x sum (i = 1 to n-1) [i²] – sum (i = 1 to n-1) [i³]

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]². So the number of squares for an array of n by n dots is

N(n) = (n–1)n²(2n–1)/6 – [(n-1)n/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) = 4n² for n = 7.

Enigma 1712

Spoiler for New Scientist Enigma 1712:

Find the set of perfect squares that between them use each of the digits 0 to 9 exactly twice and whose sum is as small as possible. Your squares must all be different, and 0 may not be a leading digit.

What is the sum of your set of squares?

The squares up to 529 (the square of 23) contain more than two of every digit except 7, which doesn’t appear even once; the smallest 7-containing squares are 576, 676, 729, 784, 1764… Other “difficult” digits are 0 (occurring in 100, 400, 900, 1024, 1089, 1600…), 3 (in 36, 324, 361, 1369…) and 8 (in 81, 289, 484, 784, 841, 1089, 1681…). Since 7 looks like the toughest constraint let’s start with 576 and 729 (we can’t use 576 and 676, that’s three 6s already). To that we can add 100 for the two 0s and 36 and 324 for the two 3s. But then for the two 8s we need 81 and… something >1999. That doesn’t look good.

Since 8 creates the problem here, let’s start with 7 and 8. Use 576 and 729 for the 7s, 81 and 289 for the 8s. Then 100 for the 0s. For the 3s, 36 and… no, 324, 361, and 1369 don’t work, and anything larger will make too large a sum. 484 instead of 289 still doesn’t allow 324, 361, or 1369. Nor does 676 instead of 576.

So it seems for our 7s and 8s we can’t find anything better than 81, 576, and 784. Then add 100, 36, and 324. For our first 9 we can use 9. That leaves us needing one each of 2, 5, and 9. We can’t use 9 and 25 since we’ve already used 9, but we can use 529 (the aforementioned square of 23). That gives us: 9+36+81+100+324+529+576+784=2439.

Is that a proof? I’m not sure there are no holes in it. But I’m fairly confident this is the smallest possible sum.