1. 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.  2.

3. Question is confusing. Does he keep repeating with the same 17 apples or does he keep this up with 17 new apples each time?  4. They are the same original 17 apples he keeps "playing" with.  5. Is everything random? Choice of first app;e? division of remaining 16?  6. Sorry for the confusing language of the puzzle. The friend I got it from lives in Belgium. Perhaps he translated it from French or Dutch.
Anyway, it is not random. For clarity, 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 apples. We need to show that x1=x2=x3...  7. It looks like removing each apple has no effect on the remaining weight, so they all must have the same weight.  8. "It looks like removing each apple has no effect on the remaining weight"
How come? I don't see it. Why it can't be that after removing #1 the remaining weight is 24, while after removing #2 the remaining weight is 28, and so on? Could you elaborate?  9. Originally Posted by mathman It looks like removing each apple has no effect on the remaining weight, so they all must have the same weight.
Agree. If each apple weighs x then you’re always left with 16x or (8x + 8x) no matter what apple is removed.  10. Originally Posted by zinjanthropos  Originally Posted by mathman It looks like removing each apple has no effect on the remaining weight, so they all must have the same weight.
Agree. If each apple weighs x then you’re always left with 16x or (8x + 8x) no matter what apple is removed.
But we don't know yet that "each apple weighs x". This is exactly what we are asked to show in this puzzle.  11. This problem has captured my interest and is not straightforward. In terms of linear algebra, it can be expressed as the following matrix equation:

A x = 0

where:

x is the 17-component vector representing the weights to be solved
A is a 17x17 matrix with 0 along the diagonal, and +1 or –1 at the other positions such that each row has eight +1 and eight –1
0 is the 17-component zero vector

From the above, x is the null space, also known as the kernel, of the linear map. 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.

It seems to me that this can be proven by showing that the given null space x is a solution to the equation for all A, and that the rank of A is 16, thus showing by the rank–nullity theorem that the null space is one-dimensional, and therefore that the given null space solution is unique up to arbitrary value k.  12. Right. So far, this was precisely my approach. My next step was this:

We want to show that rank of A is equal 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...  13. Originally Posted by tsfgenady Right. So far, this was precisely my approach. My next step was this:

We want to show that rank of A is equal 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...
An easier approach would be to convert the matrix A to either row echelon form or column echelon form (the choice depends on the definition of A). In echelon form, the rank of A is simply the number of non-zero rows or columns.

However, for a given location of the 0 in a row of A, there are ½ * 16! / (8!)² = 6435 inequivalent arrangements of eight +1 and eight –1 in the row. So converting all possible A to echelon form will require ingenuity.  14. I didn't find yet how to deal with these echelon structures generically. Here is my thinking of the determinant of a mentioned 16x16 minor matrix.

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 sum is 0. There are 14x(number of pairs of rows) of such, 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. Now comes a punch line: No sum of odd number of 1s and -1s makes 0 !!!

So, the determinant of this 16x16 matrix is not 0. QED.  15. I created a Microsoft Excel spreadsheet that performs a step-by-step Gaussian elimination on a randomised 17x17 matrix A to obtain the matrix in column echelon form. Column echelon form was chosen over row echelon form because it is the rows of A that have eight +1 and eight –1, whereas the columns of A have no such requirement. Each recalculation of the spreadsheet generates new random values, and pressing then holding down the "delete" key in a selected unused cell causes rapid generation of new matrix values, which allows one to see what changes and what does not change. One notable thing that does not change is that immediately before the final step, the rightmost column is the negative of the column next to it.

However, it should be noted that what needs to be proven is that there is no more than one zero column in the column echelon form, not that there is a zero column. That's because the existence of a non-trivial null space solution is straightforward to prove by showing that the solution we have is indeed a solution.

Before creating the spreadsheet dealing with the full 17x17 matrix, I manually investigated the 3x3 case. I was able to consider a sufficiently general form of the 3x3 matrix to be able to prove the desired result for three apples. Interestingly, immediately before the final step, the rightmost column is the negative of the column next to it. I suspect this to be true for all relevant (2n+1)x(2n+1) matrices.

The spreadsheet is not a proof, but may provide guidance to a proof. One possibility is that the general case of 2n+1 apples can be proven by induction.  16. Very nice. This could be a second solution.  17. I decided to extend my spreadsheet to produce the row echelon form from the column echelon form obtained from A. This is a diagonal matrix. However, there appears to be no regularity in the resultant diagonal elements other than the expected 0 in the bottom-right cell. Not even is the bottom row the negative of the row next to it in the step immediately before the final step. This extension to my spreadsheet appears to produce no new insights other than it produces no new insights.  Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement