[LXI OM] I etap

[Swistak]

Nie wiadomo też, czy do pierwszych klas nie przyszło pokolenie genialnych matematyków.

No jak to? Ja, ty, tyle wystarczy xD.
Ofc żartuję ;P.

[kubus1353]

No i jak wam poszedł I etap? Ile zadanek zrobiliście i jak oceniacie poziom? Ciekawy jestem. Ja wysłałem 8 zadań, więc zobaczymy!

[Flesiu]

Ale drugi etap to dla niektórych zdobywanie doświadczenia, niektórzy wiedzą że na finał jeszcze za mało umieją, ale zawsze oswoją się z "atmosferą" olimpiady. Mówię tu oczywiście o pierwszych, drugich klasach. W trzeciej już nie ma na co zdobywać doświadczenia, bo więcej szans nie ma.

[szablewskil]

ale raczej jak ktoś nie może zrobić 5 zadań przez 3 miesiące w domu (a takie są zwykle progi) to raczej będzie miał pewien problem ze zrobieniem trzech - czterech na II etapie.

Z tym to różnie. II etap bardzo różni się od I. Po pierwsze rozwiązujesz na określony czas, po drugie większy stres, po trzecie bardzo dużo zależy od samopoczucia danego dnia. Wiedzę na zrobienie 3-4 zadań ma raczej każdy na II etapie, kwestia tego żeby ją wykorzystać. Na I etapie zadania z reguły są bardziej złożone, na II to często kwestia pomysłu (chwytu)
Ogólnie to ostatnio zupełnie nic nie wiadomo bo za często zmieniają komitet zadaniowy

[karolina668]

8 zadań w całości i do tego 2 zadania "do połowy", bo niestety nie udało mi się ich dokończyć. Ile Wam wyszło w zad. 9 i 12?

[fafner]

Jak wam wyszło 12? Ja podam moje "pół" rozwiązania tego zadania ;p
więc: ułożeniem n-rzędu nazwijmy wypełnieniem je n-1 kamykami ( po 1 w każdym) czyli ułożenie 5-rzędu to będzie tak(cyfry oznaczają ilość kamyków w każdym kubku:
\(\displaystyle{ [0,0],[0,0],0

1,1,[0],[0],0

1,1,1,[0],[0],

1,1,1,1,0}\)
zajęło to 3 rundy
warto zauważyć ze jakbyśmy chcieli zrobić tak aby w każdym kubku była inna ilość kamieni to teraz trzeba było się wziąć za ułożenie 4-rzędy( te w których jest jeden kamień) potem 3-rzędu, i 2.
I rysujemy tabele gdzie będzie ilość kubków n, ile nam zajmie rund ułożenie tylko n-rzędu oraz minimalna ilość rund czyli ile nam zajmie ułożenie n-rzędu+(n-1)-rzędu+...+2-rzędu. I wzór ogólny na minimalną ilość rund wyjdzie:
\(\displaystyle{ [log(n-1)]+[log(n-2)]+..+[log(2)]+n-1}\)
podstawą do każdego logarytmu jest 2
jestem tego prawie pewien tylko co dalej? ;p

[jerzozwierz]

fafner, Twój sposób jest nieoptymalny. Bo marnotrawstwem jest w drugiej rundzie wybieranie zbiorów jednoelementowych, podczas gdy da się "wycisnąć" od F-a większe.

Co do ogólnego tematu. Wysłałem 10 zadań, raczej wszystkie dobrze. Nie ruszyłem 11 ani 12 (znaczy myślałem dość sporo nad nimi, ale konkretnego wniosku brak). Poziom oceniam na prostszy niż był rok czy dwa lata temu.
Mój podział zadań:
1,2,3,9 - bardzo łatwe
5,6,10 - w miarę, spokojnie do zrobienia
4,7 - średnie
8 - trudne
11,12 - hardkor.
Od najłatwiejszego lecąc 2 3 1 9 6 10 5 7 4 8 11 12.
Jak ktoś ma kompletny dowód do 11 lub 12, prosiłbym o zamieszczenie bo jestem niezmiernie ciekawy

[fafner]

w którym miejscu dokładnie da się wycisnąć i od jakiego "f"-a większe co?

[jerzozwierz]

Popatrz: jesteśmy K. Chodzi nam o to, żeby jak najszybciej zdobyć jak najwięcej fasolek. Ty w drugiej rundzie wybierasz dwa zbiory jednoelementowe. Po co? Jakbyś wybrał dwuelementowe, to F byłby zmuszony wrzucić gdzieś dwie fasolki - korzyść dla nas. Tak więc da się grać optymalniej.

[karolina668]

Co myślicie o tym:
Niech \(\displaystyle{ a _{i}}\) oznacza liczbę kubków w zbiorze A z i=0,1,2.... fasolkami, zaś \(\displaystyle{ b_{i}}\) liczbę kubków z i=0,1,2.... fasolkami w zbiorze B
Niech gracz K przyjmie taką strategię: w każdej rundzie wskazuje takie zbiory kubków A i B, że dla każdego i= 0,1,2... \(\displaystyle{ a_{i} = b_{i}}\) oraz liczba wskazanych kubków jest możliwie największa. Zbiory A i B są więc identyczne i nie ma znaczenia ktory z nich wybierze gracz F, zatem ta strategia zawsze daje graczowi K zwycięstwo (wygrywa gdy w n kubkach będzie miał kolejno 0,1,2,n-1 fasolek).
Jest to strategia niezależna od gracza F i doszłam do wniosku, że nie istnieje żadna inna strategia niezależna od F, dająca zwycięstwo K w mniejszej ilości rund niż ta opisana powyżej.
W tej opisanej powyżej mamy:
dla n=2, l=1 (gdzie l-liczba rund)
dla n=3, l=3
dla n=4, l=4
i wykazałam indukcyjnie, że dla \(\displaystyle{ n \ge 4}\) dla n+1 kubków K może uzyskać zwycięstwo, jeśli przeprowadzi 2 rundy więcej niż w przypadku n kubków
czyli dla n=5 , l=6,
dla n =6, l=8 itd
więc l=2n-4
więc \(\displaystyle{ 2n-4 \le cn}\)
i korzystając z granicy przy n sążącym do nieskonczonosci mamy, że \(\displaystyle{ c \ge 2}\)

[jerzozwierz]

Miałem praktycznie taki sam pomysł. Znalazłem w nim jednak kilka luk - po pierwsze, na pewno istnieje strategia optymalniejsza dla K. Oto dlaczego: piszesz że wybierasz zbiory identyczne. Robiąc to zadanie, na pewno zorientowałaś się na czym to polega: gramy dla n w taki sposób, żeby w każdej rundzie dostawać możliwie najwięcej fasolek. Oczywiście na początku wybieramy zbiory dopełniające się do całości, w przeciwnym wypadku marnujemy fasolki. Ale uwaga - gdy zostanie tylko jeden pusty kubek, to już nie możemy go wybierać do żadnego z podzbiorów: w przeciwnym wypadku F wrzuci tam fasolkę i musimy skądś skombinować jeszcze n fasolek. Tak więc jak zostanie jeden pusty kubek, to tak jakby gramy od tej chwili na n-1 kubkach. Rzecz polega na tym, że zbiory pozornie identyczne jednak mogą się nieco różnić. Otóż dla K ważne jest ustawienie fasolek w kubkach - kiedy są bardziej "napchane" - tzn jest spora różnica między tym gdzie jest najwięcej fasolek a w tym gdzie jest najmniej, to jest dla niego korzystniej, gdyż może dłużej wybierać większe podzbiory. I doszedłem do tego, że największy problem jest gdy mamy "aktualne" n nieparzyste. Wówczas jeden podzbiór jest większy od drugiego. Pytanie, czy F woli konserwatywnie wrzucać zawsze tam gdzie mniej, czy poświęci tą jedną fasolkę więcej, aby uzyskać lepsze dla siebie ustawienie do przyszłych rund. Mniej więcej po tym wniosku dałem sobie spokój z tym zadaniem, bo przypadków do rozpatrzenia mamy multum i jeszcze trochę.

[kubus1353]

no ja mam zupełnie inny pogląd na temat trudności zadań, ale nie ma się sprzeczać, zachowam go dla siebie... Mimo wszystko uważam, że 7 zadanie syntetycznie rozwiązań było najtrudniej.

[jerzozwierz]

A kto powiedział że trzeba było robić syntetycznie? Uznałem to zadanie za średnie ze względu na łatwość spałowania.

[fafner]

Niech gracz K przyjmie taką strategię: w każdej rundzie wskazuje takie zbiory kubków A i B, że dla każdego i= 0,1,2... \(\displaystyle{ a_{i} = b_{i}}\) oraz liczba wskazanych kubków jest możliwie największa. Zbiory A i B są więc identyczne i nie ma znaczenia ktory z nich wybierze gracz F, zatem ta strategia zawsze daje graczowi K zwycięstwo (wygrywa gdy w n kubkach będzie miał kolejno 0,1,2,n-1 fasolek).

Heh brzmi jak ta moja taktyka tylko jest jednak inaczej, jak to by wyglądało np przy 5 kubkach, tak samo jak u mnie? (patrz wyżej)-- 1 grudnia 2009, 17:34 --jerzozwierz, to daj jakiś przykład że przy tym jest mnie rund, ja szukałem i nie znalazłem.

[jerzozwierz]

[0,0],[0,0,0]
[1,0],[1,0,0]
2,1,1,0,0
3,1,1,1,0
[3],[2],2,1,0
4,[2],[2],1,0
4,3,2,1,0

Po 6 rundach koniec. Ty byś nie doszedł do końca w 6.