Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Świstak na imprezę urodzinową zaprosił \(\displaystyle{ 2n}\) osób. Jedną z wielu tradycji tych melanży jest to, że na początku każdy gość pisze na karteczce zadanie i wrzuca do worka. Gdy już wszyscy wrzucą, solenizant wyjmuje je i każdemu gościowi daje jedno. Mówimy, że podział zadań jest "madafaka", jeśli można rozdzielić \(\displaystyle{ n}\) czapeczek czerwonych i \(\displaystyle{ n}\) niebieskich tak, że każdy gość z czerwoną czapeczką dostał zadanie, które do worka wrzucił gość z niebieską czapeczką.
Wykaż, że liczba podziałów "madafaka" jest kwadratem liczby naturalnej.
Zauważmy, że podział "madafaka" to permutacja zbioru \(\displaystyle{ 2n}\)-elementowego, której każdy cykl jest długości parzystej. Policzmy, ile jest permutacji zbioru \(\displaystyle{ 2n}\)-elementowego o cyklach długości \(\displaystyle{ 2a_1,2a_2,\dots,2a_k}\). Oznaczmy ciąg \(\displaystyle{ 2a_1,2a_2,\dots,2a_k}\) przez \(\displaystyle{ \pi}\). Podziałów zbioru \(\displaystyle{ 2n}\)-elementowego na uporządkowane podzbiory o odpowiednio \(\displaystyle{ 2a_1,2a_2,\dots,2a_k}\) elementach jest \(\displaystyle{ \frac{(2n)!}{(2a_1)!(2a_2)!\dots (2a_k)!}}\), zatem na nieuporządkowane jest tyle samo razy \(\displaystyle{ \prod_{i=0}^n x_{i,\pi}!}\), gdzie \(\displaystyle{ x_{i,\pi}}\) jest liczbą wystąpień liczby \(\displaystyle{ 2i}\) w ciągu \(\displaystyle{ 2a_1,2a_2,\dots,2a_k}\). Jeżeli mamy już ustalone zbiory, do których będą należały elementy cykli, to zauważmy, że dla \(\displaystyle{ i}\)-tego cyklu możemy na \(\displaystyle{ (2a_i-1)!}\) sposobów ustawić kolejność jego elementów (jeden ustalamy, reszta ułożona według dowolnej permutacji). Zatem liczba podziałów "madafaka" wynosi \(\displaystyle{ \sum_{a_1+a_2+\dots+a_k=n,a_1\le a_2\le\dots a_k}x_{i,2a_1,2a_2,\dots,2a_k}\frac{(2n)!}{(2a_1)(2a_2)\dots (2a_k)}=\\=\frac{(2n)!}{n!}\sum_{a_1+a_2+\dots+a_k=n,a_1\le a_2\le\dots a_k}x_{i,2a_1,2a_2,\dots,2a_k}\frac{1}{2^k}\frac{n!}{a_1a_2\dots a_k}=\frac{(2n)!}{n!}\sum_{k=0}^{n}\left[ n\atop k\right]\frac{1}{2^k}=\frac{(2n)!}{n!}\frac{1}{2}^{\overline{n}}=\frac{(2n)!}{n!}\frac{1\cdot3\dots(2n-1)}{2^n}=\frac{(2n)!}{n!}\frac{(2n)!}{n!2^n}\frac{1}{2^n}=\left(\frac{(2n)!}{n!2^n}\right)^2,}\)
c.k.d.
Przez f(2n) oznaczmy to, co chcemy. Łatwo zauważyć, ze \(\displaystyle{ f(2n)=(2n-1)f(2n-2)+(2n-1)(2n-2)(2n-3)f(2n-4)+...+(2n-1)!}\). Piszemy teraz ten wzorek dla 2n+2 i otrzymujemy, że \(\displaystyle{ f(2n+2)=(2n+1)f(2n)+(2n+1)2n(2n-1)f(2n-2)+(2n-1)(2n-2)(2n-3)f(2n-4)+...+(2n-1)!)=(2n+1)f(2n)+(2n+1)2nf(2n)=(2n+1)^2f(2n)}\), co w połączeniu z \(\displaystyle{ f(2)=1}\) daje wynik \(\displaystyle{ f(2n)=((2n-1)!!)^2}\)
Inne ciekawe rozwiązanie: Istnieje łatwa bijekcja pomiędzy parami skojarzeń w klice rozmiaru 2n oraz jej pokryciami cyklowymi cyklami o parzystej dlugości. Liczba par skojarzeń w takowej klice, to oczywiście kwadrat, koniec .
