German Federal Math Olympiad 2000 R2 P1

[andreben]

I love this way of presenting problem solving. It does show how you can find a solution yourself and I thus love the fact that you section your videos so that we can try and solve it, even if we didn't have the initial ideas.

I find it weird that I solved it the exact same way you did. It's such a nice and elegant problem. Simple, but elegant.

[Blabla]

The sum of the numbers is n(n+1)/2 which must be divisibe by 3 so n=6k or n=6k+5

[riadsouissi]

Lovely problem.
I took a different induction approach, though similar.
For n=1mod(3), it is obvious no solution is possible.

For n=2 mod(3), I assume I have three partitions of equal size if I include 0. Also n and n-1 are not located in the same partition and 0 is collocated with n (verifies for n=5).
Now I add 1 to every element in each partition. 0 becomes 1 and n becomes n+1. This new partitions have same size and wright and verify the required conditions for n+1=0 mod(3). Note zero is not included in these partitions and n, n+1 are still not located in same partition.

For n=0 mod(3), assume I also have three partitions of equal size. 0 is not included here and n-1, n are not in same partition. Now add 2 to every element in each partition. Lowest value 1 becomes 3 and highest value n becomes n+2. All partitions have same weight but we are missing 1 and 2 that cannot be split between three partitions. We need to add weight=1 to each partition. Now swap n+1 and n+2. So partition with n+2 has now the correct weight but we are going to add 0 to it. Add 2 to partition with n+1 which ends up with correct weight. Finally add element 1 to the last partition. Notice here n+1, n+2 are not located in same partition, 0 is located co-located with n+2 and all partitions have same size and wright. Condition for n+2=2 mod(3) is verified.

[nicolasteffenato]

Really nice easy problem!


I solved it in a different way, but I'm not sure it's 100% correct.
I first noticed that, since S=1+2+...+n=n(n+1)/2, n cannot be equal to 1 mod 3, because S must be divided in 3 groups.
Then I set S=3k and tried to construct two groups of numbers with sum k (the third one must have sum k by difference), but I'm afraid my reasoning could not be rigorous. I put in the first group some numbers starting from n and going in descendent order up to the point in which the sum of the groups would be greater than or equal to k. At this point I removed the last number and put instead the difference between k and the quantity I had, say d, for difference - notice that this can always be done because the difference lies between 0 and the number I just removed. Then I repeated this process for the second group, with the exception d could not be chosen and had to be replaced by d-1 and 1. At this stage, as I said earlier, the problem should be solved, since the third group necessarily has sum k.
If anyone could check this and tell me whether there are mistakes I would be really grateful!