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.
Square of 16

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
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.
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.

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
Re: Square of 16
Given the constraints of the puzzle, we are looking for eight integersDanishDynamite wrote: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?
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.

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
Re: Square of 16
Just for grins, from the example given for N=4, we can go back and determine the values for those eight integers:xouper wrote: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
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
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.
(Offtopic 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.)

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen