Matematyka.pl

\(\displaystyle{ a_{n+1} = \frac{na_n+ 2(n+1)^2}{n+2}\\ a_1=1}\)
Udowadniamy przez indukcję silną, że \(\displaystyle{ a_m= \frac{m(m+1)}{2} , \ m=1,2,3,4\ldots}\).
\(\displaystyle{ 1^{\circ}}\) Warunek początkowy daje nam \(\displaystyle{ a_1=1=\frac{1\cdot 2}{2}}\), OK.
\(\displaystyle{ 2^{\circ}}\)
Rozpisując \(\displaystyle{ (k+1)a_{k+1}-ka_k=-a_{k+1}+2(k+1)^2}\),
dodając stronami takie równości dla \(\displaystyle{ k=1,2, \ldots n}\) i wykorzystując tożsamość
\(\displaystyle{ \sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}}\)
otrzymujemy
\(\displaystyle{ a_{n+1}=-\frac{1}{n+2} \sum_{k=1}^{n}a_k+ \frac{(n+1)(2n+3)}{3}}\)
Korzystając teraz w tej sumie
\(\displaystyle{ \sum_{k=1}^{n}a_k}\)
z założenia indukcyjnego dostajemy
\(\displaystyle{ a_{n+1}=-\frac{1}{n+2} \sum_{k=1}^{n} \frac{k(k+1)}{2}+ \frac{(n+1)(2n+3)}{3}=\\=-\frac{1}{n+2}\cdot \frac{n(n+1)(2n+1)}{12}-\frac{1}{n+2}\cdot \frac{n(n+1)}{4} + \frac{(n+1)(2n+3)}{3}=\frac{(n+1)(n+2)}{2}}\)
gdyż
\(\displaystyle{ 4(n+2)(2n+3)-3n-n(2n+1)=6(n+2)^2}\)

Stąd mamy \(\displaystyle{ a_n=\frac{n(n+1)}{2}}\) dla każdego \(\displaystyle{ n\in \NN^+}\)
i jeśli \(\displaystyle{ n\equiv 3\pmod{4} \vee n\equiv 0\pmod{4}}\), to liczba \(\displaystyle{ a_n}\) jest parzysta, a w przeciwnym razie jest nieparzysta.

Zakładam, że \(\displaystyle{ B}\) wie, czy \(\displaystyle{ C}\) skłamał czy nie oraz \(\displaystyle{ A}\) wie, czy \(\displaystyle{ B}\) skłamał (bądź nie), a więc \(\displaystyle{ A}\) w szczególności wie, co powiedział \(\displaystyle{ C}\).

Jeżeli \(\displaystyle{ B}\) mówi prawdę, to \(\displaystyle{ C}\) kłamie. Jeśli natomiast \(\displaystyle{ B}\) kłamie, to \(\displaystyle{ C}\) musi mówić prawdę. To oznacza, że \(\displaystyle{ B}\) oraz \(\displaystyle{ C}\) nie mogą jednocześnie mówić prawdy bądź też jednocześnie kłamać.

Prawdopodobieństwo zdarzenia, że dokładnie jedna spośród osób \(\displaystyle{ B}\) oraz \(\displaystyle{ C}\) mówi prawdę, wynosi \(\displaystyle{ \tfrac{4}{9}}\): są dokładnie dwa zdarzenia spośród czterech (nie uwzględniając \(\displaystyle{ A}\)) o prawdopodobieństwie \(\displaystyle{ \tfrac{2}{3}\cdot\tfrac{1}{3}}\) odpowiadające powyższej sytuacji.

Rozważamy zatem sytuację, w której \(\displaystyle{ C}\) kłamie, pod warunkiem, że dokładnie jedna z osób \(\displaystyle{ B}\) i \(\displaystyle{ C}\) mówi prawdę. Wśród czterech spósród ośmiu (wszystich możliwych) zdarzeń, pozostają poniższe warianty:

\(\displaystyle{ \begin{array}{ccc}A & B & C\\\hline 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array}}\)

gdzie wartości logiczne odpowiadają temu, czy podana osoba mówiła prawdę.

Jak łatwo przeliczyć, prawdopodobieństwo, że \(\displaystyle{ C}\) skłamie oraz \(\displaystyle{ B}\) mówi prawdę wynosi zaledwie \(\displaystyle{ \tfrac{1}{3}\tfrac{1}{3}\tfrac{2}{3}+\tfrac{2}{3}\tfrac{1}{3}\tfrac{2}{3}=\tfrac{2}{9}}\).

Stąd szukane prawdopodobieństwo warunkowe wynosi \(\displaystyle{ \frac{\tfrac{2}{9}}{\tfrac{4}{9}}=\tfrac{1}{2}}\).

Wszystko wskazuje na to, że jedynym rozwiązaniem jest \(\displaystyle{ x+\tfrac{1}{x}}\).

Rozwiązując równanie

\(\displaystyle{ x=\frac{1}{1-x}}\), którego rozwiązaniami są nietrywialne pierwiastki z minus jedynki trzeciego stopnia, możemy spróbować zdefiniować funkcję następującym wzorem:

\(\displaystyle{ h(x)=\frac{1}{1-x}}\)

i zauważyć, że \(\displaystyle{ h(h(h(x)))=x}\), tj. \(\displaystyle{ h(x)}\) jest funkcyjnym pierwiastkiem trzeciego stopnia identyczności*. Rozważmy zatem wyrażenie

\(\displaystyle{ f(x)+ f\left(\frac{1}{1-x}\right) = 1 + \frac{1}{x(1-x)}}\) dla \(\displaystyle{ x\mapsto h(x)}\), uzyskując

\(\displaystyle{ f\left(\frac{1}{1-x}\right)+f\left(\frac{x-1}{x}\right)=3-x-\frac{1}{x}}\);

z kolei korzystając ponownie z podstawienia \(\displaystyle{ x\mapsto h(x)}\), otrzymujemy

\(\displaystyle{ f\left(\frac{x-1}{x}\right)+f(x)=\frac{x^2+x-1}{x-1}}\),

co pozwala wyznaczyć \(\displaystyle{ f(x)}\), łącząc podane trzy równania:

\(\displaystyle{ 2f(x)=-2+\frac{1}{x}+\frac{1}{(1-x)x}+x+\frac{x^2+x-1}{x-1}=2\left(x+\frac{1}{x}\right)}\).

* - Wyrażenia postaci \(\displaystyle{ \tfrac{ax+b}{cx+d}}\) odpowiadają macierzom postaci \(\displaystyle{ \begin{bmatrix}a & b \\ c & d\end{bmatrix}}\), a złożenia takich przekształceń - iloczynom macierzy. W naszym przypadku macierz

\(\displaystyle{ A = \begin{bmatrix}0 & 1 \\ -1 & 1\end{bmatrix}}\)

odpowiada funkcji \(\displaystyle{ \frac{1}{1-x}}\), gdzie \(\displaystyle{ A^3=-I}\).

\(\displaystyle{ 3y^2 = x^4+x\\ 3y^2=x(x^3+1)}\)
Tutaj odnotujmy, że liczby \(\displaystyle{ x}\) oraz \(\displaystyle{ x^3+1}\) są zawsze względnie pierwsze.
Rozważymy dwa przypadki, wynikające z rozważenia reszt obu stron z dzielenia przez \(\displaystyle{ 3}\):
1) jeśli \(\displaystyle{ x\equiv 0\pmod{3}}\), to kładziemy \(\displaystyle{ x=3z, \ z\in \NN^+}\) i mamy
\(\displaystyle{ y^2=z(27z^3+1)}\)
Oczywiście także \(\displaystyle{ z}\) i \(\displaystyle{ 27z^3+1}\) są względnie pierwsze, zatem obie te liczby muszą być kwadratami. Niech więc \(\displaystyle{ z=b^2, \ b\in \NN^+}\). Jest więc:
\(\displaystyle{ \left( \frac y b\right)^2=(3b^2)^3+1}\)
Jednak rozwiązanie takiego równania byłoby w szczególności rozwiązaniem równania w naturalnych dodatnich:
\(\displaystyle{ c^2=d^3+1}\),
a na mocy

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Twierdzenie_Mih%C4%83ilescu

to prowadzi do \(\displaystyle{ c=3, \ d=2}\), czyli w szczególności
\(\displaystyle{ 3b^2=2}\), sprzeczność.

2) jeśli \(\displaystyle{ x\equiv 2\pmod{3}}\), to kładziemy \(\displaystyle{ x=3z-1, \ z\in \NN^+}\) i mamy
\(\displaystyle{ 3y^2=(3z-1)(27z^3-27z^2+9z)\\ y^2=(3z-1)(9z^3-9z^2+3z)}\)
i z analizy podzielności przez \(\displaystyle{ 3}\) i \(\displaystyle{ 9}\) wywnioskujemy, że
\(\displaystyle{ y=3s, s\in \NN^+, \ z=3t, \ t\in \NN^+}\)
a po podstawieniu tego:
\(\displaystyle{ s^2=(9t-1)(27t^3-9t^2+t)\\ s^2=t(9t-1)(27t^2-9t+1)}\)
Oczywiście liczba \(\displaystyle{ t}\) jest względnie pierwsza z \(\displaystyle{ (9t-1)(27t^2-9t+1)}\),
więc łatwo wywnioskować, że musi ona być kwadratem, niech więc \(\displaystyle{ t=u^2, \ u\in \NN^+}\).Otrzymujemy wówczas:
\(\displaystyle{ \left( \frac s u\right)^2=(9u^2-1)(27u^4-9u^2+1)}\),
ale to jest sprzeczność, ponieważ reszty kwadratowe modulo \(\displaystyle{ 9}\) to \(\displaystyle{ 0,1,4,7}\), a tymczasem dla dowolnego \(\displaystyle{ u\in \NN^+}\) jest
\(\displaystyle{ (9u^2-1)(27u^4-9u^2+1)\equiv 8\pmod{9}}\).

To kończy dowód.

i) ci, którzy pływali na torach nieparzystych, nie kończyli zawodów na nieparzystych miejscach
ii) ci zaś, którzy kończyli na parzystych miejscach nie pływali na parzystych torach
Wobec powyższych danych o ilu wynikach można tu mówić ?

Aby zachodził warunek i) to przynajmniej jeden z zawodników z nieparzystego toru nie ukończył zawodów lub zajmowno parzyste miejsca ex aequo. Warunek ii) sugeruje że przynajmniej dwaj z trzech zawodników z torów nieparzystych ukończyło wyścig.

Opcje:

a) zajęto miejsca 1,2,3,4 a jeden z zawodników nie ukończył zawodów lub został zdyskwalifikowany.
Ilość możliwości (zajmowania powyższych lokat): \(\displaystyle{ 2 \cdot 3 \cdot 1 \cdot 2}\)

b) zajęto miejsca 1,2,2,4 a jeden z zawodników (z toru parzystego lub nieparzystego) nie ukończył zawodów lub został zdyskwalifikowany.
Ilość możliwości : \(\displaystyle{ 2 \cdot {3 \choose 2} \cdot 1 +2 \cdot {3 \choose 2} \cdot 1}\)

c) zajęto miejsca 1,2,2,4,5
Ilość możliwości : \(\displaystyle{ 2 \cdot {3 \choose 2} \cdot 1 \cdot 1}\)

d) zajęto miejsca 1,2,3,4,4
Ilość możliwości : \(\displaystyle{ 2 \cdot 3 \cdot 1 \cdot {2 \choose 2}}\)

e) zajęto miejsca 1,2,2,2,5
Ilość możliwości : \(\displaystyle{ 2 \cdot {3 \choose 3} \cdot 1}\)

f) zajęto miejsca 1,2,2,2 a jeden z zawodników z toru parzystego nie ukończył zawodów lub został zdyskwalifikowany.
Ilość możliwości : \(\displaystyle{ 2 \cdot {3 \choose 3}}\)

f) zajęto miejsca 1,2,2 a jeden z zawodników z toru parzystego i jeden z nieparzystego nie ukończył zawodów lub został zdyskwalifikowany.
Ilość możliwości : \(\displaystyle{ 2 \cdot {2 \choose 2}}\)

Wygodnym podejściem jest rozbicie zagadki na mniejsze grupy, według ilości cyfr w liczbie a tych na zbiory liczbowe. Na dzień dobry można odrzucić liczby składające z 1- i 5-cyfr jako niespełniające warunków rozwiązania. Widzę właściwie dwa podejścia: rozwiązanie siłowe sprawdzające kolejne zbiory, w sumie ok. kilka milionów kombinacji do sprawdzenia lub skorzystanie z zasady włączeń i wyłączeń. Dla liczb 2- i 3-cyfrowych mamy 100 zbiorów do rozpatrzenia a dla liczb 4-cyfrowych mamy prawie 700 zbiorów. Jeśli rozpoczniemy analizę od zbiorów z najmniejszą ilością liczb w zbiorze to w grupie liczb 2-cyfrowych nie ma rozwiązań, a w grupie liczb 3-cyfrowych pierwszym rozwiązaniem jakie znajdziemy jest podzbiór liczb {168, 249, 328, 480, 624} i pozostają jeszcze do sprawdzenia zbiory dla liczb od 16 do 42.

\(\displaystyle{ U(x+1)W(x)-U(x)W(x+1) \equiv 1}\)
Na początku załóżmy, że \(\displaystyle{ U, W}\) są wielomianami stopnia co najmniej \(\displaystyle{ 2}\). Czyli \(\displaystyle{ U(x) = \sum_{i=0}^{n} a_ix^i}\), gdzie \(\displaystyle{ a_n \neq 0 \wedge n \ge 2}\) oraz \(\displaystyle{ W(x) = \sum_{i=0}^{m} b_ix^i}\), gdzie \(\displaystyle{ b_m \neq 0 \wedge m \ge 2}\). Wymnażając lewą stronę widzimy, że współczynnik przy \(\displaystyle{ x^{n+m}}\) się zeruje a przy \(\displaystyle{ x^{n+m-1}}\)
wynosi \(\displaystyle{ a_nb_m(n-m)}\). Naturalnie \(\displaystyle{ n+m-1 > 0}\) stąd \(\displaystyle{ n = m}\). Liczymy dalej i wychodzi, że współczynnik przy \(\displaystyle{ x^{2n-2}}\) wynosi \(\displaystyle{ a_nb_{n-1}-a_{n-1}b_n}\). Stąd \(\displaystyle{ a_nb_{n-1} = a_{n-1}b_n}\). Pokażemy indukcyjnie, że \(\displaystyle{ a_nb_{n-i} = a_{n-i}b_n \ , \ i \in [1; n]}\). Dla \(\displaystyle{ i=1}\) już udowodniliśmy. Załóżmy, że teza działa dla wszystkich \(\displaystyle{ i \in [1; k-2] \ , \ k \ge 3}\). Pokażemy, że działa wówczas dla \(\displaystyle{ i = k-1}\). Na początku zauważmy, że z założenia indukcyjnego wynika, że dla dowolnych \(\displaystyle{ p, q \in [n-k+2; n]}\) zachodzi \(\displaystyle{ a_pb_q = a_qb_p}\). Istotnie, mamy dwie równości: \(\displaystyle{ \begin{cases} a_nb_p = a_pb_n \\ a_qb_n = a_nb_q\end{cases}}\). Mnożąc je stronami i dzieląc przez \(\displaystyle{ a_nb_n}\) dostajemy żądaną równość.
Rozważmy współczynnik przy \(\displaystyle{ x^{2n-k}}\). Żeby za wiele nie liczyć popatrzmy na interesujące nas rzeczy w \(\displaystyle{ U(x+1)W(x)}\), tj:
\(\displaystyle{ (x^na_n+x^{n-1}(a_{n-1}+{n \choose 1}a_n)+x^{n-2}(a_{n-2}+{n-1 \choose 1}a_{n-1}+{n \choose 2}a_n)+...+x^{n-k}(a_{n-k}+{n-k+1 \choose 1}a_{n-k+1} + ... + {n \choose k} a_n)( b_{n-k}x^{n-k}+b_{n-k+1}x^{n-k+1}+...+b_nx^n)}\)
Zauważmy, że nie interesują nas składniki zawierające \(\displaystyle{ a_pb_q}\) gdzie \(\displaystyle{ p,q \in [n-k+2; n]}\), gdyż z symetrii odejmując \(\displaystyle{ U(x)W(x+1)}\) odejmiemy tą samą wielokrotność \(\displaystyle{ a_qb_p}\), co jak zauważyliśmy wyzeruje nam się, bo \(\displaystyle{ a_pb_q = a_qb_p}\). Łatwo też widać, że przy naszym współczynniku \(\displaystyle{ x^{2n-k}}\)
wystąpi symetryczne \(\displaystyle{ a_nb_{n-k}+a_{n-k}b_n}\) więc to też nam się zredukuje. Zostaje popatrzeć na to co zostanie z \(\displaystyle{ a_{n-k+1}}\) oraz \(\displaystyle{ b_{n-k+1}}\). Tu dostajemy symetryczne \(\displaystyle{ a_{n-k+1}b_{n-1}+a_{n-1}b_{n-k+1}}\) oraz niesymetryczne \(\displaystyle{ (n-k+1)a_{n-k+1}b_n+na_nb_{n-k+1}}\), stąd po wszystkich redukcjach przy \(\displaystyle{ x^{2n-k}}\) zostaje \(\displaystyle{ (k-1)(a_nb_{n-k+1}-a_{n-k+1}b_n)}\), skąd istotnie \(\displaystyle{ a_nb_{n-k+1} = a_{n-k+1}b_n}\).
Zauważmy jednak, że wyraz wolny wielomianu po lewej stronie wynosi \(\displaystyle{ b_0(a_0+a_1+...+a_n)-a_0(b_0+b_1+...+b_n)
= 0}\) co wynika bezpośrednio z udowodnionego wyżej faktu, stąd sprzeczność.
To oznacza, że co najmniej jeden wielomian jest stopnia nie większego niż 1. Niech \(\displaystyle{ U(x) = a_0+a_1x+...+a_nx^n \
, a_n \neq 0 \ , n \ge 1}\) (przypadek gdy jeden z wielomianów jest stały wyjdzie za chwilę) oraz \(\displaystyle{ W(x) = bx+c}\). Wówczas współczynnik przy \(\displaystyle{ x^n}\) wynosi \(\displaystyle{ a_nb(n-1)}\).
Stąd pierwsza możliwość to \(\displaystyle{ n = 1}\), czyli oba \(\displaystyle{ U, W}\) są stopnia co najwyżej \(\displaystyle{ 1}\). Wstawiając ogólną postać \(\displaystyle{ U(x) = ax+b' \ , \ W(x) = cx+d}\) do naszego równania dostajemy po redukcji, że jest ono równoważne \(\displaystyle{ ad-b'c = 1}\).
Druga możliwość to \(\displaystyle{ b=0}\), czyli \(\displaystyle{ W(x) = p \ , \ p \neq 0}\) (dla \(\displaystyle{ p=0}\) nie ma rozwiązań) i wówczas łatwo dostać, że \(\displaystyle{ U(x)}\) musi być stopnia co najwyżej \(\displaystyle{ 1}\) (współczynnik przy \(\displaystyle{ x^n}\) jest niezerowy) stąd jest to szczególny przypadek tego co już rozpatrzyliśmy.
Przypadek gdy \(\displaystyle{ U(x)}\) jest liniowy jest analogiczny i nie daje nowych rozwiązań.
Ostatecznie wielomianami spełniającymi zadaną równość są \(\displaystyle{ U(x) = ax+b \ , \ W(x) = cx+d}\) gdzie a,b,c,d są dowolnymi liczbami rzeczywistymi spełniającymi \(\displaystyle{ ad-bc = 1}\)