[MIX] 20 zadań

[Inkwizytor]

Zadanie 17 - poprawione:    

Mój pomysł polega na generowaniu niepowtarzających się zestawów cyfr (które trzeba potem jeszcze permutować aby uzyskać wszystkie możliwości)

\(\displaystyle{ n}\) - liczba cyfr składających na liczbę naturalną. \(\displaystyle{ n \in <2,11>}\)
\(\displaystyle{ x_1 , x_2 , ... ,x_n}\) - cyfry składowe "budujące" liczbę n-cyfrową
WARUNEK 1: \(\displaystyle{ \sum_{i=1}^{n} x_i =11}\)
WARUNEK 2: \(\displaystyle{ 0<x_i \le 9}\)
Aby uniknąć powtórzenia sie składu cyfr w różnych krokach zakładamy:
WARUNEK 3: \(\displaystyle{ x_1 \le x_2 \le ... \le x_n}\)

Mam nadzieję że po paru krokach każdy zorientuje się na czym polega "wyczerpywalność" wszystkich możliwości dla danego n
Generowanie cyfr składowych:
a) \(\displaystyle{ n=2}\)
Zestawy cyfr to: \(\displaystyle{ (2,9) ; (3,8) ; (4,7) ; (5,6)}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 4 \cdot 2!}\)

b) \(\displaystyle{ n=3}\)
Zestawy cyfr to: \(\displaystyle{ (1,1,9) ; (1,2,8) ; (1,3,7) ; (1,4,6) ; (1,5,5) ; (2,2,7) ; (2,3,6) ; (2,4,5) ; (3,3,5) ; (3,4,4)}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 5 \cdot 3! + 5 \cdot \frac{3!}{2!}}\) (W 5 przypadkach występi permutacja z powtórzeniami)

c) \(\displaystyle{ n=4}\)
Zestawy cyfr to: \(\displaystyle{ (1,1,1,8) ; (1,1,2,7) ; (1,1,3,6) ; (1,1,4,5) ;}\)\(\displaystyle{ (1,2,2,6) ; (1,2,3,5) ; (1,2,4,4) ; (1,3,3,4) ; (2,2,2,5) ; (2,2,3,4) ; (2,3,3,3)}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 4! + 7 \cdot \frac{4!}{2!} + 3 \cdot \frac{4!}{3!}}\) (uwzględnienie permutacji z powtórzeniami)

d) \(\displaystyle{ n=5}\)
Zestawy cyfr to: \(\displaystyle{ (1,1,1,1,7) ; (1,1,1,2,6) ; (1,1,1,3,5) ; (1,1,1,4,4) ;}\)\(\displaystyle{ (1,1,2,2,5) ; (1,1,2,3,4) ; (1,1,3,3,3) ;}\)\(\displaystyle{ (1,2,2,2,4) ; (1,2,2,3,3) ; (2,2,2,2,3)}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 2 \cdot 5+ 3 \cdot \frac{5!}{3!} + 2 \cdot \frac{5!}{3! \cdot 2!}+2 \cdot \frac{5!}{2! \cdot 2!} + \frac{5!}{2!}}\) (uwzględnienie permutacji z powtórzeniami)

e) \(\displaystyle{ n=6}\)
Zestawy cyfr to: \(\displaystyle{ (1,1,1,1,1,6) ; (1,1,1,1,2,5) ; (1,1,1,1,3,4) ; (1,1,1,2,2,4) ; (1,1,1,2,3,3) ; (1,1,2,2,2,3) ; (1,2,2,2,2,2) ;}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 2 \cdot 6 + 2 \cdot \frac{6!}{4!} + 3 \cdot \frac{6!}{3! \cdot 2!}}\) (uwzględnienie permutacji z powtórzeniami)

f) \(\displaystyle{ n=7}\)
Zestawy cyfr to: \(\displaystyle{ (1,1,1,1,1,1,5) ; (1,1,1,1,1,2,4) ; (1,1,1,1,1,3,3) ; (1,1,1,1,2,2,3) ; (1,1,1,2,2,2,2)}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 7 + \frac{7!}{5!} + \frac{7!}{5! \cdot 2!}+ \frac{7!}{4! \cdot 2!}+\frac{7!}{4! \cdot 3!}}\) (uwzględnienie permutacji z powtórzeniami)

g) \(\displaystyle{ n=8}\)
Zestawy cyfr to: \(\displaystyle{ (1,1,1,1,1,1,1,4) ; (1,1,1,1,1,1,2,3) ; (1,1,1,1,1,2,2,2)}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 8 + \frac{8!}{6!} + \frac{8!}{5! \cdot 3!}}\) (uwzględnienie permutacji z powtórzeniami)

h) \(\displaystyle{ n=9}\)
Zestawy cyfr to: \(\displaystyle{ (1,1,1,1,1,1,1,1,3) ; (1,1,1,1,1,1,1,2,2)}\)
Ilość liczb dwucyfrowych: \(\displaystyle{ 9 + \frac{9!}{2! \cdot 7!}}\) (uwzględnienie permutacji z powtórzeniami)

i) \(\displaystyle{ n=10}\)
Zestawy cyfr to: 9 "jedynek" i jedna "dwójka".
Pozycja "dwójki" może być wybrana na 10 sposobów.

j) \(\displaystyle{ n=11}\)
Chyba oczywiste że będzie jedno rozwiązanie: \(\displaystyle{ 11111111111}\)

Ufff... Pozostaje tylko zliczenie tego:
\(\displaystyle{ 8+45+120+210+252+210+120+45+10+1=1021}\)

Rozwiązanie nie byłoby do końca poprawne gdyby nie pomoc aresa i inspiracja Qń

-- 24 lut 2012, o 11:49 --

Zadanie 16 po modyfikacji treści zadania

Zadanie 16:    

Pokazać że \(\displaystyle{ \cos{\sin{x}} > \sin{\cos{x}}}\) dla dowolnego x.

Fakt 1. Funkcje wew. w obu przypadkach maja okres \(\displaystyle{ 2 \pi}\) zatem dla większej czytelności rozważania można przeprowadzić dla wybranego przedziału (o takiej właśnie szerokości) a potem powołać się na okresowość tychże.

Fakt 2. W nawiązaniu do poprzedniego mego rozwiązania kilka postów wyżej, funkcje wew. przyjmują wartości w przedziale \(\displaystyle{ <-1,1>}\). Zatem taka jest dziedzina obu funkcji zew.
Po nałożeniu wykresów \(\displaystyle{ y= \cos t}\) oraz \(\displaystyle{ y= \sin k}\) dla \(\displaystyle{ t,k \in <-1,1>}\)



Zauważyć można że tylko w przedziale \(\displaystyle{ t,k \in < \frac{\pi}{4} ,1>}\)
\(\displaystyle{ \sin k \ge \cos t}\)
Poza tym przedziałem nierówność z treści zadania jest prawdziwa
Zatem dalsze rozważania można przeprowadzić tylko dla następujących warunków:
\(\displaystyle{ t \in < \frac{\pi}{4} ,1> \wedge k \in < \frac{\pi}{4} ,1> \\
\sin x \in < \frac{\pi}{4} ,1> \wedge \cos x \in < \frac{\pi}{4} ,1>}\)

Ponadto \(\displaystyle{ \frac{\pi}{4} > 0,785}\)

Z analizy wykresów funkcji \(\displaystyle{ \sin x}\) i \(\displaystyle{ \cos x}\) wynika że nie istnieje taki x dla którego obie funkcje przyjmują jednocześnie wartość \(\displaystyle{ 0,785}\) albo i więcej
(co również można dodatkowo uzasadnić za pomocą jedynki trygonometrycznej)

A więc taki przypadek jak rozważony przed chwilą nie ma miejsca dla żadnego x.
Stąd prawdziwa jest nierówność z zadania.

[Qń]

Zadanie 17:    

Dla \(\displaystyle{ 1\le k\le 11}\) liczb \(\displaystyle{ k}\)-cyfrowych o żądanej własności jest prawie tyle co rozwiązań w liczbach całkowitych dodatnich równania:
\(\displaystyle{ x_1+x_2+ \ldots +x_k=11}\)
bo prawie każde rozwiązanie takiego równania składa się z liczb jednocyfrowych (z wyjątkiem \(\displaystyle{ 11,10+1,1+10}\)), czyli generuje nam jedną liczbę o żądanej własności.Czyli \(\displaystyle{ \binom{10}{k-1}}\).Ostatecznie więc odpowiedzią jest:
\(\displaystyle{ -3+\sum_{k=1}^{11}\binom{10}{k-1}=-3+\sum_{k=0}^{10}\binom{10}{k}=-3+1024=1021}\)

Q.

[ares41]

Inkwizytor, Sprawdź czy to są wszystkie możliwości
Np. dla \(\displaystyle{ n=7}\) brakuje jeszcze \(\displaystyle{ (1,1,1,2,2,2,2)}\)

PS:    

W każdym przypadku

Ilość liczb dwucyfrowych:

?
Chyba za dużo Ctrl+C, Ctrl+V

[Inkwizytor]

Dzięki, poprawione

Ukryta treść:    

Skupiałem się przede wszystkim na tym by mi sesja nie wygasła, aby mnie nie wylogowało

[ares41]

Jeszcze mało

Ukryta treść:    

Brakuje \(\displaystyle{ 66}\)

[Panda]

Bez zespolonych:

9:    

\(\displaystyle{ x^{3} \equiv 1 (\mod x^{2} + x + 1)}\), jak Qń zauważył, a traktując każdy jednomian tym przystawaniem, dostajemy \(\displaystyle{ a_{0} + a_{1}x^{3} + ... + a_{n}x^{3n} \equiv a_{0} + a_{1} + a_{2} + ... + a_{n}}\), co jest zerem wtedy i tylko wtedy, gdy zachodzi podzielność.

[Sylwek]

Specjalnie dla Inkwizytora napiszę kilka zdań o zadaniu 17

17:    

Specjalny przypadek dla liczb dwucyfrowych - jest ich 8. Dalej rozpatrzmy pewne \(\displaystyle{ k \in \lbrace 3,4,\ldots,11 \rbrace}\) i policzmy wszystkie liczby k-cyfrowe, których suma cyfr wynosi 11. Ta liczba jest równa ilości różnych ciągów liczb całkowitych dodatnich \(\displaystyle{ (a_1, a_2, \ldots , a_k)}\) takich, że \(\displaystyle{ a_1+a_2+\ldots+a_k=11}\) (jest bijekcja, ponieważ wszystkie liczby \(\displaystyle{ a_i}\) należą do langle 1, 9
angle).

Mamy więc 11 jedynek i 10 plusów między nimi (w ten sposób: \(\displaystyle{ 1+1+1+1+1+1+1+1+1+1+1}\)) i niektóre plusy zastępujemy przegródką: "\(\displaystyle{ @}\)", tak, aby przegródek było \(\displaystyle{ k-1}\), a kolejne sumy (suma sum jest = 11) oddzielone przegródkami były kolejnymi wyrazami naszego ciągu (np. \(\displaystyle{ 1+1@1+1+1+1@1@1+1+1+1}\)) odpowiada ciągowi \(\displaystyle{ (a_1,a_2,a_3,a_4)=(2,4,1,4)}\), czyli liczbie \(\displaystyle{ 2414}\). Możliwości wstawienia tych przegródek jest oczywiście \(\displaystyle{ \binom{10}{k-1}}\). Podsumowując, suma jest równa:
\(\displaystyle{ 8+\sum_{k=3}^{11} \binom{10}{k-1} = 8+\sum_{k=2}^{10} \binom{10}{k} = 8+2^{10} - \binom{10}{0} - \binom{10}{1} = 1021}\)

UWAGA: Musieliśmy zrobić specjalny przypadek dla liczb dwucyfrowych, ponieważ 11=10+1=1+10, ale "10" nie jest cyfrą w zapisie dziesiętnym, więc nie zachodziłaby tu bijekcja pomiędzy ciągami liczb sumujących się do 11, a liczbami o sumie cyfr 11.

Edit po przeczytaniu poniższego postu: Aha, nie zauważyłem rozwiązania Qń-a

[Inkwizytor]

Specjalnie dla Inkwizytora napiszę kilka zdań o zadaniu 17

Ależ ja wiem na czym to polega. Gdy zobaczyłem rozwiązanie Qń'a wiedziałem już gdzie poszło coś nie tak w moim toku rozumowania (początek miałem analogiczny). Koniec końców urodził mi się algorytm postępowania przedstawiony w rozwiązaniu Swoją drogą dobre zadania na ćwiczenia z algorytmów kombinatorycznych

[Ponewor]

18.

Ukryta treść:    

można tu ładnie zaaplikować twierdzenie Caseya

Mógłbyś nieco rozwinąć?

[mol_ksiazkowy]

Nierozwiązane to : 3, 6, 11, 18 (?) , 19

[Dasio11]

3.:    

Klasyka: podciąg nazwiemy łańcuchem, jeśli każdy wyraz dzieli wyraz następny, a antyłańcuchem, gdy żaden wyraz nie dzieli następnego. Dla \(\displaystyle{ i = 1, \ldots, mn+1}\) niech \(\displaystyle{ \alpha(i)}\) oznacza największą długość łańcucha kończącego się na \(\displaystyle{ a_i}\), z kolei \(\displaystyle{ \beta(i)}\) niech oznacza największą długość takiego antyłańcucha. Wtedy \(\displaystyle{ (\alpha(i), \beta(i)) \neq (\alpha(j), \beta(j))}\) dla \(\displaystyle{ i < j}\), są bowiem dwa przypadki:

(i) \(\displaystyle{ a_i \mid a_j}\) - wtedy oczywiście \(\displaystyle{ \alpha(j) > \alpha(i)}\);
(ii) \(\displaystyle{ a_i \nmid a_j}\) - wówczas \(\displaystyle{ \beta(j) > \beta(i)}\).

Z zasady szufladkowej Dirichleta musi zatem istnieć takie \(\displaystyle{ i \in \{ 1, \ldots, mn+1 \}}\) dla którego \(\displaystyle{ \alpha(i) > m}\) lub \(\displaystyle{ \beta(i) > n}\), co jest tożsame z tezą zadania.

6.:    

Teza jest natychmiastową konsekwencją faktu (a w zasadzie definicji), że wielomiany wielu zmiennych są równe wtedy i tylko wtedy, gdy ich współczynniki przy każdym jednomianie postaci \(\displaystyle{ X_1^{\alpha_1} \cdot X_2^{\alpha_2} \cdot \ldots \cdot X_n^{\alpha_n}}\) są równe.

11.:    

(a) Wystarczy wykazać przez indukcję, że \(\displaystyle{ b_n \le 2 - \frac{2}{\sqrt{a_n}}}\). Dla \(\displaystyle{ n = 0}\) teza jest oczywista, ustalmy więc \(\displaystyle{ n \ge 0}\) spełniające naszą tezę. Oczywiście mamy wtedy

\(\displaystyle{ b_n \le 2 - \frac{2}{\sqrt{a_n}}}\)

a ponadto

\(\displaystyle{ b_{n+1} - b_n = \left( 1 - \frac{a_n}{a_{n+1}} \right) \cdot \frac{1}{\sqrt{a_{n+1}}} = \frac{a_{n+1} - a_n}{a_{n+1} \sqrt{a_{n+1}}} \stackrel{(\bigstar_n)}{\le} \frac{2 \left( a_{n+1}-a_n \right)}{\sqrt{a_n} \sqrt{a_{n+1}} \big( \sqrt{a_{n+1}} + \sqrt{a_n} \big)} = \frac{2}{\sqrt{a_n}} - \frac{2}{\sqrt{a_{n+1}}},}\)

co po dodaniu stronami natychmiast daje żądaną tezę dla \(\displaystyle{ n+1}\).

(b) Z powyższego dowodu widać, że \(\displaystyle{ b_n}\) różni się od \(\displaystyle{ 2 - \frac{2}{\sqrt{a_n}}}\) o sumę wszystkich różnic na nierównościach \(\displaystyle{ (\bigstar_i)}\) dla \(\displaystyle{ i = 0, \ldots, n-1}\), trzeba więc tak dobrać liczby \(\displaystyle{ (a_1, \ldots, a_n)}\), by ta suma była jak najmniejsza oraz \(\displaystyle{ a_n}\) było dostatecznie duże, a wtedy \(\displaystyle{ b_n \approx 2}\). Konkretnie: podstawiając \(\displaystyle{ a_{n+1} - a_n = \varepsilon_n}\), szacujemy

\(\displaystyle{ \begin{align*}
\Delta(\bigstar_n) & = \frac{2 \left( a_{n+1}-a_n \right)}{\sqrt{a_n} \sqrt{a_{n+1}} \big( \sqrt{a_{n+1}} + \sqrt{a_n} \big)} - \frac{a_{n+1} - a_n}{a_{n+1} \sqrt{a_{n+1}}} = \frac{a_{n+1}-a_n}{\sqrt{a_{n+1}}} \cdot \left( \frac{2}{\sqrt{a_n} \big( \sqrt{a_{n+1}} + \sqrt{a_n} \big)} - \frac{1}{a_{n+1}} \right) \\
& \le \frac{\varepsilon_n}{1} \cdot \left( \frac{2}{\sqrt{a_n} \big( \sqrt{a_n} + \sqrt{a_n} \big)} - \frac{1}{a_{n+1}} \right) = \varepsilon_n \cdot \frac{a_{n+1} - a_n}{a_n a_{n+1}} \le \varepsilon_n^2.
\end{align*}
}\)

Widzimy więc, że dla ustalonego \(\displaystyle{ N \in \NN}\) jeśli dobierzemy liczby \(\displaystyle{ a_0 \le a_1 \le a_2 \le \ldots}\) tak by przyrosty wyniosły \(\displaystyle{ \varepsilon_n = \frac{1}{N^3}}\), to dostaniemy

\(\displaystyle{ a_{N^5} = a_0 + \sum_{n=0}^{N^5-1} \varepsilon_n = a_0 + N^5 \cdot \frac{1}{N^3} > N^2 \\[1ex]
b_{N^5} = 2 - \frac{2}{\sqrt{a_{N^5}}} - \sum_{n=0}^{N^5-1} \Delta(\bigstar_n) > 2 - \frac{2}{N} - N^5 \cdot \frac{1}{N^6} = 2 - \frac{3}{N}}\)

i oczywiście \(\displaystyle{ b_n > 2 - \frac{3}{N}}\) dla \(\displaystyle{ n > N^5}\), tak jak chcemy.