15510. Gra [AL_09_07]

Zadanie:
https://pl.spoj.com/problems/AL_09_07

Skrócony opis problemu:

Dana jest moneta, na której wypada orzeł z prawdopodobieństwem $\frac{2}{3}$, a reszka z $\frac{1}{3}$. Czy prawdopodobieństwo $P(A)$, że w $n$ rzutach wypadło $k$ reszek jest większe, mniejsze czy równe prawdopodobieństwu $P(B)$ przy dodatkowej wiedzy, że w pierwszym rzucie wypadła reszka?

Rozwiązanie:

Prawdopodobieństwo $k$ sukcesów w $n$ próbach możemy obliczyć z rozkładu dwumianowego, a więc ze wzoru:

$$\binom{n}{k} p^k (1-p)^{n-k}$$
Gdzie $n$ to ilość prób, $k$ to ilość sukcesów, a $p$ to prawdopodobieństwo sukcesu.

Skąd wziął się ów wzór?

Ano stąd, że mamy sobie ciąg zero-jedynkowy o długości $n$, gdzie 0 to porażka, a 1 to sukces. No i chcemy mieć $k$ 1-nek. $p^k$ to prawdopodobieństwo, że będziemy mieli przynajmniej $k$ 1-nek. No bo prawd. że będziemy mieli 1-nkę wynosi $p$, że 2. 1-nki to $p^2$, itd. Czemu "przynajmniej"? Bo na pozostałych $n-k$ pozycjach może być obojętnie co wg naszego prawdopodobieństwa $p^k$. Musimy zatem uwzględnić również, że chcemy $k$ 1-nek oraz $n-k$ zer. Koniunkcja w logice to iloczyn w algebrze, więc mamy $p^k \cdot (1-p)^{n-k}$. Dla pewności dodam, że skoro $p$ to prawdopodobieństwo sukcesu, to $1-p$ to prawd. porażki. No bo jeśli na 99% (0.99) ten artykuł nam pomoże rozwiązać to zadanie to na 100%-99%=1% (1-0.99=0.01) nam nie pomoże.

No a po co nam ten dwumian Newtona? A po to, bo póki co założyliśmy po cichu, że kolejność ma znaczenie. A więc ciąg 01 nam da 1 sukces w 2 próbach, ale zapominamy, że ciąg 10 też nam to zagwarantuje. Musimy zatem przemnożyć nasz wynik przez ilość ciągów zawierających $k$ 1-nek. Jest ich $\binom{n}{k}$, bo wybieramy spośród $n$ możliwych miejsc $k$ dowolnych miejsc.

Wracając do zadania, sukcesem u nas jest reszka, a porażką orzeł. Tak więc $p=\frac{1}{3}$. Interesuje nas zatem wynik takiej różnicy:

$$\binom{n}{k} p^k (1-p)^{n-k} - \binom{n-1}{k-1} p^{k-1} (1-p)^{n-k}$$

W drugim członie zamieniliśmy $n$ na $n-1$ a $k$ na $k-1$ (bo skoro mamy już jeden sukces to zostało nam tylko $k-1$, ale mamy też jedną próbę mniej). Czemu w ostatnim członie drugiego członu jest tak samo? Bo $n-1-(k-1)=n-1-k+1=n-k$. To tak dla jasności.

Teraz pozostaje nam tylko uprościć tę różnicę, gdyż obliczenie dwumianu Newtona zajmuje trochę czasu. Wyciągnijmy zatem przed nawias co możemy i zamieńmy dwumian Newtona na jego wzór z silniami.

$$p^{k-1} (1-p)^{n-k} \left(p \frac{n!}{(n-k)!k!} - \frac{(n-1)!}{(n-k)!(k-1)!}\right)$$

Teraz musimy sobie coś uświadomić. Czy na pewno zależy nam na wyniku? Nie. Zależy nam na wartości funkcji signum wyniku, a więc, mówiąc prościej, na znaku. Interesuje nas czy wynik powyższego działania jest dodatni, ujemny czy zerowy. No i tutaj możemy zauważyć, że zarówno $p^k$ jak i $(1-p)^{n-k}$ nie wpływają na znak działania, gdyż jest są to funkcje wykładnicze o podstawie dodatniej (prawdopodobieństwo jest dodatnie w naszym przypadku - inaczej mogłoby być też zerowe, ale u nas nie jest). Tak więc wywalamy oba człony sprzed nawiasu i zostaje nam:

$$p \frac{n!}{(n-k)!k!} - \frac{(n-1)!}{(n-k)!(k-1)!}$$

Ponownie wyrzućmy przed nawias co możemy:

$$\frac{(n-1)!}{(k-1)!(n-k)!} \left(p \frac{n}{k} - 1\right)$$

Znów możemy zrezygnować z członu przed nawiasem, gdyż silnia jest zawsze dodatnia. Tak więc $P(A)$ będzie większe od $P(B)$ jeśli wynik jest dodatni, a więc jeśli $p \frac{n}{k}-1>0 \Leftrightarrow n \cdot p > k$.

Musimy jeszcze dodatkowo wyifować przypadek, że $n < k$. Wtedy prawdopodobieństwo jest zawsze 0, więc $P(A)=P(B)$.

Złożoność: $O(1)$.

Ostateczny algorytm:

int main()
{
    int n, k;

    scanf("%d%d", &n, &k);
    puts(n < k || n == 3*k ? "NIE" : n > 3*k ? "TAK, ZMNIEJSZY SIE" : "TAK, ZWIEKSZY SIE"); // operator trójwarunkowy
}