Square of 16

[DanishDynamite]

I hesitate to post this puzzle as it is liable to be besmirched by ceptimus's brute force computer. :)

Nevertheless:

For which whole numbers N > 1 can the numbers from 1 to 16 be placed in a 4x4 square such that each row sum and each column sum is not only unique but divisible by N?

Prove it.

[DanishDynamite]

Come now, folks! Get your mathematical butts in gear!

[DanishDynamite]

OK. To get you guys going I'll start the ball rolling.

The sum of the numbers from 1 to 16 is 136. Hence the 4 vertical sums and the 4 horizontal sums must added together make 272. Since each sum must unique and yet divisible by N, we get that 272 >= N + 2N + 3N + ... + 8N = 36N. Hence N <= 272/36 <= 7. There, we've already narrowed down N to at most 7 numbers.

What else do we know? Well, we know that although the 8 sums might not be the consecutive sums seen above (i.e. they could be N, 3N, 4N, 6N, ... ), they will all be divisible N. And if each sum is divisible by N, what can we deduce about whether the sum of the sums is divisible by N? Does the answer make primes of interest?

There. I've almost solved it. The rest is up to you guys.

[xouper]

For which whole numbers N > 1 can the numbers from 1 to 16 be placed in a 4x4 square such that each row sum and each column sum is not only unique but divisible by N?

Given the constraints of the puzzle, we are looking for eight integers

0 > a > b > c > d > e > f > g > h

such that the sums of each of the rows and columns are as follows (in no particular order):

a*N
b*N
c*N
d*N
e*N
f*N
g*N
h*N

Since the sum of the numbers 1 to 16 is 136, the total sum of the rows and columns must be:

a*N + b*N + c*N + d*N + e*N + f*N + g*N + h*N = 272

or

a + b + c + d + e + f + g + h = 272 / N

The divisors of 272 are {1, 2, 4, 8, 16, 17, 34, 68, 136, 272}, so those are the only possible values for N.

From the definition of the puzzle, N cannot be 1, which is a trivial result anyway.

Since the smallest possible sum of a+b+c+d+e+f+g+h is 36,
and since 36 > 272/8, we can eliminate N>=8.

That leaves N=2 or N=4. And that's my answer.

Here's one possible arrangement that works for N=4 (sums are in bold):

<table cellpadding="6" cellspacing='0' border="1"><tr><td>1</td><td>3</td><td>5</td><td>7</td><td>16</td></tr><tr><td>4</td><td>2</td><td>8</td><td>6</td><td>20</td></tr><tr><td>9</td><td>11</td><td>13</td><td>15</td><td>48</td></tr><tr><td>10</td><td>12</td><td>14</td><td>16</td><td>52</td></tr><tr><td>24</td><td>28</td><td>40</td><td>44</td></tr></table>

QED.

[xouper]

Given the constraints of the puzzle, we are looking for eight integers

0 > a > b > c > d > e > f > g > h

such that the sums of each of the rows and columns are as follows (in no particular order):

a*N
b*N
c*N
d*N
e*N
f*N
g*N
h*N

Just for grins, from the example given for N=4, we can go back and determine the values for those eight integers:

Code: Select all

row1 = a*N =  4*4 = 16
row2 = b*N =  5*4 = 20
col1 = c*N =  6*4 = 24
col2 = d*N =  7*4 = 28
col3 = e*N = 10*4 = 40
col4 = f*N = 11*4 = 44
row3 = g*N = 12*4 = 48
row4 = h*N = 13*4 = 52

So we have indeed found eight integers matching the requirement

0 > 4 > 5 > 6 > 7 > 10 > 11 > 12 > 13

And the sum of the rows and columns

16 + 20 + 24 + 28 + 40 + 44 + 48 + 52 = 272

as predicted.





(Off-topic whine - This forum is brain dead when it comes to html. I would have prefered to use html instead of the

Code: Select all

 tag for formatting the above list.  People ask, "what do you need THAT tag for?"  Well, now you know.)

[DanishDynamite]

Well done, xouper. Finally, this baby has been attended to in the manner it deserved. :)