17 apples

[Genady]

A friend has sent this question to me. I have it solved with linear algebra (and some hand waving). Can you find a shorter way to the answer? (It's not a homework, not mine anyway. My homework times long gone.)

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

[Genady]

Here is how I reformulate the puzzle to make it clearer without, hopefully, pushing a specific way of solution:

Let's say, the apples are marked 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+x4...

Etc. 17 times. Each side of each equation has 8 apple weights in it.

We are asked to show that x1=x2=x3...

[Genady]

Oh, well... Just to close the case:

In terms of linear algebra, the problem can be expressed as the matrix equation

A x = 0

where:

x is the 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 the null space (the kernel) of A. The problem is to show that for all matrices A satisfying the above, the null space x is:

x1 = k
x2 = k
···
x16 = k
x17 = k

where k is an arbitrary value.

In other words, null space x 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 combinations of matrix elements, one from each row and from each column, with corresponding coefficients 0, 1 or -1.

The combinations 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 because the corresponding coefficient in the determinant formula is 0. There are (14 times a number of pairs of rows) of such combinations, 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 products that do contribute to the determinant. Each product 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.

 

Edited December 30, 2021 by Genady

[Ghideon]

Quick try at a different approach:

Spoiler

Assume the gardener has successfully created the two sets S₁ and S₂ containing weights of i apples. S₁ contains weights w₁₁ , w₁₂, .... , w_1i of apples and S₂ contains weights w₂₁ , w₂₂, .... , w_2i . The sum of the weights in S₁ and sum of the weights in S₂ are identical as required in OP. The gardener has one additional apple of weight W. When the gardener removes any one of the apples in S₁ or S₂ and inserts the apple W he finds that the weight does not change. This means that the weight W equals the weight of the removed apple: W=w₁₁ , W=w₁₂, .... , W=w_{1i ,} W=w₂₁ , W=w₂₂, .... , W=w_2i or, in other words, all apples have identical weights.

 

[Genady]

7 minutes ago, Ghideon said:

Quick try at a different approach:

  Hide contents

When the gardener removes any one of the apples in S₁ or S₂ and inserts the apple W he finds that the weight does not change.

 

It is not necessarily so. According to the puzzle, after removing and inserting he might need to rearrange the other apples between the two sets to get equal weights again.

[John Cuthber]

Imagine I arrange the apples in three piles of 1, 8 and 8 apples.

The two piles of 8 apples have the same weight.

Imagine that I swap the single apple for one from one of the other two piles.

The mass of that pile of apples must still be the same as the other pile of 8.

But that's only possible if the 1 apple has the same mass as any of the apples in that pile.

And that's also true if I swap the singleton with an apple from the other pile.
In fact, there's no significance to the two piles of 8, you can consider them as a single pile of 16.
The mass of that pile must be unchanged by exchange of any pair of apples.
That's only possible if they all have the same mass.

[Genady]

Just now, John Cuthber said:

The mass of that pile of apples must still be the same as the other pile of 8.

It is not necessarily so. It could be different. The puzzle says, that after the swapping and some possible rearrangement of other apples between the piles he gets equal weights again.