Question

Петя,Вася и Толя на уроке физкультуры по очереди бросают друг другу волейбольный мяч.Первым бросает Петя.Найдите число способов,которыми может вернутся обратно Пете через 37 бросков(необязательно первые)​

Answer 1

Ответ:

Через 37 бросков Петя может получить мяч от двоих своих друзей 45 812 984 490 способами.

Объяснение:

Найти число способов, которыми мяч может вернутся к Пете от Васи или Толи через 37 бросков (необязательно первых), при этом первым мяч бросает Петя.

1) Число способов перекинуть мяч к Пете от Васи или Толи обозначим B₃₇.

Для удобства будем обозначать ребят буквами П, В, Т.

При каждом броске мяч перебрасывается между двумя мальчиками, то есть броски совершаются попарно.

Например, могут быть броски:

П → В, П → Т, В → П, В → Т, Т → П, Т → В.

Через 37 бросков мяч должен оказаться у Пети. Но Петя не может сам себе бросить мяч.

Петя на тридцать седьмом броске получит мяч, если на тридцать шестом броске его получил Вася или Толя.

2) Тогда всего способов перебросить мяч  между двумя друзьями должно быть 2³⁶.

Из общего количество способов нужно отнять способы, при которых мяч получает Петя.

Тогда общее число способов перекинуть мяч в паре мальчиков:

B₃₇ = 2³⁶ - B₃₆ .

Для 35 бросков получим количество способов перебрасывания мяча:

B₃₆ = 2³⁵ - B₃₅

и т.д.

В общем виде мы получили зависимость:

Bₙ₊₁ = 2ⁿ - Bₙ.

3) Запишем полученное выражение в развернутом виде:

B₃₇ = 2³⁶ - B₃₆  = 2³⁶ - (2³⁵ - B₃₅) = 2³⁶ - 2³⁵ + B₃₅ =

= 2³⁶ - 2³⁵ + 2³⁴ - 2³³ + 2³² - ...+2² - 2.

4) Мы получили сумму, в которой содержатся слагаемые в четных степенях со знаком (+), а в нечетных степенях - со знаком (-).

Последний бросок можно сделать двумя способами: В → П, или Т → П.

Причем последнее слагаемое равно (-2), так как его степень нечетна.

Таким образом, количество способов перебросить мяч Пете представляет собой сумму n членов геометрической прогрессии, в которой:

первый член равен b₁ = -2;

знаменатель прогрессии равен q = -2,

n = 36.

• Сумма n первых членов геометрической прогрессии вычисляется по формуле
  $\displaystyle S = \frac {b_{1}(q^{n}-1)}{q - 1}$

Тогда:

$\displaystyle B_{37} = \frac {-2((-2)^{36}-1)}{-2- 1} = \frac{(-2)^{37}+2}{-3} =\\\\\\=\frac{2^{37}-2}{3} =\frac{137\;438\;953\;472-2}{3} =45\;812\;984\;490.$

Answer 2

Чтобы найти число способов, которыми мяч может вернуться обратно Пете через 37 бросков, мы можем использовать метод динамического программирования.

Пусть dp[i] - число способов, которыми мяч может вернуться обратно Пете через i бросков.

Изначально у нас есть только один бросок, который сделал Петя, поэтому dp[1] = 1.

Затем мы можем рассмотреть все возможные сценарии для остальных бросков:

- Если предыдущим броском был Вася, то на текущем броске мяч может вернуться обратно Пете только одним способом. То есть, dp[i] += dp[i-1]. - Если предыдущим броском был Толя, то на текущем броске мяч может вернуться обратно Пете двумя способами (Петя может бросить мяч прямо Васе или через Васю). То есть, dp[i] += dp[i-1] + dp[i-2].

Таким образом, мы можем вычислить все значения dp[i] для i от 2 до 37, используя значения предыдущих элементов.

В итоге, число способов, которыми мяч может вернуться обратно Пете через 37 бросков, будет равно dp[37].