Genady Posted December 25, 2021 Share Posted December 25, 2021 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. Link to comment Share on other sites More sharing options...

Genady Posted December 27, 2021 Author Share Posted December 27, 2021 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... Link to comment Share on other sites More sharing options...

Genady Posted December 30, 2021 Author Share Posted December 30, 2021 (edited) 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 Link to comment Share on other sites More sharing options...

Ghideon Posted January 1 Share Posted January 1 Quick try at a different approach: Spoiler Assume the gardener has successfully created the two sets S_{1 }and S_{2 }containing weights of i apples. S_{1 }contains weights w_{1}_{1 }, w_{1}_{2}, .... , w_{1}_{i} of apples and S_{2}_{ }contains weights w_{2}_{1 }, w_{2}_{2}, .... , w_{2}_{i} . The sum of the weights in S_{1} and sum of the weights in S_{2} 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_{1 }or S_{2 }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_{1}_{1 }, W=w_{1}_{2}, .... , W=w_{1i , }W=w_{2}_{1 }, W=w_{2}_{2}, .... , W=w_{2}_{i }or, in other words, all apples have identical weights. Link to comment Share on other sites More sharing options...

Genady Posted January 1 Author Share Posted January 1 7 minutes ago, Ghideon said: Quick try at a different approach: Hide contents When the gardener removes any one of the apples in S_{1 }or S_{2 }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. Link to comment Share on other sites More sharing options...

John Cuthber Posted January 1 Share Posted January 1 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. Link to comment Share on other sites More sharing options...

Genady Posted January 1 Author Share Posted January 1 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. Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now