A gardener collected 17 apples...

[Hill]

I've learned something new. The permament of a matrix:

https://en.wikipedia.org/wiki/Permanent_(mathematics)

This simplifies the counting, since the number of terms in the determinant for $M$ is the permanent of the matrix $M'$, where all the $\pm 1$ entries are $1$. And, the recurrence relation for the permanent of $M'$ is easy to show:
$$a(n) = (n-1)[a(n-1) + a(n-2)] = na(n-1) + (-1)^n$$This is clearly odd when $n$ is even.

Yes, new to me and good to know, especially for problems involving counting.

It explicitly shows the formula I've arrived to:

I suspect that because permanent of a matrix is basis dependent, its use in physics is limited.

 

[nuuskur]

Let $X$ be an $n\times n$ matrix with even numbers on the diagonal, and odd numbers everywhere else. Then $\det X = n+1\pmod 2$.

Pf. Consider $X$ modulo $2$. Then its diagonal is zero and there are ones everywhere else. Let $S$ be an $n\times n$ matrix whose every entry is $1$. The eigenvalues of $S$ are precisely $n$ and $0$. Therefore, $S-I_n$ has eigenvalues $n-1$ and $-1$. Hence $\det (S-I_n) = (n-1)^a(-1)^b$. Thus, the parity of $\det X$ is $n+1\pmod{2}$. $_{\blacksquare}$

Now, let $n+1\geqslant 3$ be odd and $A$ a square matrix of dimension $n+1$ such that its diagonal is zero and there are equal number of $\pm 1$ on each row. Since $A(1,1,\ldots, 1)^t=0$, we have that $\mathrm{rank}A \leqslant n$. Consider the $n\times n$ submatrix obtained from first $n$ rows and columns. By the previous claim, its determinant is an odd number, hence $\mathrm{rank}A = n$.

Thus, in the initial problem, the vector $(1,1,\ldots ,1)$ generates the kernel of $A$. Hence, every apple must have the same weight.

 

[Hill]

Let $X$ be an $n\times n$ matrix with even numbers on the diagonal, and odd numbers everywhere else. Then $\det X = n+1\pmod 2$.

Pf. Consider $X$ modulo $2$. Then its diagonal is zero and there are ones everywhere else. Let $S$ be a matrix whose every entry is $1$. The eigenvalues of $S$ are precisely $n$ and $0$. Therefore, $S-I_n$ has eigenvalues $n-1$ and $-1$. Hence $\det (S-I_n) = (n-1)^a(-1)^b$. Thus, the parity of $\det X$ is $n+1\pmod{2}$. $_{\blacksquare}$

Now, let $n+1\geqslant 3$ be odd and $A$ a square matrix of dimension $n+1$ such that its diagonal is zero and there are equal number of $\pm 1$ on each row. Since $A(1,1,\ldots, 1)=0$, we have that $\mathrm{rank}A \leqslant n$. Consider the $n\times n$ submatrix obtained from first $n$ rows and columns. By the previous claim, its determinant is an odd number, hence $\mathrm{rank}A = n$.

Thus, in the initial problem, the vector $(1,1,\ldots ,1)$ generates the kernel of $A$. Hence, every apple must have the same weight.

Thank you. This is much shorter and more elegant than my solution. No explicit counting needed. Beautiful!