Notices
Results 1 to 16 of 16

Thread: 17 apples

  1. #1 17 apples 
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    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.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    1,235
    Question is confusing. Does he keep repeating with the same 17 apples or does he keep this up with 17 new apples each time?


    Reply With Quote  
     

  4. #3  
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    They are the same original 17 apples he keeps "playing" with.
    Last edited by tsfgenady; December 25th, 2021 at 11:12 PM.
    Reply With Quote  
     

  5. #4  
    Forum Professor
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    1,235
    Is everything random? Choice of first app;e? division of remaining 16?
    Reply With Quote  
     

  6. #5  
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    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...
    Reply With Quote  
     

  7. #6  
    Forum Professor
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    1,235
    It looks like removing each apple has no effect on the remaining weight, so they all must have the same weight.
    Reply With Quote  
     

  8. #7  
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    "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?
    Reply With Quote  
     

  9. #8  
    Time Lord zinjanthropos's Avatar
    Join Date
    Dec 2005
    Location
    Driving in my car
    Posts
    5,942
    Quote Originally Posted by mathman View Post
    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.
    All that belongs to human understanding, in this deep ignorance and obscurity, is to be skeptical, or at least cautious; and not to admit of any hypothesis, whatsoever; much less, of any which is supported by no appearance of probability...Hume
    Reply With Quote  
     

  10. #9  
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    Quote Originally Posted by zinjanthropos View Post
    Quote Originally Posted by mathman View Post
    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.
    Reply With Quote  
     

  11. #10  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,717
    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.
    Last edited by KJW; December 28th, 2021 at 07:37 AM.
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  12. #11  
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    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...
    Reply With Quote  
     

  13. #12  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,717
    Quote Originally Posted by tsfgenady View Post
    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.
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  14. #13  
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    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.
    Reply With Quote  
     

  15. #14  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,717
    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.
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  16. #15  
    Forum Freshman tsfgenady's Avatar
    Join Date
    Dec 2021
    Posts
    25
    Very nice. This could be a second solution.
    Reply With Quote  
     

  17. #16  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,717
    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.
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

Similar Threads

  1. Imagining Apples.
    By Cogito Ergo Sum in forum General Discussion
    Replies: 17
    Last Post: December 31st, 2013, 11:02 AM
Bookmarks
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
  •