задачка (теория вероятностей)

[avva]

Вот такую задачку рассказали:

В мешке лежат n шаров, раскрашенных в n разных цветов. Вы повторяете следующую операцию: запускаете руки в мешок, достаете не глядя два шара, по одному в каждой руке, затем красите шар в правой руке в цвет шара в левой руке и кладете оба обратно. Найти математическое ожидание числа таких операций, после которого все шары будут одного цвета.

(я знаю ответ, но понятия не имею, как доказать)

Update: ссылку на доказательство дал в комментариях kdv2005, не идите по ней, если хотите решать самостоятельно.

Comments

woe betide, for I have forgotten all my probability theory.

[0qwerty0.livejournal.com]

using System;

namespace ballshuffle
{
class Program
{
public static void Main(string[] args)
{
int nsteps, niterations=100000, sumnsteps;
Ballset bs;
Random r = new Random(DateTime.Now.Millisecond);

for(int nballs = 1; nballs<20; nballs++) {
sumnsteps = 0;
for(int i=0;i<niterations;i++) { bs = new Ballset(nballs,r); for(nsteps = 0; !bs.arethesame(); nsteps++) { bs.draw(); } sumnsteps += nsteps; } Console.WriteLine(nballs + ": average number of draws (" + niterations +" interations): "+ (double)sumnsteps/niterations); } } } class Ballset { private int[] balls; private Random r; public Ballset(int n, Random r){ balls = new int[n]; this.r = r; for(int i=0; i<n; i++) balls[i] = i; } public void print(){ for(int i=0; i<balls.GetLength(0);i++) Console.Write(balls[i]+" "); Console.WriteLine(); } public void draw(){ int left = (int)(r.NextDouble()*balls.GetLength(0)); int right = left; while(right == left) { right = (int)(r.NextDouble()*balls.GetLength(0)); } balls[left] = balls[right]; } public bool arethesame() { for(int i=1; i<balls.GetLength(0);i++) if(balls[i]!=balls[0]) return false; return true; } } }