A gardener collected 17 apples...

[Hill]

Homework Statement

A gardener collected 17 apples...
He finds that each time he removes an apple from his harvest, he can split the remaining apples in two piles of equal weight, each containing 8 apples. Show that all apples are the same weight.

Relevant Equations

Linear algebra

In fact, it WAS a homework couple of years ago, and I've solved it, kind of (below). I still would like to find a cleaner solution.
Here is what I did.

Let's say, the apples are labeled, and their weights are $x_1, x_2, ...$. He takes out the apple #1 and finds that, e.g., $x_2+x_5+x_9+... = x_3+x_4+x_6+...$. Then he puts the #1 back, takes out #2, and finds that $x_1+x_7+...=x_3+x_8+...$. And so, 17 times. Each side of each equation has 8 apple weights in it. We are asked to show that $x_1=x_2=x_3=...$.

In terms of linear algebra, the problem can be expressed as the matrix equation, $A x = 0$, where $x$ is a vector of $x_1, x_2, ... , x_{17}$, $A$ is a 17x17 matrix with 0 along the diagonal, and +1 or –1 at the other positions such that each row has eight +1s and eight –1s, $0$ is the 17-component zero vector.

From the equation, $x$ is the null space (the kernel) of A. The problem is to show that for all matrices $A$ of this form, the null space has rank 1. For this, rank of A has to be 16. That is, if we take a 16x16 minor matrix of A, its determinant is not 0. So, we take a 16x16 matrix with 0s on diagonal and 1s and -1s everywhere else and consider its determinant.

The determinant is sum of products of all possible permutations of matrix elements, one from each row and from each column, with corresponding coefficients 1 or -1.

The terms that include 0s from the diagonal are 0s and don't contribute to the sum. Each row has 15 non-zeroes. There are 16 rows. So, there are 15^16 combinations of 1s or -1s. This is an odd number.

For every two rows, 14 non-zero pairs are from a same column. These do not contribute to the determinant. There are 14 times a number of pairs of rows of such permutations, which is an even number.

After removing the latter even number from the odd number above (i.e. from 15^16) we are left with some odd number of terms that contribute to the determinant. Each term is equal to either 1 or -1 and contributes with a coefficient of either 1 or -1. Thus, the determinant is a sum of odd number of 1s and -1s.

Here comes the punch line: No sum of odd number of 1s and -1s makes 0 !!!

So, determinant of this 16x16 matrix is not 0. QED.

But there is some handwaving there, isn't it? Is there a better way to solve it?

 

[nuuskur]

The abstraction is correctly formulated. We leave out each apple one by one and then by assumption there is some combination of $\pm 1$ (eight of each) that yields the sum of the remaining weights to be zero.

Hence we want $0$ to be an eigenvalue and its corresponding subspace to be generated by, without loss of generality, the constant vector $x_n:=(1,1,\ldots, 1)$ ($n$ times). Clearly, $Ax_n=0$ holds.

It suffices to prove the following general statement. For any square matrix $A$ of odd dimension with zeroes on diagonal and equally many $+1$ and $-1$ on each row, its rank is precisely $n-1$. Which should work out by induction.

edit: on second thought, induction might be messy.

I sketched some proof attempt but the main thing I'm too tired to tackle right now is the following.

Consider such matrix $A$ of odd dimension $n+1$. Let $B$ be the submatrix obtained with first $n$ rows and columns. Next, consider $S-E$, where $S$ is $n\times n$ where all entries are $1$ and $E$ is the identity. Show that $\det B$ and $\det (S-E)$ have the same parity.

From there we have only eigenvalues of $S$ are $n$ and $0$, hence $\det (S-E)=(n-1)^a(-1)^b$, which is odd, so $\det B$ must be nonzero. Hence, by maximality, $\mathrm{rank}A=\mathrm{rank}B=n$.

 

[Hill]

I've tried induction then and again now after your suggestion. It went nowhere.

I have noticed that in my original attempt the fact that the numbers of $+1$ and of $-1$ in each row are equal, is not explicitly used. But this fact is crucial. Without this restriction there are solutions other than equal weights of all apples. Do you employ it in your sketch?

I sketched some proof attempt but the main thing I'm too tired to tackle right now is the following.

Consider such matrix $A$ of odd dimension $n+1$. Let $B$ be the submatrix obtained with first $n$ rows and columns. Next, consider $S-E$, where $S$ is $n\times n$ where all entries are $1$ and $E$ is the identity. Show that $\det B$ and $\det (S-E)$ have the same parity.

From there we have only eigenvalues of $S$ are $n$ and $0$, hence $\det (S-E)=(n-1)^a(-1)^b$, which is odd, so $\det B$ must be nonzero. Hence, by maximality, $\mathrm{rank}A=\mathrm{rank}B=n$.

 

[WWGD]

A technicality, sorry. You can't have x being the kernel of the ( map associated with the) matrix, unless x is the 0 vector and the matrix is nonsingular. The kernel is a subspace, thus it's the 0 vector or it's infinite in cardinality.

 

[Hill]

A technicality, sorry. You can't have x being the kernel of the ( map associated with the) matrix, unless x is the 0 vector and the matrix is nonsingular. The kernel is a subspace, thus it's the 0 vector or it's infinite in cardinality.

I should've said that $x$ is in the null space / kernel of $A$. Is this correct?

 

[WWGD]

Yes, since it was in the Math section, I thought Id bring it up.

 

[Hill]

Yes, since it was in the Math section, I thought Id bring it up.

And you were right. Thank you.

 

[WWGD]

I would suggest trying this for values of n smaller than 17. Maybe starting with n=5.

 

[nuuskur]

A thought.

Let $A$ be $n\times n$ such that diagonal elements are even and other elements are odd. Consider this problem modulo $2$. Then $A$ will have zeroes on the diagonal and ones everywhere else. Calculate its determinant with row/column operations - turn it into lower triangle matrix, then it should work out that $\det A = n+1\pmod 2$.

Apply the above to the $B$ we had in #2. (The eigenvalue argument is redundant, even)

The equal amount of $\pm 1$ in each row is required simply for $(1,1,\ldots, 1)$ to be a solution. The remaining task is to show it's the only solution up to multiples of $\lambda$.

I can write out the details if necessary, will be busy for a few days, though.

 

[Hill]

I've started to suspect that my conversion of the original problem into the linear algebra equation is incorrect. Here is why.

Let's suspend the requirement that after removing any apple the rest are always split into two piles of eight apples each. Then, $x_1=x_2=...=x_{17}=1$ is a solution, but $x_1=15, x_2=x_3=...=x_{17}=1$ is a solution, too. In the second case, when $x_1$ is removed, the rest are split into two piles of eight apples each, but if any other apple is removed, the rest are split into one "pile" containing $x_1$ and another pile containing all other apples. These different solutions of the original problem correspond to different $A$'s.

 

[nuuskur]

Let's suspend the requirement that after removing any apple the rest are always split into two piles of eight apples each.

Then we will have changed the problem statement. It is correct to view the initial problem as a matrix in the way you described. Give me a few days, I will suspend your disbelief

 

[Hill]

Then we will have changed the problem statement.

Of course. It was to demonstrate that different $A$'s can have different solutions. Maybe different $A$'s with equal numbers of $+1$ and $-1$ in each row can have different solutions, too? Proving that one $A$ like that has only one solution would not solve the problem then.

Give me a few days

No problem. As I said, it is not for homework anymore, just for fun. Thank you for playing.

 

[Hill]

I think I know the answer to my previous comment:

Any $A$ with equal numbers of $+1$ and $-1$ in each row has the solution of all apples having equal weight. So, if it is the only solution for any such $A$, then it is the only solution for the original problem.

We can continue now...

 

[Hill]

Two years later, inspired by PF, I've managed to make exact my original solution and thus to solve the problem cleanly. Here we go.

We got a matrix $M$, $n \times n$, with $0$'s on the diagonal and $\pm 1$'s everywhere else. To evaluate its determinant, let's consider the Leibniz formula: $$det(M)=\sum \epsilon_{i_1...i_n}a_{1i_1}...a_{ni_n}$$
There are $n!$ terms with $\epsilon_{i_1...i_n}=\pm1$ corresponding to $n!$ permutations of non-repeating indices $i_1...i_n$. Among these terms, all terms which include diagonal elements of $M$ equal $0$, and other terms equal $\pm 1$. Let's count the zero terms.
If we pick a zero element on some row then there are $(n-1)!$ permutations of the elements from other rows. Since there are $n$ rows, we get a total of $\begin{pmatrix} n\\1 \end{pmatrix} (n-1)!$ of permutations which contribute $0$ to the determinant. Removing them, we are left with
$$n!-\begin{pmatrix} n\\1 \end{pmatrix} (n-1)!$$ terms.
But we've removed too many terms: there are terms with two diagonal zeroes in them and we have removed them twice. Putting them back, we get $$n!-\begin{pmatrix} n\\1 \end{pmatrix} (n-1)!+\begin{pmatrix} n\\2 \end{pmatrix} (n-2)!$$ terms.
But we've put back too many terms: there are terms with three diagonal zeroes ... etc. After all, the total number of non-zero terms, i.e. $\pm1$ terms in the Leibniz formula is $$n!-\begin{pmatrix} n\\1 \end{pmatrix} (n-1)!+\begin{pmatrix} n\\2 \end{pmatrix} (n-2)!-\begin{pmatrix} n\\3 \end{pmatrix} (n-3)!+...\begin{pmatrix} n\\n \end{pmatrix} (n-n)!$$ After simplifying, there are $$\frac {n!} {2!} - \frac {n!} {3!} +...\frac {n!} {n!}$$ $\pm1$ terms.
In our case, $n=16$. All terms in the formula above except the last one are even and the last term $\frac {n!} {n!}=1$. Thus, the determinant in our case is a sum of odd number of $\pm1$'s, which is certainly not $0$.
QED

 

[PeroK]

We got a matrix $M$, $n \times n$, with $0$'s on the diagonal and $\pm 1$'s everywhere else. To evaluate its determinant, let's consider the Leibniz formula: $$det(M)=\sum \epsilon_{i_1...i_n}a_{1i_1}...a_{ni_n}$$

Perhaps I don't know enough linear algebra, but I don't follow this at all. Can you explain what you are doing with the original matrix, in terms of rank, nullity and minor matrices? How does $M$ relate to $A$?

In particular, why are the zeroes on the diagonal of the minor matrix? Although, I'm not sure that matters in the subsequent counting.

Note: your proof, if valid, is valid for all even $n$. I.e. all odd numbers of apples.

 

[Hill]

Can you explain what you are doing with the original matrix, in terms of rank, nullity and minor matrices?

In particular, why are the zeroes on the diagonal of the minor matrix?

I copy the relevant part of the OP that, I hope, answers these questions:

Homework Statement: A gardener collected 17 apples...
He finds that each time he removes an apple from his harvest, he can split the remaining apples in two piles of equal weight, each containing 8 apples. Show that all apples are the same weight.
Relevant Equations: Linear algebra

Let's say, the apples are labeled, and their weights are x1,x2,.... He takes out the apple #1 and finds that, e.g., x2+x5+x9+...=x3+x4+x6+.... Then he puts the #1 back, takes out #2, and finds that x1+x7+...=x3+x8+.... And so, 17 times. Each side of each equation has 8 apple weights in it. We are asked to show that x1=x2=x3=....

In terms of linear algebra, the problem can be expressed as the matrix equation, Ax=0, where x is a vector of x1,x2,...,x17, A is a 17x17 matrix with 0 along the diagonal, and +1 or –1 at the other positions such that each row has eight +1s and eight –1s, 0 is the 17-component zero vector.

From the equation, x is ln the null space (the kernel) of A. The problem is to show that for all matrices A of this form, the null space has rank 1. For this, rank of A has to be 16. That is, if we take a 16x16 minor matrix of A, its determinant is not 0. So, we take a 16x16 matrix with 0s on diagonal and 1s and -1s everywhere else and consider its determinant.

 

[PeroK]

I copy the relevant part of the OP that, I hope, answers these questions:

Okay.

From the equation, $x$ is the null space (the kernel) of A. The problem is to show that for all matrices $A$ of this form, the null space has rank 1. For this, rank of A has to be 16. That is, if we take a 16x16 minor matrix of A, its determinant is not 0.

What you are saying here is that, for example, a 3x3 matrix has rank 2 iff the minor matrix without the first row and column has rank 2?

 

[WWGD]

I would suggest trying this for values of n smaller than 17. Maybe starting with n=5.

 

[PeroK]

I would suggest trying this for values of n smaller than 17. Maybe starting with n=5.

We've got a provisional proof on the table for all odd $n$.

 

[PeroK]

@Hill here's an idea. Look at the characteristic polynomial for the original matrix $A$. Use your counting technique to show that the coefficent of $\lambda$ is non-zero. It should be an odd number of $\pm 1$. This implies that the nullity is one dimensional, as required.

 

[Hill]

Okay.

What you are saying here is that, for example, a 3x3 matrix has rank 2 iff the minor matrix without the first row and column has rank 2?

Not exactly. A 3x3 matrix has rank 2 iff at least one of its minors (i.e. 2x2) has rank 2 and it itself does not have rank 3.

 

[Hill]

I would suggest trying this for values of n smaller than 17. Maybe starting with n=5.

I did. It works. (If I did not make a counting mistake.)

 

[PeroK]

Not exactly. A 3x3 matrix has rank 2 iff at least one of its minors (i.e. 2x2) has rank 2 and it itself does not have rank 3.

That makes sense now.

I did. It works. (If I did not make a counting mistake.)

I think your counting works. Alternatively, as above, you could do something similar with the characteristic polynomial of the original matrix to get an odd sum of $\pm \lambda$ terms. And we already know the constant term is zero, because the matrix has a zero eigenvalue.

 

[Hill]

An immediate check of the counting formula is easy with 3x3 determinant. In this case the count should be $\frac {3!}{2!}-\frac {3!}{3!}=2$. Let's take a determinant $$\begin{vmatrix} 0&a&b\\c&0&d\\e&f&0 \end{vmatrix}$$ It indeed has two non-zero terms: $ade+cfb$.

 

[PeroK]

An immediate check of the counting formula is easy with 3x3 determinant. In this case the count should be $\frac {3!}{2!}-\frac {3!}{3!}=2$. Let's take a determinant $$\begin{vmatrix} 0&a&b\\c&0&d\\e&f&0 \end{vmatrix}$$ It indeed has two non-zero terms: $ade+cfb$.

Your sequence is here:

https://oeis.org/search?q=2,+9,+44,+265&language=english&go=Search

 

[Hill]

Your sequence is here:

https://oeis.org/search?q=2,+9,+44,+265&language=english&go=Search

Thank you. Here is a quick Excel spreadsheet to confirm the count for n=10:

 

[PeroK]

I did it like this. The second sequence is $(n+1)$ times the sequence you found. That the number of terms in $\lambda$ in the characteristic polynominal of the original matrix. That sequence is here:

https://oeis.org/search?q=3,+8,+45,+264&language=english&go=Search

n

n!

2​

6​

24​

120​

720​

5040​

40320​

362880​

3628800​

2​

2​

1​

1​

3​

6​

3​

1​

2​

3​

4​

24​

12​

4​

1​

9​

8​

5​

120​

60​

20​

5​

1​

44​

45​

6​

720​

360​

120​

30​

6​

1​

265​

264​

7​

5040​

2520​

840​

210​

42​

7​

1​

1854​

1855​

8​

40320​

20160​

6720​

1680​

336​

56​

8​

1​

14833​

14832​

9​

362880​

181440​

60480​

15120​

3024​

504​

72​

9​

1​

133496​

133497​

10​

3628800​

1814400​

604800​

151200​

30240​

5040​

720​

90​

10​

1​

1334961​

1334960​

 

[PeroK]

@Hill it was a good effort to solve that. It was a hard problem.

 

[Hill]

@Hill it was a good effort to solve that. It was a hard problem.

Thank you.

 

[PeroK]

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.

 

[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!