Задачка

[spamsink]

Абстрагируясь от предметной области:

Даны N > 0, K > 0. Массив чисел размером 2N первоначально содержит нули. Далее, пока в массиве осталось не менее 2 элементов, меньших K, из них выбираются 2 случайных (или, если осталось ровно 2, то не очень случайных), и к обоим прибавляется 1.

Найти ожидаемое количество итераций цикла.

Бонус: восстановить формулировку в терминах исходной предметной области.

Comments

[ivan-ghandhi.livejournal.com]

Кроме обычной комбинаторики из Кнута я как-то не заметил ничего выдающегося.

[spamsink.livejournal.com]

В задаче как таковой, пожалуй, ничего выдающегося нет, но результат оказался для меня несколько неожиданным.

[raindog-2.livejournal.com]

Наверное, не понял условия. Получится же что каждое число дойдет до К и "остановится", поэтому число итераций всегда равно K*N. В чем подвох?

[spamsink.livejournal.com]

В любом случае, отличном от тривиального, это не так:
N = 2, K = 2
0 0 0 0
1 1 0 0
2 1 1 0
2 2 2 0
Приехали.

[stas]

может быть от К*N до [K*(2N-1)/2] в зависимости от значения "последнего могиканина".

[syarzhuk.livejournal.com]

восстановить формулировку в терминах исходной предметной области
А вот это как раз интересно

[spamsink.livejournal.com]

Хинт: носки.

[syarzhuk.livejournal.com]

Типа - на сколько дней хватит N пар носков, если каждый день брать два более-менее подходящих (разница в цвете не больше K по какой-то шкале)?

[spamsink.livejournal.com]

Почти. За сколько дней они износятся.