Thread: 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.

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

,

covers all residues mod k (where k is the number of bottles). This is equivalent to saying that covers all residues mod k (via shifting by 1).

But...we have a problem. If k = 3, is always congruent to 0 or 1 mod 3. Thoughts?

I can follow that the shifting by 1 is possible for 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 or why it is possible for all ?

Originally Posted by annegret

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 , which is divisible by k unless k is even.