Podział liczby naturalnej

[musialmi]

Niech \(\displaystyle{ f_{n}}\) oznacza ilość podziałów liczby naturalnej n, w których składniki parzyste się nie powtarzają, a \(\displaystyle{ g_{n}}\) oznacza ilość podziałów, w których żaden składnik nie jest podzielny przez 4. Pokaż, że \(\displaystyle{ f_{n}=g_{n}}\). (Kolejność występowania składników nie ma znaczenia).

Wg mnie to jest fałsz, proszę o wskazanie mojego błędu. Mamy liczbę 16, którą można podzielić na 5 sposobów:
\(\displaystyle{ 16=16=8 \cdot 2=4 \cdot 2 \cdot 2=2 \cdot 2 \cdot 2 \cdot 2=4 \cdot 4}\)

Podziały, w których składniki parzyste się nie powtarzają: \(\displaystyle{ 16, 8 \cdot 2}\) i są dwa takie podziały.
Podziały, w których żaden składnik nie jest podzielny przez 4: \(\displaystyle{ 2 \cdot 2 \cdot 2 \cdot 2}\) i jest jeden taki.

[Qń]

Ale w treści jest mowa o składnikach, nie czynnikach.

Q.

[musialmi]

No jasne! Co ja robię...
Proponuję takie rozwiązanie:
Każdy podział, w którym występuje składnik \(\displaystyle{ k}\) podzielny przez 4, można zamienić go na podział, w którym składniki parzyste się powtarzają. A w jaki sposób? Zapisując \(\displaystyle{ k}\) jako \(\displaystyle{ \frac{k}{2} + \frac{k}{2}}\) (\(\displaystyle{ k}\) jest podzielne przez 4, więc również przez 2, więc \(\displaystyle{ \frac{k}{2}}\) jest całkowite).
Natomiast każdy podział, w którym występują dwa takie same parzyste składniki \(\displaystyle{ t}\), można zamienić na podział, w którym będzie składnik podzielny przez 4. W jaki sposób? Otóż zapisując \(\displaystyle{ t+t}\) jako \(\displaystyle{ 2t}\) (\(\displaystyle{ t}\) jest parzyste, więc \(\displaystyle{ \frac{t}{2}}\) jest całkowite, więc \(\displaystyle{ \frac{t+t}{4}= \frac{2t}{4} = \frac{t}{2}}\) też jest całkowite).
Zasada ta działa dla każdych podziałów spełniających warunki, więc liczba tych podziałów jest równa.

Wykazałem to w prawidłowy sposób?

[Qń]

Musisz wskazać bijekcję między podziałami w których składniki parzyste się nie powtarzają a podziałami w których nie występuje składnik podzielny przez cztery. To co zrobiłeś w najmniejszym stopniu nie przypomina wskazania takiej bijekcji - dlaczego właściwie bierzesz na tapetę podziały w których występują składniki podzielne przez cztery?

Q.

[musialmi]

Rozważyłem takie, bo występowanie takich i takich podziałów działa na zasadach równoważności.
Obawiam się, że nie umiem rozwiązać tego problemu.

[Qń]

Rozważyłem takie, bo występowanie takich i takich podziałów działa na zasadach równoważności.

Nie rozumiem.

Co do zadania - wskazówka: w dowolnym podziale w którym składniki parzyste się nie powtarzają zastąpmy każdy składnik postaci \(\displaystyle{ 2^k(4l+2)}\) przez \(\displaystyle{ 2^k}\) składników postaci \(\displaystyle{ 4l+2}\). Trzeba pokazać tylko, że w nowym podziale nie występują składniki podzielne przez cztery (oczywiste) oraz że takie przypisanie jednemu podziałowi drugiego jest bijekcją.

Q.

[musialmi]

Dalej nie wiem jak to rozwiązać. I to ani trochę.

Rozważyłem takie, bo występowanie takich i takich podziałów działa na zasadach równoważności.

Nie rozumiem.

Każdy podział z parzystymi można zastąpić podziałem z czwórką. Każdy podział z czwórką można zastąpić podziałem z parzystymi. O tę relację równoważności mi chodziło. Podziałów z parzystymi jest \(\displaystyle{ a}\), podziałów z czwórką jest \(\displaystyle{ b}\). Pokazałem, że \(\displaystyle{ a=b}\). Wszystkich podziałów jest \(\displaystyle{ p}\). Podziałów bez powtórzonych składników parzystych jest \(\displaystyle{ p-a=f}\), natomiast podziałów bez składników podzielnych przez 4 jest \(\displaystyle{ p-b=g}\).
\(\displaystyle{ a=b \Rightarrow p-a=p-b \Rightarrow f=g}\)

[Qń]

A, próbujesz wskazać bijekcję pomiędzy dopełnieniami zbiorów żądanych podziałów. Tak też można, ale to co wskazałeś nie jest nawet funkcją: czy podziałowi \(\displaystyle{ 8+4}\) przypisujesz \(\displaystyle{ 4+4+4}\) czy \(\displaystyle{ 8+2+2}\); czy podziałowi \(\displaystyle{ 6+6+2+2}\) przypisujesz \(\displaystyle{ 12+2+2}\) czy \(\displaystyle{ 6+6+4}\)?

Jeśli chcesz wskazać bijekcję, to musisz pokazać jak jednemu podziałowi w którym występuje składnik podzielny przez cztery przypisujesz jednoznacznie dokładnie jeden podział w którym składniki parzyste się powtarzają, a następnie pokazać, że to przypisanie jest różnowartościowe i "na".

Branie na tapetę dopełnień zbiorów nie jest istotnym ułatwieniem problemu, choć idea będzie podobna do tej o której pisałem. Jeśli nie rozumiesz tej idei, to po pierwsze zauważ, że składniki nieparzyste możemy zupełnie pominąć (w moim przypisaniu one się nie zmieniają, więc są nieistotne), a po drugie przypatrz się jakiemuś prostemu przypadkowi, na przykład podziałom liczby \(\displaystyle{ 18}\).

Te w których składniki parzyste się nie powtarzają (ale wszystkie są parzyste) to:
\(\displaystyle{ 18=16+2=14+4=12+6=12+4+2=10+8=10+6+2=8+6+4}\)
Te w których nie występuje składnik podzielny przez \(\displaystyle{ 4}\) (ale składniki są parzyste) to:
\(\displaystyle{ 18=14+2+2=10+6+2=10+2+2+2+2=6+6+6=\\ =6+6+2+2+2=6+2+2+2+2+2+2=2+2+2+2+2+2+2+2+2}\)

A proponowana przeze mnie funkcja działa tak:
\(\displaystyle{ f(18)=18\\
f(16+2)=2+2+2+2+2+2+2+2+2\\
f(14+4)=14+2+2\\
f(12+6)=6+6+6\\
f(12+4+2)=6+6+2+2+2\\
f(10+8)=10+2+2+2+2\\
f(10+6+2)=10+6+2\\
f(8+6+4)=6+2+2+2+2+2+2}\)

Q.