[MIX] Mix matematyczny (35)

[mol_ksiazkowy]

1. Dany jest ciąg określony rekurencyjnie \(\displaystyle{ a_{n+1} = \frac{na_n+ 2(n+1)^2}{n+2}}\) i \(\displaystyle{ a_1=1}\). Udowodnić, że wszystkie wyrazy tego ciągu są liczbami naturalnymi. Które z nich są parzyste ?
2. Wyznaczyć wszystkie wielomiany \(\displaystyle{ U}\) i \(\displaystyle{ W}\) takie, że \(\displaystyle{ U(x+1)W(x) - U(x)W(x+1) \equiv 1}\)
3. \(\displaystyle{ A}\) powiedział, że \(\displaystyle{ B}\) mu powiedział, iż \(\displaystyle{ C}\) skłamał. Jakie jest prawdopodobieństwo tego że \(\displaystyle{ C}\) istotnie skłamał, jeśli każdy z nich zwykł kłamać z prawdopodobieństwem \(\displaystyle{ \frac{1}{3}}\) ?
4. Ile może istnieć maksymalnie \(\displaystyle{ k-1}\) cykli w grafie, w którym nie ma \(\displaystyle{ k}\) cykli ?
5. W zawodach pływackich wzięło udział pięciu zawodników, którzy pływali na torach basenu oznaczonych numerami od 1 do 5.
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ć ?
6. Udowodnić, że równanie \(\displaystyle{ 3y^2 = x^4+x}\) nie ma rozwiązań w liczbach naturalnych
7. Wyznaczyć wszystkie funkcje \(\displaystyle{ f: R \backslash \{ 0, 1 \} \mapsto R}\) takie że
\(\displaystyle{ f(x)+ f(\frac{1}{1-x}) = 1 + \frac{1}{x(1-x)}}\)
gdy \(\displaystyle{ x \neq 0}\) i \(\displaystyle{ x \neq 1}\)
8. Syn profesora Żabackiego, student czwartego roku Instytutu Zagadkowego odbywając praktykę na jednym z dworców kolejowych, otrzymał polecenie policzenia wagonów stojących na pięciu bocznicach dworca. Zdenerwowany sposobem wykorzystywania jego wiedzy zakpił z szefa i po wykonaniu polecenia zostawił na jego biurku kartkę z następującą informacją:
– wszystkich wagonów jest nie więcej jak 16640
– liczba wagonów zarówno na wszystkich bocznicach jak i na każdych czterech
dowolnych z nich jest kwadratem rożnych liczb
– liczba wagonów na każdej bocznicy jest wyrażona liczbą o tej samej ilości cyfr.
Ile było wagonów na każdej bocznicy ?
Rozkosze Łamania Głowy

[Premislav]

1.:    

\(\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.

[JakimPL]

3:    

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}}\).

7:    

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}\).

[Premislav]

6.:    

\(\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.

[kerajs]

5:    

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}}\)

[Elayne]

8. Szczątkowe rozwiązanie:    

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.

[Vax]

2:    

\(\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}\)

[mol_ksiazkowy]

Co z 4 ?

[Dasio11]

Czy treść tego zadania jest na pewno poprawna? Zdaje się, że odpowiedzią jest "dowolna liczba naturalna \(\displaystyle{ n}\)", o czym świadczy suma \(\displaystyle{ n}\) rozłącznych cykli długości \(\displaystyle{ k-1}\).

[mol_ksiazkowy]

być może należy załozyc spójność....

[Dasio11]

To też niewiele da, bo opisany przykład da się uspójnić \(\displaystyle{ n-1}\) krawędziami tak, żeby nie powstały nowe cykle.

Zakładam oczywiście, że mowa jest o cyklach prostych, ale w przeciwnym razie zadanie też jest raczej nieciekawe.