Matematyka.pl

Dane są liczby naturalne \(\displaystyle{ a_1, ..., a_{2n}}\) ( \(\displaystyle{ n \geq 3}\)) nie większe niż \(\displaystyle{ 2n-1 }\) oraz \(\displaystyle{ a_1 +...+ a_{2n} =4n.}\) Udowodnić, że \(\displaystyle{ \sum_{j \in J} a_j =2n}\) dla jakiegoś \(\displaystyle{ J \subset \{ 1,..., 2n \}}\).

Jeżeli założymy sobie, że:

\(\displaystyle{ a_{1} \ge a_{2} \ge ... \ge a_{2n}}\)

Oraz, że:

\(\displaystyle{ a_{1}+a_{2}+...+a_{2n}=4n}\)

Można zauważyć, że chodzi tu o partycje:

\(\displaystyle{ P(4n,2n)}\)

Biorąc jeszcze pod uwagę, że:

\(\displaystyle{ a_{i}<2n}\)

łatwo wywnioskować , że tych partycji spełniających warunki zadania będzie:

\(\displaystyle{ P(4n,2n)-2}\)

A mamy udowodnić ,że w tym składzie istnieje jakaś partycja:

\(\displaystyle{ P(2n, k) , 1 \le k \le 2n}\)

Ładnie to idzie z rekurencji po \(\displaystyle{ n}\)

Np dla \(\displaystyle{ n=1}\) mamy zero możliwości

bo:

\(\displaystyle{ 3+1=4}\)

\(\displaystyle{ 2+2=4}\)

żadna nie spełnia warunków zadania...

dla \(\displaystyle{ n=2 }\) mamy:

\(\displaystyle{ P(8,4)}\) :

\(\displaystyle{ 3+3+1+1=8}\)

\(\displaystyle{ 3+2+2+1=8}\)

\(\displaystyle{ 2+2+2+2=8}\)

W każdym z tych układów istnieje jakaś tam partycja typu:

\(\displaystyle{ P(4,2)}\)

Co łatwo zauważyć...

Więc indukcyjnie po n łatwo wychodzi przy założeniu dla n, że zachodzi:

\(\displaystyle{ P(4n,2n)}\)

Powinno być (zachodzić):

\(\displaystyle{ P(4n+4,2n+2)}\)

Dlatego że ostatni układ na końcu może mieć:

\(\displaystyle{ 1,1,1,1}\)

\(\displaystyle{ 2,1,1}\)

lub:

\(\displaystyle{ 2,2}\)

W pierwszym i drugim przypadku dokładamy dwie jedynki na dwóch miejscach i otrzymujemy: \(\displaystyle{ P(4n+4,2n+2)}\)

W ostatnim przypadku układ będzie miał same dwójki w sumie więc sprawa oczywista...

cnd...