Wow, I've just noticed that there are 1 document in English which contains all problems and solutions from 1-4th olympiads. Again, http://mech.math.msu.su/probab/index-k.html , the second last link, then 5th link from the top.

<r>Here's the link to the problems and solutions of 1st-7th olympiads (2001, 2003-2008): <URL url="http://mech.math.msu.su/probab/index-k.html">http://mech.math.msu.su/probab/index-k.html</URL> , after that the second last link. The main problem is that it's all in Russian and it seems like there is...

<t>wileysw, E[N(a)]=1 is correct. This was the second problem from Kolmogorov's olympiad for 1st and 2nd year students in Moscow State University, so it should takes about 10-15 min for quite smart young man to solve it. Interesting thing is that my friend, who told me it (by the way, he is on 2nd y...

B - is a simple random walk starting at 0:( B(0)=0, B(i)=S(1)+...+S(i). All S(k) are independent and P(S(k)=1) = P(S(k)=-1) = 1/2 for every k )Let's denote by N(a) the number of times the process B was equal to a, before its first returning back to 0. What is the E[N(a)]?

You are right, i just misread cm27874's message and thought that for next element we should simulate all previous process without swapping.

<t>tqt, why did you use in 3rd and 4th cases 1501 instead of 1500? It seems that the dry-run method strongly depends on average cycle length. (without using cycles)-methods uses about O(n*n*m) swaps, and dry-run should use something like O(A*exp(C*(m*n)/A)) where A is average cycle length. For NxN m...

<t>Here is the algorithm, which doesn't use much memory. Suppose, you've got numbers 1...m*n. Mark every n number, and send marking numbers to the end of the queue. You should do it in the way that doesn't change the order of marked and unmarked elements, i.e on first step you'll get 1...n-1, n+1,.....