[LXI OM] I etap

[Dumel]

w 9. znając życie pewnie wiele osób nie podało przykładu funkcji

czyli jak się nie podało to będą ciąć?:P

no chyba będą musieli do 5 uciąć bo bez przykładu rozwiązanie jest niekompletne - 0 to tylko potencjalna wartość w zerze funkcji, która być może nie istnieje.

[Swistak]

W dwunastym \(\displaystyle{ c \ge \frac{3}{2}}\), rozwiązanie praktycznie widać po rozpisaniu kilku kolejnych przykładów, gorzej z udowodnieniem.
Dla \(\displaystyle{ n \ge 2}\) ilość liczb rund wynosi:

\(\displaystyle{ \frac{3}{2}n - 2}\) dla n parzystego

\(\displaystyle{ 3\frac{n-1}{2}}\) dla n nieparzystego

granica w nieskończoności dla obu wyrażeń podzielonych przez n wynosi \(\displaystyle{ \frac{3}{2}}\)

PS. Wam tez nie działa strona olimpiady? Czyżby dodawali rozwiązania, bądź coś zmieniali?

To se raczej kiepsko rozpisałeś te przykłady...
Ja se rozpisałem beż żadnego algorytmu bodajże do 8 i z algorytmem (wspominany już wcześniej algorytm dzielenia na 2 maxymalne identyczne zbiory) do 12 i postawiłem dość solidną tezę, że liczba ruchów potrzebna do wygrania, to \(\displaystyle{ 2n-[log_{2} n]-2}\), jednak i ona padła po napisaniu tego w C++. Liczba ruchów normalnie skacze o 2, jednak czasami skakała tylko o 1 i wg mojego wzoru powinna skoczyć o 1 przy 16, a skoczyła przy 15 :<. A dalej to już kompletny brak regularności względem mojego wzoru :/. Oto wyniki, które wygenerował mój program stosując ten algorytm:

[pawels]

To zależy od kształtu rozwiązania. Ja udowodniłem, że dla każdej pary f i g spełniających warunki zadania jedyną wartością f w punkcie 0 jest liczba 0.

10 lat temu we wzorcówce zadania 4. z zawodów matematycznych państw bałtyckich nie dowodzono, że badana funkcja istnieje, więc nie sądzę aby było to tutaj wymagane.

To podejście może wynikać z tego, że w tym zadaniu pytają się o wszystkie liczby x, takie że następująca implikacja jest prawdziwa: Jeżeli fi i g są funkcjami spełniającymi założenia zadania to równość f(0)=x nie prowadzi do sprzeczności.

Wówczas wystarczy oczywiście pokazać, to co napisałem w pierwszym zdaniu.

Swoją drogą też byłem przekonany, że w 12. po pierwszych \(\displaystyle{ \lceil \log_2n\rceil}\) ruchach tego samego algorytmu, z których każdy powoduje powstanie nowego kubka z inna liczba fasolek, każdy następny pojawia się op dwóch ruchach:) Ale rozpisywałem tylko do 13, więc stąd to przypuszczenie.

[JWilk]

Powiem wam, że np. na 59 OM 1 zadanie z drugiego etapu wymagało podania przykładu. Znam pare osób, które udowodniły co trzeba, podały poprawną odpowiedż, ale nie podały przykładu no i kosztowało ich to finał...

Jeśli chodzi o cfasolki to u mnie w szkole podaje się taką odpowiedź jak podał Swistak.

[Swistak]

LoL xD <facepalm>
Jakim sposobem w 10. znaleźliście pasujące liczby dla n=3,4? Metodą prób i błędów nie znalazłem żadnego pasującego układu (być może zbyt mało szczęścia co do losowości liczb? ), po czym 80% czasu straciłem na próbowanie udowodnienia, że takie n nie istnieje

A co do 9. - też robiliście "k-tą" iteracją funkcji i dalej idzie z tego, że od pewnego momentu jedna strona jest ujemna, a druga nieujemna?

Moje rozumowanie przebiegało mniej więcej tak:
1. Udowodniłem sobie przypadek z n=2.
2. Dość luźno rozmyślałem nad tym jaka może być odpowiedź.
3. Stwierdziłem, że coś w stylu dowodu dla n=2 nie ma sensu dla większych n i raczej nie ma na to żadnych przeciwwskazań i stwierdziłem, że takie liczby najprawdopodobniej istnieją i zacząłem myśleć nad sposobem ich szukania.
4. Ich losowe szukanie jest dość głupie, jednak po chwili zastanowienia dało się wymyślić sensowny algorytm. Polegał on na tym, że dobieram sobie odpowiednie różne liczby oprócz ostatniej pary, tak aby końcowy iloczyn liczb z jednej grupy wyszedł 2 razy większy niż iloczyn liczb z drugiej grupy i po prostu patrzę na ich różnicę i dostawiam jedna liczbę \(\displaystyle{ r}\), a druga \(\displaystyle{ 2r}\) (gdzie r to ta różnica) i równość iloczynu jak i zarówno sumy jest spełniona. O ile mam farta, to wszystkie liczby są różne, a jak nie, to szukam innych.
Przykładowo dla n=3.
Biorę sobie \(\displaystyle{ a_{1}=1, b_{1}=2}\), nie mogę zrobić tak, aby iloczyn liczb z b wyszedł 2 razy większy, więc teraz dobieram sobie \(\displaystyle{ a_{2}}\) 4 razy większe od \(\displaystyle{ b_{2}}\), zatem \(\displaystyle{ b_{2}=3, a_{2}=12}\). Suma liczb z a, to 13, a suma liczb z b, to 5, więc biorę sobie \(\displaystyle{ a_{3}=8, b_{3}=16}\) i wszystko jest spełnione.

A co do zad 9, to to rozwiązanie z podstawianiem pod n kolejnych iteracji funkcji trochę mi się nie podobało. Moje polegało na tym, że dla n>0 mamy \(\displaystyle{ g(n)>g(f(n))}\), a więc funkcja g nie może przyjąc swojego minimum w punkcie dodatnim, a więc ma swoje jedyne minimum w punkcie 0, więc \(\displaystyle{ g(0)<g(n)}\), dla każdego n>0, a skoro \(\displaystyle{ g(0)=g(f(0))}\), to \(\displaystyle{ f(0)=0}\). To rozwiązanie nie wykorzystuje też faktu, że obie funkcje przekształcają zbiór naturalnych w naturalne .

[mazur89]

W zadaniu 12. wychodzi \(\displaystyle{ c\geq 2}\). Dla \(\displaystyle{ c=2}\) stosunkowo łatwo wypisać jakąś strategię, a dalej rozumujemy tak: niech kubeczek o numerze \(\displaystyle{ k}\) ma wartość \(\displaystyle{ (1+x)^{a_k}}\), gdzie \(\displaystyle{ a_k}\) oznacza liczbę fasolek w kubeczku. Wrzucenie fasolek do odpowiednich kubeczków oznacza pomnożenie ich wartości przez \(\displaystyle{ (1+x)}\). Gracz wybierający jeden z dwóch podzbiorów może zadbać o to, aby zawsze jego łączna wartość nie przekroczyła połowy wartości wszystkich kubeczków, a to oznacza, że zwiększymy wartość całego zbioru kubeczków co najwyżej \(\displaystyle{ 1+\frac{x}{2}}\) razy. Ale żeby w każdym kubeczku była inna liczba fasolek, to cały zbiór musi mieć wartość co najmniej \(\displaystyle{ \frac{(1+x)^n-1}{(1+x)-1}}\), czyli ruchów musi być przynajmniej \(\displaystyle{ n\cdot \frac{\log_{1+\frac{x}{2}}\frac{(1+x)^n-1}{(1+x)-1}}{n}}\), co po przejściu z \(\displaystyle{ n\to \infty}\) daje \(\displaystyle{ c\geq\log_{1+\frac{x}{2}}(1+x)}\), a po przejściu z \(\displaystyle{ x\to 0}\) daje \(\displaystyle{ c\geq2}\).

[kubek1]

Ja tam robiłem w 9 na iteracje i uzyskałem, że funkcja g jest większa od jakiejś tam sumy z iteracjami f. Stąd wynikało, że ta suma musi być zbieżna, gdyż jej wyrazy są nieujemne i stąd było prosto do tezy

[XMaS11]

Heh, przepiękne rozwiązanie ^^

[Dumel]

A co do zad 9, to to rozwiązanie z podstawianiem pod n kolejnych iteracji funkcji trochę mi się nie podobało. Moje polegało na tym, że dla n>0 mamy \(\displaystyle{ g(n)>g(f(n))}\), a więc funkcja g nie może przyjąc swojego minimum w punkcie dodatnim, a więc ma swoje jedyne minimum w punkcie 0, więc \(\displaystyle{ g(0)<g(n)}\), dla każdego n>0, a skoro \(\displaystyle{ g(0)=g(f(0))}\), to \(\displaystyle{ f(0)=0}\). To rozwiązanie nie wykorzystuje też faktu, że obie funkcje przekształcają zbiór naturalnych w naturalne .

wykorzystuje, bo inaczej nie masz gwarancji (no chyba że byś to udowodnił ale nie piszesz abyś to zrobił) że minimum jest osiągane

[jerzozwierz]

Tak się wczytuję w to rozwiązanie 12, i nie mogę ogarnąć co znaczy to x mógłby mnie ktoś oświecić?

[Dumel]

skomplikowana odpowiedź- x to jest jakaś liczba dodatnia
tyle

[Django]

Proste i skuteczne rozwiązanie zadania 9.

Ukryta treść:    

Ponieważ funkcje \(\displaystyle{ f,g}\) przyjmują wartości w zbiorze liczb całkowitych nieujemnych, to wnioskujemy, że zarówno funkcja f, jak i g przyjmują wartość minimalną (bo zbiór \(\displaystyle{ N_{0}}\) jest ograniczony od dołu). Zatem, przyjmijmy że wartość minimalna funkcji g to p, a przyjmuje ją dla argumentu x, czyli mamy: \(\displaystyle{ g(x) = p}\) Podstawiając x:
\(\displaystyle{ g(f(x))=g(x)-x \Leftrightarrow g(f(x))=p-x}\). Jeśli \(\displaystyle{ x \neq 0}\), to sprzeczność, bo istniałaby wtedy wartość mniejsza od wartości minimalnej, a tak być nie może. Czyli, \(\displaystyle{ x=0}\).
Dalej mamy \(\displaystyle{ g(f(0))=p}\). Podstawiając \(\displaystyle{ f(0)=m}\) mamy zaś: \(\displaystyle{ g(m)=p}\), a po podstawieniu m do równości w treści dostajemy: \(\displaystyle{ g(f(m))=g(m)-m}\). I tak jak powyżej wnioskujemy, że m musi być równe 0, bo inaczej istniałaby wartość mniejsza od wartości minimalnej, a tak być nie może. Czyli \(\displaystyle{ f(0)=0}\)

Blefa chyba nie ma
Pzdr

[Swistak]

A co do zad 9, to to rozwiązanie z podstawianiem pod n kolejnych iteracji funkcji trochę mi się nie podobało. Moje polegało na tym, że dla n>0 mamy \(\displaystyle{ g(n)>g(f(n))}\), a więc funkcja g nie może przyjąc swojego minimum w punkcie dodatnim, a więc ma swoje jedyne minimum w punkcie 0, więc \(\displaystyle{ g(0)<g(n)}\), dla każdego n>0, a skoro \(\displaystyle{ g(0)=g(f(0))}\), to \(\displaystyle{ f(0)=0}\). To rozwiązanie nie wykorzystuje też faktu, że obie funkcje przekształcają zbiór naturalnych w naturalne .

wykorzystuje, bo inaczej nie masz gwarancji (no chyba że byś to udowodnił ale nie piszesz abyś to zrobił) że minimum jest osiągane

Nie rozumiem :/. A istnieje funkcja w dodatnich, która nie ma minimum (chodziło mi zejście z naturalnych w nieujemne, może tu się nie wyraziłem precyzyjnie, albo nadal czegoś nie rozumiem)?

[tkrass]

Owszem Wojtku, funkcja może dążyć do jakiejś wartości, ale jej nie przyjmować. Np. \(\displaystyle{ f(x)= \frac{1}{x}}\). A np. kontrprzykładem do funkcji z \(\displaystyle{ N_0}\) w \(\displaystyle{ R_{+}}\) będzie \(\displaystyle{ f(0)=1}\), \(\displaystyle{ f(x+1)= \frac{f(x)}{2}}\) dla \(\displaystyle{ x>0}\).

[Punkitititi]

mazur89, jak dla mnie jesteś bogiem. W sumie to brakło mi czasu na zajęcie się 12, ale i tak nie mam złudzeń.