12
$\begingroup$

Fill in each square of the grid with a number from $1$ to $16$, using each number exactly once. Numbers at the left or top give the largest sum of two numbers in that row or column. Numbers at the right or bottom give the largest difference of two numbers in that row or column.

enter image description here

$\endgroup$
1
  • 8
    $\begingroup$ This is another USAMTS past puzzle that you have not declared as such in the post - it comes from the Round 3 problem set from 2016-17. You must provide attribution for puzzles created by others or sourced from elsewhere. $\endgroup$
    – Stiv
    Jan 5 at 0:34

2 Answers 2

10
$\begingroup$

Very nice puzzle!

enter image description here

@WeatherVane beat me to the answer but thought I'd post with some logical deductions:


Logic on how to solve:

Initial deductions about combinations

Firstly, there are two 28 sums which can only be made by $12+16$ and $13+15$, so one pair must be in each of the two sums' row/column. It also means the $14$ is not in either of these rows/columns, as then the maximum sum would be more than 28.

There are also two 13 sums, each with a max difference of 7. There are also only two ways to each achieve these, but this time we know nearly the entire row: $[9,4,3,2]$ or $[8,5,?,1]$ with $? = 4, 3$ or $2$.
The two sums overlap in the first cell, and the $?$ must be in this cell, although we don't know which digit it is yet.

Now consider the 23 sums. One has a difference of 8, and there are 3 ways this could happen, with $[14,9,?,6]$, $[13,10,?,5]$ or $[12,11,?,4]$ where the $?$ is always between the second and last number. Similarly the 23 with a 12 difference has 4 ways.

Now finally consider the 25 sum. There are 4 ways to make it $[16,9,?,4]$, $[15,10,?,3]$, $[14,11,?,2]$ and $[13,12,?,1]$. But it can't be the $16$ or $13$ option as the $9/4$ and $13/12$ are required in the 13 and 28 sums.

It also cannot be the $15$ option, as the $15$ would have to go in the overlap with 28, and then $13$ can only go on the right to complete the 28 but then both the 25 and 23 column both need a $10$. So the 25 must be $[14,11,?,2]$ and numbers can start to be placed.

Placing numbers

The $2$ must overlap with the 13 sum so goes at the top. That leaves a $4$ or $3$ top left, and we also know which way round the 13 sums go, and the $9$ must be at the top.

Now the $14$ can't overlap with the 28 sum so is in the bottom two rows. But if it is in the 23 sum, a $9$ is required, but that is already required at the top, so it must be second bottom.

enter image description here

If the $11$ now goes on the bottom row, the $12$ must go next to it to complete the 23 but overlap with 28, but then that leaves no place for the $13/15$ pair for the other 28. So the $11$ must be on the second row.

The $14$ cannot have a difference of greater than 8, so no other cell in that row can be below $6$. This means in the first column there must be an $8$ for the 13 sum. The $1$ then has to be on the second row, as if it is on the bottom row then the 23 cannot be made, and hence the $5$ is on the second row.

There is only two places left for the $12/16$ pair to complete the 28 in row 2, and the only number in the pairs for the 28 that can overlap both 28s is the $12$, as it doesn't affect $13+15$, so that goes in the second column, and $16$ in the last.

The 23 sum in the 4th column needs a $4$ for a difference of 12 and this must go in the first row for the 13 sum. This completes the sum and a $9$ can be put in the second column, and a $3$ in the top left.

enter image description here

The 23 sum at the bottom now is from $13+10$, so the $15/13$ pair to complete the remaining 28 pair must have the $13$ at the bottom.

There are $6$, $7$ and $10$ remaining to be placed. The $15$ in the 3rd row now means the remaining cell on the right cannot be below $7$, so the $6$ must be in the bottom row , as does the $10$ for the 23 sum, and the $7$ goes in the 3rd row.

Finally, the $10$ can't go in the final column, otherwise it would make a sum of 26, so it goes in the 3rd column, and we're done!

enter image description here

$\endgroup$
5
  • $\begingroup$ Nice logical approach – it seems we verified each other's solution. $\endgroup$ Jan 3 at 18:48
  • $\begingroup$ @WeatherVane upvoted as thats harsh, maybe add a bit about what the algorithm works would help? $\endgroup$ Jan 3 at 18:48
  • $\begingroup$ Thanks to you :) $\endgroup$ Jan 3 at 18:49
  • $\begingroup$ It also means the 14 is not in either of these rows/columns - Why? $\endgroup$
    – BadHorsie
    Jan 5 at 13:47
  • $\begingroup$ @BadHorsie if 14 was in the same row/column of either of those pairs, you’d be able to create a sum more than 28, so it has to be elsewhere. E.g. if it was the same row as 12+16, the new maximum sum would be 14+16 which isn’t 28 $\endgroup$ Jan 5 at 14:25
6
$\begingroup$

My solution:

enter image description here

Method: programmed recursion in C –
Permute the 16 numbers on the bottom row.
For each arrangement, check the maximum sum and difference tally.
If so, mark those numbers as used and move to the next row up.
Repeat using the available numbers until the top row is solved.
Finally verify that the maxima for each column is correct.
One solution only was found.

  3  9  2  4
  1 12 11 16
  8 15 14  7
  5 13 10  6

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.