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.

[Commander]

Hi
Thank you for informing me about this puzzle and asking for my Solution to it

My approach will be like this 

Let us take 17 apples x1, x2 … x17
Let their weights in Grams be
201, 203,205, etc upto 231 as consecutive odd numbers
The total sum is an odd number adding 17 Odd numbers 
If we remove any one apple the rest of the 16 apples add to an even number

I find in this setup I can have two equal halfs if any Apple is removed

Therefore you can inform your farmer friend that all apples need not be of equal weight and if you can have two equal weights of the remaining 16 apples does not prove that all apples are equal in weight

BTW in real life no two apples can have exact weight saying in a lighter vein !

[Genady]

2 hours ago, Commander said:

Hi
Thank you for informing me about this puzzle and asking for my Solution to it

My approach will be like this 

Let us take 17 apples x1, x2 … x17
Let their weights in Grams be
201, 203,205, etc upto 231 as consecutive odd numbers
The total sum is an odd number adding 17 Odd numbers 
If we remove any one apple the rest of the 16 apples add to an even number

I find in this setup I can have two equal halfs if any Apple is removed

Therefore you can inform your farmer friend that all apples need not be of equal weight and if you can have two equal weights of the remaining 16 apples does not prove that all apples are equal in weight

BTW in real life no two apples can have exact weight saying in a lighter vein !

Thank you for your reply.

Unfortunately, there is a mistake in your calculations: 17 apples with the weights you suggest go up to x17 = 233 rather than 231. Thus, their total weight is 3689. 

Let's remove x2 now. The total weight of the remaining 16 apples is 3486. Half of it is 1743. As this is an odd number, there is no way to get it by any combination of 8 of the remaining apples.

Thus, the puzzle is not solved, and I have nothing to inform my farmer friend.

BTW, this is a mathematical puzzle, and they could be snails instead of apples as well. We can use any convenient real numbers. 1 to 33 are easier to deal with than 201 to 233, with the same result.

[Commander]

10 hours ago, Genady said:

Thank you for your reply.

Unfortunately, there is a mistake in your calculations: 17 apples with the weights you suggest go up to x17 = 233 rather than 231. Thus, their total weight is 3689. 

Let's remove x2 now. The total weight of the remaining 16 apples is 3486. Half of it is 1743. As this is an odd number, there is no way to get it by any combination of 8 of the remaining apples.

Thus, the puzzle is not solved, and I have nothing to inform my farmer friend.

BTW, this is a mathematical puzzle, and they could be snails instead of apples as well. We can use any convenient real numbers. 1 to 33 are easier to deal with than 201 to 233, with the same result.

You are right 

I had made a mistake and was about to inform of that here

Thank you for pointing it out and correcting 

Yes 201 to 233 a set of 17 numbers

If any of x1 x3 or such odd suffix is removed it is easy to see the two equal sets

If x2 or any even suffix is removed a different approach is needed

For x2 it is

Some combination I had visualized

I will give it here if I recollect it

If it is really impossible I apologize for my suggestion 

 

[Commander]

I am unable to find a configuration of 17 numbers which are not all equal and removing any one and remaining can be divided into two equal Sums and equal numbers in each group

However I  could find a Combination where after removing one the remaining 16 numbers can be arranged into two sets each adding to the same Sum  but has unequal number of numbers in the sets.

[Genady]

47 minutes ago, Commander said:

but has unequal number of numbers in the sets.

Yes, this is a crucial condition:

On 12/25/2021 at 11:08 AM, Genady said:

two piles of equal weight, each containing 8 apples