Poland math Olympiads

I use Google Analytics to gather stats for Math Pages. Besides other information it provides, it also shows from which countries my visitors come. I was somewhat surprised today to see that Poland is on the fifth place on the list. India is on the six, but I know people who live there, so it is not surprising. Visits from Poland are a surprise however.

Because of this positive surprise, this post is about math Olympiads in Poland. I am not going to talk much about them, just to solve some of the problems I found on their (official?) site. I never participated in a math Olympiad (and likely will never participate in one in the future), so writing this post is an attempt to fix this partially.

First problem:

Let n ≥ 3 be a positive integer. Prove that the sum of the cubes of all natural numbers, coprime and less than n, is divisible by n.

Firstly lets test this for n=3, and for n=4:

1^3+2^3=9, 9/3=3

1^3+2^3+3^3=36 36/4=9

So far the theorem works. Unfortunately, it is not correct. It fails on n=10:

1^3+2^3+3^3+5^3+7^3=504 504/10=50.4

It is easy to see that the numbers 1,2,3,5,7 are coprimes - the only common divisor for any two of them is 1. The numbers not included 4,6,8,9 are not coprimes with the rest because:
4=2*2 not coprime with 2, 6=2*3 not coprime with 2, 8=2*4 not coprime with 2, 9=3*3 not coprime with 3.

Second problem:

Prove that the number:
is divisible by

Speaking about usefulness of large numbers.. It is not difficult to solve this one, but it requires writing a lot in Latex - so I am leaving this one for the reader. Clue - you need to prove a general statement and then the problem is solved as a special case.

Third Problem:

In a group of n ≥ 3 peoples each member of the group has an even number (perhaps zero) of acquaintances in the group. Prove that there exist three members of the group which have the same number of acquaintances in this group.
Remark: Assume that nobody includes himself into the set of his acquaintances and that A knows B if and only if B knows A.

This one is actually very easy. Lets see what is going on for n=3: Because the number of acquaintances must be even and less then 3, it can be only zero or two. Lets call each of the three members A(x).B(x),C(x), where x is the number of the member acquaintances. Firstly, if A(0) than it must follow that neither B or C know A. Therefore, because x can have only even values we get B(0), C(0). In the same way it is possible to show that if A(2) then B(2) and C(2).

Now lets prove the general case by induction. Lets suppose that we proved for n=k, k≥3. Thus in this group we have three members with equal number of acquaintances. If we will add one more member to the group there are two options - either he knows one of these three members or not. If he doesn't know anyone of them than there are still those three members with the same number of acquaintances that were before we added him. Now lets suppose that he knows one of these three members, lets call this member A. But then the acquaintances number of A will grow by exactly one and become odd. This is not allowed. Q.E.D.