Podzbiory koszerne

[mol_ksiazkowy]

Udowodnić, że ilość podzbiorów \(\displaystyle{ \{ 1,..., n \}}\) takich, że średnia i mediana ich wszystkich elementów są równe jest nieparzysta.

[arek1357]

Takie zbiory, których średnia arytmetyczna i mediana są równe nazywamy symetrycznymi.
Czyli będą to podzbiory typu:

\(\displaystyle{ \left\{ 1,2,3\right\}}\) w każdym

\(\displaystyle{ \left\{ 1,2,5,6\right\}}\) w np. \(\displaystyle{ 6}\)

Każde dwu i jednoelementowe są symetryczne czyli koszerne, itd...

niech.:\(\displaystyle{ a(n)}\) - oznacza ilość podzbiorów zbiorów koszernych w zbiorze \(\displaystyle{ n}\)- elementowym

zauważmy, że:

\(\displaystyle{ a(n+1)=a(n)+b(n+1)+1}\)

Ja teraz podzieliłem zbiór n+1 elementowy na zbiór n elementowy i jedno elementowy:

\(\displaystyle{ \left\{ 1,...,n,n+1\right\}=\left\{ 1,...,n\right\} \cup \left\{ n+1\right\}}\)

\(\displaystyle{ a(n)}\) - oznacza ile jest zbiorów koszernych w pierwszym \(\displaystyle{ n}\) elementowym zbiorze

\(\displaystyle{ a(n+1)}\) - oznacza ile jest zbiorów koszernych w \(\displaystyle{ \left\{ 1,...,n,n+1\right\}}\) zbiorze.

Natomiast :

\(\displaystyle{ ,b(n+1)}\) - oznacza , ile jest zbiorów koszernych, których ostatni element to:\(\displaystyle{ n+1}\)

Zauważmy, że:

\(\displaystyle{ b(n+1)=b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)}\)

Teraz należy się wytłumaczenie:

Będę troszkę nieścisły, i \(\displaystyle{ b(n)}\) może oznaczać wszystkie zbiory koszerne, zaczynające się
jedynką i kończące \(\displaystyle{ n}\), lub zaczynające się dwójką i i kończące :\(\displaystyle{ n+1}\) co na jedno wyjdzie.(oczywiście chodzi o ich ilość)

natomiast co znaczy:

\(\displaystyle{ b(1,k,n+1)}\), otóż jest to ilość zbiorów koszernych o pierwszym elemencie w jedynce,
ostatnim w.: \(\displaystyle{ n+1}\) zawierających dokładnie\(\displaystyle{ k}\) elemenów.

Jak widać rekurencja się zgadza...

Łatwo jest obliczyć precyzyjnie.:\(\displaystyle{ b(1,k,n+1)}\)

otóż:

\(\displaystyle{ b(1,k,n+1)= { \frac{n-2}{2} \choose \left[ \frac{k-2}{2} \right] }}\) , dla \(\displaystyle{ n+1}\) - nieparzystych.


\(\displaystyle{ b(1,k,n+1)= { \frac{n-1}{2} \choose \frac{k-2}{2} }}\) , dla \(\displaystyle{ n+1}\) - parzystych
i\(\displaystyle{ k}\)- parzystych.


\(\displaystyle{ b(1,k,n+1)= 0}\) , dla \(\displaystyle{ n+1}\) - parzystych i\(\displaystyle{ k}\)- nieparzystych.

Uprośćmy to, najpierw dla nieparzystych.: \(\displaystyle{ (n+1)}\)

\(\displaystyle{ R= \frac{n-2}{2}}\)

I wtedy:

\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)= \sum_{k=2}^{R} {R \choose k}=2^R}\)

teraz weźmy dla parzystych.: \(\displaystyle{ n+1}\)

\(\displaystyle{ r= \frac{n-1}{2}}\)

I wtedy biorąc pod uwagę powyższe rozumowania:

\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)= {r \choose 0}+ {r \choose 2}+...}\) ta suma też zawsze jest parzysta, na dole same parzyste...

Więc reasumując zapiszmy zgodnie z tym co wymyśliłem indukcyjnie:

Z:

\(\displaystyle{ a(n)=a(n-1)+b(n)+1}\)

T:

\(\displaystyle{ a(n+1)=a(n)+b(n+1)+1}\)

Dw:

\(\displaystyle{ b(n+1)=b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)}\)

lub:

(*) \(\displaystyle{ a(n+1)=a(n)+b(n)+ \sum_{k=2}^{n+1}b(1,k,n+1)+1}\)

Dla:\(\displaystyle{ n=1,2,3...}\) - łatwo sprawdzić, że:

\(\displaystyle{ a(1), a(2), a(3),...}\) - są nieparzyste, jak również nieparzyste są:\(\displaystyle{ b(1),b(2), b(3)}\)


czyli z założenia indukcyjnego w wyrażeniu (*) , nieparzyste są:

\(\displaystyle{ a(n), b(n), 1}\)

natomiast parzysta jest:

\(\displaystyle{ \sum_{k=2}^{n+1}b(1,k,n+1)}\)

co wykazaliśmy wyżej, zatem całe \(\displaystyle{ a(n+1)}\) jest nieparzyste

cnd...


A przy okazji wyprowadziłem wzór na ilość zbiorów koszernych=symetrycznych...

[Kaf]

Niech \(\displaystyle{ X}\) będzie rodziną wszystkich zbiorów koszernych.

Ja bym rozważył funkcję \(\displaystyle{ f\colon X \to X}\) daną wzorem \(\displaystyle{ f\left( A\right) =\left\{ n-a \colon a \in A\right\}}\) i policzył ile ona ma punktów stałych.

[arek1357]

I co dalej?

[Kaf]

\(\displaystyle{ f}\) jest automorfizmem rzędu 2. Liczba jego punktów stałych ma więc taką samą parzystość jak \(\displaystyle{ \left| X\right|}\).

Mała poprawka: powinno być \(\displaystyle{ f\left( A\right) =\left\{ n+1-a \colon a \in A\right\}}\) (z oczywistych względów).

[arek1357]

Generalnie to\(\displaystyle{ f}\) według mnie jest pewną permutacją zbiorów koszernych na na siebie.
No więc jakie to zbiory będą stanowiły elementy stałe tego przekształcenia.Bo coś dalej tego nie widzę...

Sprawdzałem pobieżnie i \(\displaystyle{ f}\) przekształca zbiór koszerny w zbiór koszerny...
Bo to wymaga małego uzasadnienia...

[Kaf]

Tak, \(\displaystyle{ f}\) jest permutacją \(\displaystyle{ X}\) na siebie i \(\displaystyle{ f \circ f= \mbox{id}}\). Jest to nic innego niż symetria względem punktu \(\displaystyle{ \frac{n+1}{2}}\) na prostej rzeczywistej (tylko że przekształcamy całe zbiory a nie punkty). Przy takiej interpretacji łatwo zliczyć punkty stałe.

[arek1357]

Czyli zbiór tych wszystkich permutacji będzie typu:

\(\displaystyle{ (x)...(xy).....}\) , na zbiorze, którego elementy są zbiorami koszernymi, jest ich \(\displaystyle{ a(n)}\)

jak wyliczyłem.
Teraz ile jest w tym cykli jednoelementowych czyli stałych...

[Kaf]

Nie całkiem rozumiem o co Ci chodzi Arku.

Moja idea jest taka: definiujemy \(\displaystyle{ f}\) jak wyżej, pokazujemy że \(\displaystyle{ f}\) jest permutacją \(\displaystyle{ X}\) na siebie i \(\displaystyle{ f \circ f= \mbox{id}}\). Zliczamy punkty stałe funkcji \(\displaystyle{ f}\) (skoro \(\displaystyle{ f}\) jest w pewnym sensie symetrią środkową, to takie punkty idzie prosto zliczyć - punkty stały są postaci \(\displaystyle{ A \cup f\left( A\right)}\), gdzie \(\displaystyle{ A \subset \{ 1,..., n \} \cap \left[ 1, \frac{n+1}{2}\right]}\)) i korzystamy z faktu, że \(\displaystyle{ f}\) jest inwolucją, więc liczba jej punktów stałych ma więc taką samą parzystość jak \(\displaystyle{ \left| X\right|}\) (a o parzystości tej ostatniej liczby chcemy rozstrzygać).

[arek1357]

No tak teraz już to wszystko widzę dokładnie, punkty stałe to takie, które są środkowosymetryczne,
a obrazem\(\displaystyle{ A}\) jest\(\displaystyle{ f(A)}\),(i też są środkowosymetryczne) (a Ty napisałeś wogóle o tym co wszystko jest stałe, nawet za dużo, ale ok...) .Teraz już bez liczenia wszystko zobaczyłem, pomysł fajny podoba mi się, lecz ja podchodząc do tego zadania, miałem za cel znaleźć wzór na ilość tych zbiorów koszernych, a dowód o ich nieparzystości był dla mnie uboczną i w sumie mało ważną rzeczą.
Bo reasumując zbiory są fajne, funkcję też znalazłeś fajną, fajny jest wzór na ich ilość , i naprawdę wszystko jest fajne, najmniej fajny jest tylko ten niby cel z tego zadania o udowodnieniu nieparzystości,
bo tak naprawdę najmniej mnie obchodziło czy one będą parzyste czy nieparzyste czy mieszane...