Project Euler Forum

Problem 335 (View Problem)
Well, actually I don't want to ask a question, I just cannot stop wondering how the beans gather with this algorithm (every possible number of them!). And it seems even starting with other number (e.g. 5 beans and 7 cups) does not change the situation! I would rather expect that there are some numbers of beans/cups that don't have that amazing trait...

I'm pretty sure i don't give any help for the problem here, edit that if I do.

The operation of gathering will necessarily end up in a cycle, because there is a finite number of positions (given the number of bowls and beans) and the next position depends only on the previous one.
If you consider the set A of the couples (x,y) where x is a state of the bowls and y is the position where you are, then the considered operation is a bijection of A : that is you can do the reverse operation by taking one bean from each bowl starting at the bowl you ended in until you are on an empty bowl, where you put the beans you gathered.
So if you consider now your cycle, taking the first state of the cycle and going on step backwards, you can only be at the last state of the cycle, meaning your cycle start at the first position you took. So for each starting position you will end up in the same one after a finite number of steps.

(hope my english was clear enough here..)

gprano wrote: If you consider the set A of the couples (x,y) where x is a state of the bowls and y is the position where you are, then the considered operation is a bijection of A : that is you can do the reverse operation by taking one bean from each bowl starting at the bowl you ended in until you are on an empty bowl, where you put the beans you gathered.

You now have shown injection of the operation. This is enough, but strictly speaking, by this argument only, there still could be two disjoint cycles. A nice proof nonetheless

Lord_Farin wrote:

gprano wrote: If you consider the set A of the couples (x,y) where x is a state of the bowls and y is the position where you are, then the considered operation is a bijection of A : that is you can do the reverse operation by taking one bean from each bowl starting at the bowl you ended in until you are on an empty bowl, where you put the beans you gathered.

You now have shown injection of the operation. This is enough, but strictly speaking, by this argument only, there still could be two disjoint cycles. A nice proof nonetheless

No, it really is a bijection. There can only be one previous (state,currentbowl) pair that leads to the current position.
And that is why the first position that is repeated is the starting position (otherwise that first repeated position would have two different predecessors). There still are several disjoint cycles, but only one that includes the starting position.

jaap wrote:No, it really is a bijection. There can only be one previous (state,currentbowl) pair that leads to the current position.
And that is why the first position that is repeated is the starting position (otherwise that first repeated position would have two different predecessors). There still are several disjoint cycles, but only one that includes the starting position.

My mistake, the way I stated it it's not a bijection, only an injection, which definition you precisely wrote here (but then we only use the injection aspect anyways, so it doesn't really matter if it's surjective).
To have a bijection we should restrict ourselves to the (state, currentbowl) where there is at least one bean in the current bowl, and then there is exactly one predecessor for each element.

Guys you're killing us here. I have the closed-form answer figured out. Only I don't know how to get it with the numbers being so huge. Why-oh-why must they be so big? Surely it's the concept that matters as long as the answer cannot be obtained by brute force? Now I need to learn congruence AND to find a way to deal with numbers above 2^53.

This is the second problem I absolutely have figured out but cannot get the number (the other one is 210). I could go to Wolfram or somewhere similar but I don't want to. You guys are rewarding my steadfastness in not treading cheating territory with larger and larger numbers. Very demoralising.

Oh well, part of the learning process I guess.

Waldovski wrote:This is the second problem I absolutely have figured out but cannot get the number (the other one is 210).

If you can't get the answer then you certainly haven't absolutely figured it out. The limits in any problem are specifically designed to be large enough for the correct algorithm to solve easily, and any incorrect or suboptimal solution to find very tough.

If you're finding the large limit tough, then you haven't solved the problem.