Results 1 to 4 of 4

Math Help - Difficult brain teaser - mix of algebra, number theory and maybe s.o.

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    austria
    Posts
    4

    Difficult brain teaser - mix of algebra, number theory and maybe s.o.

    Hi there,

    I put up an very interesting question from a mathematical magazine, but I was not able to solve it:
    There are n bottles arranged in a circle. You can start at any bottle and lay one litte stone inside this first bottle.
    Then you will go to the next bottle and lay a little stone in it, too.
    After that you have to go two bottles farther and lay a stone inside this one, then three, four...
    All in all, you lay stones in the 1st, 2nd, 4th, 7th,...bottle (and if you are one way round
    the 7th bottle may be the same as the 1st, so that there are two stones inside then).
    You continue doing that until there is at least one stone in every bottle.

    After some tries and discussing the problem with someone else we got so far:

    I will say that the bottle in which the nth stone goes in is given by ((n(n - 1)/2) + 1) mod k, where k is the number of bottles.

    Proof by induction : for n = 1, (1(1 - 1)/2) + 1 = 1; n = 2, (2(2 - 1)/2) + 1 = 2. Since the sequence is defined as the nth stone being placed in the bottle n - 1 bottles away from the last bottle in which a stone was placed, with the first bottle containing the first stone, it suffices to show that (n(n - 1)/2) + 1 + n = (n(n + 1)/2) + 1 as follows: (n(n - 1)/2) + 1 + n = (nē - n + 2 + 2n)/2 = (nē + n + 2)/2 = (n(n + 1)/2) + 1. So we can say that the nth stone goes in the bottle given by ((n(n - 1)/2) + 1) mod k, where k is the number of bottles. If this equals zero, the stone goes in the last bottle; if it equals one it goes in the first bottle, two the second and so on.

    If k is odd, then the positions of the bottles containing the stones will be periodic mod k, because the differences between the first k positions will be the numbers from 1 to k - 1. The sum of these differences is , which is divisible by k unless k is even. Thus, the kth position will be the same as the 1st position, which is 1. Finally, the k+1th position will also be 1, since the difference between the kth position and the k+1th position is k, which is 0 mod k. Now, since the differences are periodic mod k, with a period of k, and the k+1th position is the same as the 1st, the cycle must repeat at a length of k (the actual period could be less than k, though it must be a factor of k). However, since two of the positions in one cycle of length k are the same (namely, the first and the last), at least one of the residues mod k is not covered.

    I have no idea what to do in the case that k is even, however.

    That's about as far as I've gotten with it.

    I will guess that if k = 2^n, where n is a natural number, then it takes y stones to fill the bottles (with exactly one stone in each bottle). Further guess: the last stone goes in the y/2 + 1 bottle, if y = 2^n. One more guess: Any sequence with k ≠ 2^n will never fill all the bottles with at least one stone.

    I am very interested in a solution and hope that you can help me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Difficult brain teaser - mix of algebra, number theory and maybe s.o.

    You want to find the minimal m such that, given the sequence

    A_n = \frac{n(n-1)}{2} + 1,

    A_1, A_2, \dots A_m covers all residues mod k (where k is the number of bottles). This is equivalent to saying that \frac{n(n-1)}{2} covers all residues mod k (via shifting by 1).

    But...we have a problem. If k = 3, \frac{n(n-1)}{2} is always congruent to 0 or 1 mod 3. Thoughts?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2012
    From
    austria
    Posts
    4

    Re: Difficult brain teaser - mix of algebra, number theory and maybe s.o.

    I can follow that the shifting by 1 is possible for  k>1 because in this problem the kth bottle equals the 0th bottle and the term is easier then. I already have the proof that if k is odd, it is not possible to cover all bottles because the differences are periodic as in your example with k=3. Unfortunately, I can not see what you are trying to suggest me for the proof that it is not possible for  k \neq 2^n or why it is possible for all  k = 2^n ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2012
    From
    austria
    Posts
    4

    Re: Difficult brain teaser - mix of algebra, number theory and maybe s.o.

    Quote Originally Posted by annegret View Post
    The sum of these differences is , which is divisible by k unless k is even.
    Oh, I see that there went something wrong, the sentence means: The sum of these differences is  \frac{k(k-1)}{2}, which is divisible by k unless k is even.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help - Brain Teaser
    Posted in the Math Puzzles Forum
    Replies: 9
    Last Post: August 20th 2010, 03:10 AM
  2. Replies: 2
    Last Post: February 11th 2010, 07:27 PM
  3. Brain Teaser Help Please~!
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 12th 2008, 09:50 AM
  4. Brain Teaser
    Posted in the Algebra Forum
    Replies: 5
    Last Post: May 7th 2007, 11:01 AM
  5. brain teaser
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 1st 2005, 11:08 AM

Search Tags


/mathhelpforum @mathhelpforum