Zadanie konkursowe zawodów stopnia pierwszego:
4. Dana jest liczba naturalna k. Dowieść, że z każdego zbioru liczb całkowitych, mającego więcej niż [;3^k;] elementów, można wybrać (k+1)-elementowy podzbiór S o następujacej własności:
Dla dowolnych dwóch różnych podzbiorów A B zbioru S suma wszystkich elementów zbioru A jest różna od sumy wszystkich elementów zbioru B. (Przyjmujemy, że suma elementów zbioru pustego wynosi 0).
ROZWIĄZANIE
Niech [; X_0\ X_1\ X_2\ \ldots;] będzie dowolnym ciągiem zbiorów liczb całkowitych, takich że ich moce przewyższają kolejne potęgi liczby 3:
[;\bullet\quad\quad \forall_{\ j = 0\ 1\ \ldots}\quad|X_j| > 3^j ;]
Niech [;S_{-1};] będzie dowolnym 1-elementowym zbiorem liczb całkowitych, którego elementem nie jest 0. Zbiór [;S_{-1};] ma własność zbioru S z zadania. Załóżmy, że zdefiniowaliśmy już zbiór j-elementowy [;S_{j-1};], który ma własność zbioru S z zadania, dla pewnej nieujemnej liczby całkowitej [;j;]. Liczba wszystkich ciągów (t.j. funkcji)
[;\bullet\quad\quad\quad e : S_{j-1} \rightarrow \{-1\ \ 0\ \ 1\} ;]
wynosi [;3^j;]. Więc liczb (kombinacji liniowych) postaci:
[;\bullet\quad\quad\quad \sum_{s\in S_{j-1}}\ e(s)\cdot s ;]
jest nie więcej niż [;3^j;]. Istnieje zatem element zbioru [;X_j;], który nie jest powyższej postaci. Zdefiniujmy zbiór [;S_j;] jako [;S_{j-1};], powiększone o ten jeden element, tak, że moc nowego zbioru jest równa j+1. Jest jasnym, że nowy zbiór ma własność zbioru S z zadania. Zakończyliśmy tym indukcyjną definicję rosnącego (w sensie inkluzji) ciągu (j+1)-elementowych zbiorów [;S_j;], dla [;j=-1\ 0\ 1\ \ldots;], mających własność zbioru S z zadania; przy tym
[;\bullet\quad\quad\quad \forall_{\ j=0\ 1\ \ldots}\ S_j\, \backslash\, S_{j-1} \subseteq X_j ;]
Dodatkowo, dla dowolnego zbioru [;X;] liczb całkowitych, z tekstu zadania [;(|X| > 3^k);], możemy wybrać ciąg [;X_0\ X_1\ \ldots;] tak, żeby:
- [; X_k = X;]
- [;\forall_{\ j\ =\ 1\ 2\ \ldots}\ X_{j-1}\subseteq X_j ;]
Wtedy S := [;S_k;] jest rozwiązaniem zadania.
Twierdzenie z zadania zachodzi nie tylko dla (grupy addytywnej) liczb całkowitych, lecz także dla dowolnej grupy abelowej. W przypadku szczególnym, gdy każdy niezerowy element grupy jest rzędu 2, wystarczy założyć, że moc zbioru X przewyższa [;2^k;].
No comments:
Post a Comment