[MIX] Kilka zadań na deszczowe wieczory

[ares41]

1. Znaleźć największą liczbę całkowitą \(\displaystyle{ A}\), taką, że dla każdej permutacji zbioru liczb naturalnych nie większych od \(\displaystyle{ 100}\) suma pewnych \(\displaystyle{ 10}\) kolejnych wyrazów jest co najmniej równa \(\displaystyle{ A}\).

2. Niech \(\displaystyle{ X_n \text{ i } Y_n}\) będą niezależnymi zdarzeniami losowymi o tym samym rozkładzie:
\(\displaystyle{ \left\{ \left( \frac{k}{2^n}, \frac{1}{2^n} \right) : k=0,1,...,2^{n-1} \right\}}\)
Oznaczamy przez \(\displaystyle{ p_n}\) prawdopodobieństwo zdarzenia, że istnieje liczba rzeczywista \(\displaystyle{ t}\) spełniająca równanie \(\displaystyle{ t^2+X_n \cdot t+Y_n=0}\).

Obliczyć \(\displaystyle{ \lim_{n \to \infty } p_n}\).

3. Łososie płynąc w górę rzeki muszą pokonać dwa wodospady. Prawdopodobieństwo, że łosoś pokona pierwszy wodospad w danej próbie, wynosi \(\displaystyle{ p>0}\), a prawdopodobieństwo pokonania drugiego wodospadu w danej próbie wynosi \(\displaystyle{ q>0}\). Zakładamy, że kolejne próby forsowania wodospadów są niezależne. Obliczyć prawdopodobieństwo, że łosoś nie przebędzie pierwszego wodospadu w \(\displaystyle{ n}\) próbach pod warunkiem, że w \(\displaystyle{ n}\) próbach nie pokona obu wodospadów.

4. Dla ustalonej liczby naturalnej \(\displaystyle{ n \ge 2}\) określamy:
\(\displaystyle{ x_1=n, \ \ y_1=1, \ \ x_{i+1}= \left[ \frac{1}{2}(x_i+y_i) \right], \ \ y_{i+1}= \left[ \frac{n}{x_{i+1}} \right]}\).
Dowieść, że \(\displaystyle{ \text{min}\{x_1, x_2,...,x_n\}=\left[\sqrt{n} \right]}\)

5. Znaleźć najmniejszą wartość funkcji określonej w zbiorze liczb rzeczywistych następujacym wzorem
\(\displaystyle{ f(t)= \sum_{i=1}^{n} \frac{ \sqrt{|x_i-t|} }{2^i}}\)

6. Doświadczenie polega na wykonaniu \(\displaystyle{ n}\) niezależnych prób. Prawdopodobieństwo pozytywnego wyniku w \(\displaystyle{ \text{i-tej}}\) próbie wynosi \(\displaystyle{ p_i}\). Niech \(\displaystyle{ r_k}\) będzie prawdopodobieństwem tego, że dokładnie \(\displaystyle{ k}\) prób da wynik pozytywny. udowodnić, że:
\(\displaystyle{ \sum_{i=1}^{n}p_i= \sum_{k=0}^{n}kr_k}\)

7. Na płaszczyźnie dany jest zbiór \(\displaystyle{ M}\) punktów o następujących własnościach:
\(\displaystyle{ 1^{\circ}}\) Punkty zbioru \(\displaystyle{ M}\) nie leżą na jednej prostej.
\(\displaystyle{ 2^{\circ}}\) Jeżeli punkty \(\displaystyle{ A,B,C,D}\) są wierzchołkami równoległoboku oraz \(\displaystyle{ A,B,C \in M}\) to \(\displaystyle{ D \in M}\)
\(\displaystyle{ 3^{\circ}}\) Jeżeli \(\displaystyle{ A,B \in M}\), to \(\displaystyle{ AB \ge 1}\)

Udowodnić, że istnieją takie dwie rodziny prostych równoległych, że \(\displaystyle{ M}\) jest zbiorem przecięcia wszystkich punktów przecięcia prostych pierwszej rodziny z prostymi drugiej rodziny.

8. Prostopadłościenne pudełko można całkowicie wypełnić sześcianami jednostkowymi. Jeżeli będziemy umieszczać w nim sześciany o objętości \(\displaystyle{ 2}\) i krawędziach równoległych do krawędzi pudełka, to maksymalna liczba takich sześcianów wypełni tylko \(\displaystyle{ 40\%}\) pudełka. Wyznaczyć wymiary wewnętrzne tego pudełka.

9. Dowieść, że suma kwadratów wzajemnych odległości \(\displaystyle{ n}\) punktów na sferze jednostkowej nie przekracza \(\displaystyle{ n^2}\)

10 Dla danego naturalnego \(\displaystyle{ n}\) obliczyć liczbę liczb całkowitych \(\displaystyle{ x}\) z przedziału \(\displaystyle{ \left[ 1;n \right]}\), dla których \(\displaystyle{ x^3-x}\) jest podzielne przez \(\displaystyle{ n}\).

\(\displaystyle{ \hline}\)
Uwagi dotyczące zadań proszę kierować na PW

[Swistak]

zad.9:    

Będziemy korzystać z tw. Steinera w 3 wymiarach (w punktach umieszczamy masy jednostkowe). Jak wiadomo środek ciężkości tych punktów minimalizuje sumę kwadratów odległości od nich, zatem suma kwadratów odległości tych punktów od środka jest co najmniej taka jak suma kwadratów odległości od środka ciężkości, czyli suma kwadratów odległości od środka ciężkości jest nie większa niż \(\displaystyle{ n}\). Ustalmy sobie teraz jeden z tych wybranych punktów na sferze. Suma kwadratów jego odległości od pozostałych punktów to na mocy Steinera suma kwadratów odległości tych \(\displaystyle{ n}\) punktów od środka ciężkości plus \(\displaystyle{ n}\)krotność kwadratu odległości danego punktu od środka ciężkości. Sumujemy to po wszystkich punktach i w prosty sposób dostajemy tezę.

[Qń]

Zadanie 6:    

Niech \(\displaystyle{ X_i}\) będzie zmienną losową przyjmującą wartość \(\displaystyle{ 1}\) z prawdopodobieństwem \(\displaystyle{ p_i}\) i wartość \(\displaystyle{ 0}\) z prawdopodobieństwem \(\displaystyle{ 1-p_i}\). Oczywiście \(\displaystyle{ EX_i=p_i}\) oraz \(\displaystyle{ \sum_{i=1}^{n} EX_i=\sum_{i=1}^{n}p_i}\).
Ale
\(\displaystyle{ \sum_{i=1}^{n} EX_i=E \left(\sum_{i=1}^{n} X_i \right)}\)
a zmienna \(\displaystyle{ X=\sum_{i=1}^{n} X_i}\) to przecież zmienna mierząca ile było sukcesów.
Oczywiście z definicji jest \(\displaystyle{ EX=\sum_{i=1}^{n} kr_i}\), co kończy dowód

Q.

[mol_ksiazkowy]

ad 1

Ukryta treść:    

Jeśli A jest najwieksza z sum kolejnych dziesieciu elementów permutacji zbioru \(\displaystyle{ \{ 1,2, ..., 99,100 \}}\), to \(\displaystyle{ 10A \geq (1+...+10) + (11+...+20) + ...+ (81+...+90) +(91+...+100)=5050}\) a zatem \(\displaystyle{ A \geq 505}\)

Z drugiej strony w permutacji:
\(\displaystyle{ 100, \ 1, \ 99, \ 2, \ 98, \ 3, \ 97, \ 4, \ 96, \ 5, ..., \ 51, \ 50}\)
(będacej "splotem" ciagów: \(\displaystyle{ 100, 99, 98, ... ,51}\) i \(\displaystyle{ 1, 2, 3 ...,50}\)) suma dowolnych kolejnych dziesięciu elementów jest nie wieksza niż \(\displaystyle{ 505}\) (gdy pierwszy element tejże sumy ma indeks parzysty to suma ta = \(\displaystyle{ 500}\), a gdy nieparzysty to suma ta= \(\displaystyle{ 505}\))
Szukana liczba to \(\displaystyle{ 505}\)

[mol_ksiazkowy]

Quote

4. Dla ustalonej liczby naturalnej \(\displaystyle{ n \ge 2}\) określamy:
\(\displaystyle{ x_1=n, \ \ y_1=1, \ \ x_{i+1}= \left[ \frac{1}{2}(x_i+y_i) \right], \ \ y_{i+1}= \left[ \frac{n}{x_{i+1}} \right]}\).
Dowieść, że \(\displaystyle{ \text{min}\{x_1, x_2,...,x_n\}=\left[\sqrt{n} \right]}\)

Ukryta treść:    

Jeśli \(\displaystyle{ j<n}\) to \(\displaystyle{ x_{j+1} = \lfloor \frac{x_j + y_j}{2} \rfloor \geq \frac{x_j +y_j -1}{2} = \frac{x_j + \lfloor \frac{n}{x_j} \rfloor -1}{2} > \frac{x_j + \frac{n}{x_j} - 2}{2} \geq \sqrt{n}-1}\)
gdyż:
\(\displaystyle{ \begin{cases} x+ \frac{n}{x} \geq 2\sqrt{x} \\ x \geq \lfloor x\rfloor > x-1 \\ \lfloor \frac{k}{2} \rfloor \geq \frac{k-1}{2}\end{cases}}\)
przy czym w środkowej nierówności \(\displaystyle{ x \in R}\), zaś w ostatniej
\(\displaystyle{ k \in N}\), i zamienia się ona w równość gdy \(\displaystyle{ k}\) będzie nieparzyste…
oraz
\(\displaystyle{ x_1 = n}\)
a tj.
(*) \(\displaystyle{ min \{ x_1, ... , x_n \} \geq \lfloor \sqrt{n} \rfloor}\)

Jednak gdy \(\displaystyle{ x_{j} > \lfloor \sqrt{n} \rfloor}\) ;a więc też \(\displaystyle{ x_{j} > \sqrt{n}}\) dla jakiegoś \(\displaystyle{ j < n}\), to:

\(\displaystyle{ x_{j+1} \leq \frac{x_j +y_j}{2} \leq \frac{x_j + \frac{n}{x_j}}{2} \leq \frac{x_j + \frac{x_j^2}{x_j}}{2} =x_j}\)

ale tak być nie może; bo wtedy ciąg \(\displaystyle{ n=x_1, …, x_n}\) byłby malejący (istotnie), tj. \(\displaystyle{ x_n=1}\), sprzeczne z (*)

I tak np. gdy \(\displaystyle{ n=2013}\)
Początkowe wyrazy tych ciągów to:
\(\displaystyle{ x_1= 2013 \ x_2 = 1012 \ x_3 = 506 \ x_4 = 254 \ x_5 = 130 \ x_6 = 72 \ x_7 = 49 \ x_8 = 45}\) oraz
\(\displaystyle{ y_1= 1 \ y_2 = 1012 \ x_3 = 506 \ x_4 = 254 \ x_5 = 130 \ x_6 = 72 \ x_7 = 49 \ x_8 = 45}\)
tj. ciąg \(\displaystyle{ x_n}\) maleje, \(\displaystyle{ y_n}\) rośnie, i oba te ciągi “zbliżają się” do siebie. Następnie:
\(\displaystyle{ \begin{cases} x_8=45\\y_8=44\end{cases}}\) i:
\(\displaystyle{ \begin{cases} x_9=44\\y_8=45\end{cases}}\) tj.
\(\displaystyle{ x_j= x_9}\) dla \(\displaystyle{ j > 9}\)

przy czym hipoteza (do sprawdzenia) ewentualnie:
\(\displaystyle{ max \{ y_1, ... , y_n \} \in \{ \lfloor \sqrt{n} \rfloor , \lfloor \sqrt{n} \rfloor + 1 \}}\)

[mol_ksiazkowy]

Jeszcze jeden zaniedbany Mix...
3

Ukryta treść:    

[Zahion]

10

Ukryta treść:    

[dec1]

7

Ukryta treść: