[Kombinatoryka][Teoria liczb] IMO Longlist, Rachunek prawdopodobieństwa

[laurelandilas]

Liczby \(\displaystyle{ x_{1}, x_{2} ... x_{n}}\)są wybierane losowo ze zbioru \(\displaystyle{ {1,2,3,4,5}}\). Udowodnij, ze prawdopodobienstwo, ze \(\displaystyle{ x_{1}^{2} + x_{2}^{2} + ... x_{n}^{2} \equiv 0 \pmod{5}}\) wynosi conajmniej \(\displaystyle{ \frac{1}{5}}\)

Z gory dzieki za pomoc

[AVquiraniel]

Ogólny szkic rozwiązania:

Ukryta treść:    

Niech \(\displaystyle{ L _{n}(k)}\) oznacza prawdopodobieństwo, że \(\displaystyle{ x_{1}^{2}+x_{2}^{2}+...+x_{n}^{2}\equiv k \pmod{5}}\). Zauważmy, że (*) \(\displaystyle{ L_{n+1}(i)= \frac{1}{5} L_{n}(i) + \frac{2}{5} L_{n}(i-1) + \frac{2}{5} L_{n}(i-4)}\) (aby się o tym przekonać wystarczy rozpisać reszty kwadratowe \(\displaystyle{ \pmod{5}}\) )
Teraz pozostaje nam tylko zauważyć/domyślić się, że dla \(\displaystyle{ n}\) nieparzystych mamy:\(\displaystyle{ L_{n}(0)=\frac{1}{5}; L_{n}(1) = L_{n}(4) >\frac{1}{5}; L_{n}(2)=L_{n}(3)<\frac{1}{5}}\), a dla nieparzystych: \(\displaystyle{ L_{n}(0)>\frac{1}{5}; L_{n}(1) = L_{n}(2) = L_{n}(3) = L_{n}(4) < \frac{1}{5}}\) - i, korzystając z (*) udowadniamy indukcyjnie.