Question

Помогите пожалуйста срочно нужно .У вас есть n корзин. В каждой корзине лежит бесконечное количество шаров, помеченных номером корзины. На каждом шаге вы равновероятно выбираете корзину, вытаскиваете из неё один шар и откладываете его в кучу. Сколько в среднем вам потребуется шагов, чтобы в куче лежало хотя бы по одному шару из каждой корзины? Спасибо

Answer 1

4шага максимум а минимум 2 шага

Answer 2

Давайте рассмотрим данную задачу.

Пусть n - количество корзин, а T(n) - среднее количество шагов, которое понадобится, чтобы в куче окажется по одному шару из каждой корзины.

На первом шаге, вероятность выбрать корзину с номером i равна 1/n, и вероятность не выбрать корзину с номером i равна (n-1)/n. После первого шага у нас будет один шар в куче, и проблема сводится к такой же, но с n-1 корзинами, так как корзина с номером i уже удовлетворена.

Теперь мы можем сформулировать рекуррентное соотношение для T(n):

T(n) = 1 + (n-1)/n * T(n-1)

где:

• 1 - это первый шаг, который всегда нужен, чтобы взять первый шар и положить в кучу.
• (n-1)/n - вероятность того, что мы не выберем корзину с номером i на первом шаге.
• T(n-1) - количество шагов, которое потребуется для n-1 корзин после первого шага.

Теперь мы можем решить рекуррентное соотношение.

Для n=1, очевидно, что T(1) = 1.

Для n=2: T(2) = 1 + (2-1)/2 * T(1) = 1 + 1/2 * 1 = 1.5

Для n=3: T(3) = 1 + (3-1)/3 * T(2) = 1 + 2/3 * 1.5 = 2

Для n=4: T(4) = 1 + (4-1)/4 * T(3) = 1 + 3/4 * 2 = 2.5

Мы можем заметить, что T(n) = n/2 для всех целых n >= 1. Поэтому ответ на ваш вопрос: в среднем потребуется n/2 шагов, чтобы в куче лежало хотя бы по одному шару из каждой корзины.