Square of 16

Stump your fellow simians.
User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Square of 16

Post by DanishDynamite » Wed Aug 11, 2004 8:56 pm

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.

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

Post by DanishDynamite » Tue Aug 17, 2004 3:48 pm

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

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

Post by DanishDynamite » Fri Aug 20, 2004 3:49 pm

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.

User avatar
xouper
Posts: 8968
Joined: Fri Jun 11, 2004 4:52 am
Location: HockeyTown USA
Has thanked: 238 times
Been thanked: 144 times

Re: Square of 16

Post by xouper » Sat Aug 28, 2004 2:19 pm

DanishDynamite 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?
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.

User avatar
xouper
Posts: 8968
Joined: Fri Jun 11, 2004 4:52 am
Location: HockeyTown USA
Has thanked: 238 times
Been thanked: 144 times

Re: Square of 16

Post by xouper » Sat Aug 28, 2004 6:20 pm

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
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.)

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

Post by DanishDynamite » Mon Aug 30, 2004 8:08 pm

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