Magic cutting squares with given sum

You meet a guy on the road. The following conversation follows:

He: Let's play a game. Give me any natural number from $3$ to $10$. I'll call this number the grid size

You: Okay, $4$.

(He draws a $4$x$4$ grid on a sheet of paper, since you picked $4$)

He: Now give me another integer. Try to give a small one to make our calculations easy. This number will be called our 'sum'.

You: Okay, $9$.

He: Now give me any $4$ integers that add up to $9$.

You: $3,-1,2,5$

(He writes them on the diagonal of the grid)

He: Now give me any $3$ (as $3$ is 1 less than $4$) integers, completely at random.

You: $9,14,-5$

(He writes them on the first row, starting with the 2nd cell, since the first cell was already filled)

The grid looks like

3  9  14 -5
-1
2
5


He fills the rest of the grid himself.

3  9  14 -5
-7 -1 4  -15
-9 -3 2  -17
13 19 24 5


He: Now pick any $4$ cells, such that no $2$ cells share the same row or column.

You: Okay, the $9$ on top, the $4$ in the next row, $-9$ in the third row, and the leaves only $5$ on the last cell.

He: Now add them up.

You: It's $9$! The number I originally picked.

He: Try another set of $4$.

You: $14,-15,-3,13$

You: which again add up to $9$.

What 'trick' did he use, and can you defeat him? Does a exist an allowed grid size and set of input numbers, for which such a 'magic cutting grid' cannot be generated?

• I have proof-read it quite a lot, but since I made a lot of errors initially, I'm still not convinced it's error-free. Please tell me if there are any. – ghosts_in_the_code May 24 '15 at 16:09
• Last sentence: "Does a exist..." instead of "Does there exist...". Otherwise, looks good. :) – AlbeyAmakiir May 24 '15 at 23:05

The grid could be filled by him easily, he only has to solve equations with one unknowns. After my numbers are in the grid, he first calculates the first column:

-7 = 9 - (9 + 2 + 5)

-9 = 9 - (14 -1 + 5)

13 = 9 - (-5 -1 + 2)

Then he calculates the subdiagonals from the top-left to the bottom-right.

4 = 9 - (9 -9 + 5)

-3 = 9 - (14 -7 + 5)

...

It could be done on larger grids as well.

Detailed steps:

Just calculate the first column, then go from the top-left to the bottom-right through the subdiagonals:

Said $a_{i,j}$ the element in the $i_{th}$ row and $j_{th}$ column, we have these properties:

$(a_{i,j}-a_{i,j+1})$ is constant if you vary $i$
$(a_{i,j}-a_{i+1,j})$ is constant if you vary $j$

This means that each row/column is generated adding a constant to the first row/column. For example, in this case the second row is the first minus 10.
When you make the sum, you count exactly one number from the first row, one from the second, one from the third and one from the fourth (same for columns). It doesn't matter which numbers you choose. Why? Check this picture for an intuitive explanation:

Whichever numbers you pick to make your sum, it will always be $A+B+C+D-10-12+10=A+B+C+D-12$

Of course, this can be extended to any square of any size!

Note: this puzzle was proposed by Martin Gardner in one of his books, at least I've read it there for the first time.

Here's how your friend does this trick. Let's say you pick $n$ for the grid size, $S$ for the sum, numbers $t_1,t_2\dots,t_n$ on the top row, and $d_1,d_2,\dots d_n$ on the diagonal, where $t_1=d_1$ and $d_1+\dots+d_n=S$.

Let $r_i=d_i-t_i$. He fills out the entire grid by placing the number $$r_i+t_j$$ in the cell at row $i$ and column $j$. This scheme doesn't conflict with any of the numbers you chose, since on the top row it places $$r_1+t_j=d_1-t_1+t_j=t_j$$ and on the diagonal it places $$r_i+t_i=d_i-t_i+t_i=d_i$$ It also obeys the magic cut requirement; for any $n$ cells you pick, all in different rows/columns, their sum will be $$r_1+\dots+r_n+t_1+\dots+t_n$$ which, since $d_i=r_i+t_i$, is equal to $$d_1+\dots+d_n=S$$ Like magic, your chosen number, $S$, is always the sum. In other words, you cannot defeat him.