Matmix 2008/2009

[dabros]

mój wynik to 38/44 (KAT 2) - zepsułem cały 5 zestaw

[lukasz_650]

Ja mam 44/44 (druga kategoria), ale na razie nie mam żadnego konkretnego pomysłu na zadanie pierwsze z X zestawu, więc pewnie będą pierwsze stracone punkty

[Dumel]

u mnie 42/44 (II) - nie zaznaczylem odpowiedzi w zadaniu z liczbami Catalana

[Swistak]

Ja straciłem do tej pory 3 punkty na tym feralnym zadaniu, gdzie organizatorzy zmienili odpowiedź .
Zadania 1 z X zestawu (obie kategorie) do łatwych bym na pewno nie zaliczał, ale ja je zrobiłem w jakieś 1,5h, więc co z wami ?

[kasidelvar]

44/44 i obecny zestaw zrobiony po 1 dniu ;] A co do Twojej 1,5h to bym polemizował Świstak

[Swistak]

Zrobiłem w 1,5h, tylko wkradł mi się mały błąd obliczeniowy, który nie zmienia tego, że 99% zadania zrobiłem w 1,5h ;P.
Jeżeli ktoś uporał się z tym zadaniem, to przeszedł przez lekką rozgrzewkę aby uporać się z zadaniem 5 z dzisiejszego finału OMG .

[Dumel]

ja sie z tym zadaniem z matmixa męczylem ze 3 godziny w tygodniu (tzn. gapilem sie w kartke bo jakos nie mialem nastroju do myslenia) ale wczoraj mi poszlo w 20 minut

[Swistak]

Gdyby nie Matmix, to miałbym sporo większe szanse na zrobienie zad 5 z OMG . Strzelam focha .

[kejd?ej]

Zobaczymy czym dzisiaj nas zaskoczą

[Sylwek]

Kategoria II, zestaw 10.:
1. g
2. e

Ad 2.:
Niech \(\displaystyle{ f(x)}\) oznacza największy wykładnik dwójki dzielący \(\displaystyle{ x!}\).

Niech \(\displaystyle{ B(n)}\) oznacza sumę cyfr zapisu binarnego liczby \(\displaystyle{ n}\).

Lemat: \(\displaystyle{ B(n)=k}\). Dowiedziemy go indukcyjnie, dla \(\displaystyle{ n=1}\) bezpośrednie sprawdzenie daje nam założenie indukcyjne.

Niech: \(\displaystyle{ f(n)=q}\), z definicji funkcji \(\displaystyle{ f}\) mamy: \(\displaystyle{ f(x)= \sum_{i=1}^{+\infty} \ [ \frac{x}{2^i} ]}\). Zatem: \(\displaystyle{ f(2n)=[ \frac{2n}{2} ] + \sum_{i=2}^{+\infty} \ [ \frac{2n}{2^i} ] = [n]+ \sum_{i=1}^{+\infty} \ [ \frac{n}{2^i} ] = n + f(n)=n+q}\).

Pokażemy, że jeśli teza zachodzi dla \(\displaystyle{ n}\), to zachodzi też dla \(\displaystyle{ 2n}\) i \(\displaystyle{ 2n+1}\) (jest to warunek wystarczający, w sumie jest to oczywiste, więc pomijam tłumaczenie).

Dowiodę to, że jeśli teza zachodzi dla \(\displaystyle{ n}\), to zachodzi też dla \(\displaystyle{ 2n}\), drugi przypadek jest analogiczny. Mamy z założenia: \(\displaystyle{ k=f(2n)-2f(n)=(n+q)-2q=n-q}\), a także: \(\displaystyle{ f(4n)=[\frac{4n}{2}]+[\frac{4n}{4}]+f(n)=3n + q}\), więc: \(\displaystyle{ f(4n)-2f(2n)=(3n+q)-2(n+q)=n-q=k}\).

Zatem jak mnożymy razy dwa, to \(\displaystyle{ k}\) się nie zmienia. Mnożenie razy dwa to dopisanie zera na końcu zapisu binarnego. Podobnie dowodzimy, że \(\displaystyle{ f(4n+2)-2f(2n+1)=k+1}\) - 2k+1 oznacza dopisanie jedynki na końcu zapisu binarnego, wówczas \(\displaystyle{ k}\) rośnie o 1, co kończy dowód lematu.


Teraz to już banał - wystarczy znaleźć ilość liczb 7,8,9,10 i 11-cyfrowych mających 7 jedynek w zapisie binarnym i odjąć ilość takowych liczb, które przekraczają 2008, wynik to: \(\displaystyle{ \binom{6}{6}+\binom{7}{6}+\binom{8}{6}+\binom{9}{6}+\binom{10}{6}-5=325}\)

[ironleaf]

Kategoria II, zestaw 10.:
1. g
2. e

Potwierdzam. A w 1. ze wzoru Eulera wyszło oszacowanie z dołu. Korzystając z warunków na równość skonstruowałem sobie wielościan, który spełnia warunki zadania i zawiera 104 trójkąty oraz 145 czworokątów.

[Dumel]

mam takie same odpowiedzi. w 2. napisalem program ktory mi to policzyl a 1. tak jak ironleaf z tym ze nie udalo mi sie znalezc przykladu takiego wieloscianu
jest nowy zestaw. kombi pewnie pojdzie gladko, a strereo nawet nie chce mi sie czytac bo juz mnie to wkurza ze w kazdym zestawie cos musza z geo dac

[Desmondo]

Korzystając z warunków na równość skonstruowałem sobie wielościan, który spełnia warunki zadania i zawiera 104 trójkąty oraz 145 czworokątów.

Jak Ci się udało taki wielościan skonstruować? Wyszedł mi ten sam wynik, ale nie potrafiłem skonstruować takiego wielościanu.

[abc666]

Potwierdzam odpowiedzi, chociaż w pierwszym to był zwykły strzał. Na szczęście nowy zestaw lajcik raczej.

[kasidelvar]

Nowy zestaw już poszedł, łatwy