Matematyka dyskretna, zadanie nr 1573
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
wojtolino postów: 1 | 2013-10-11 11:44:24 Witam! Proszę o jakieś wskazówki w poniższym zadaniu. Mamy zbiór $A \subseteq \mathbb{Z}$ taki, że $\left| A+A\right|=2\left| A\right|-1$ (gdzie $A+A=\left\{ a_{1}+a_{2},\quad a_{1},a_{2}\in A\right\}$). Trzeba pokazać, że elementy $A$ tworzą ciąg arytmetycznym. Jasne jest, że pewne elementy w zbiorze sum muszą się powtarzać (bo inaczej $\left| A\right| =\frac{1}{2}n(n+1)$). Wiemy też, że $\forall_{A}\quad 2\left| A\right| -1 \le \left| A+A\right| \le {\left| A\right|+1 \choose 2}$ (tw. z wykładu), ale nie mogę stąd nic wywnioskować. Z góry dziękuję za pomoc. |
tumor postów: 8070 | 2013-10-22 21:18:16 Weźmy liczby $a_1 <a_2<a_3<...<a_n$, gdzie $|A|=n$ i $A\subset Z$. Zauważmy, że mamy pewność istnienia 2n-1 różnych sum: $a_1+a_1<a_1+a_2<a_2+a_2<a_2+a_3<a_3+a_3<...<a_{n-1}+a_n<a_n+a_n$. Przypuśćmy teraz, że wyrazy $a_i$ nie tworzą ciągu arytmetycznego. Oznacza to, że istnieją wyrazy $a_k, a_{k+1}, a_{k+2}$ dla $1\le k <n-1$ takie, że zachodzi jeden z poniższych warunków: 1) $a_{k+2}-a_{k+1} > a_{k+1} - a_{k}$ 2) $ a_{k+2}-a_{k+1} < a_{k+1} - a_{k}$ czyli, mówiąc po polsku, że dwie sąsiednie różnice kolejnych elementów nie są równe. Ad.1) Po przerzuceniu mamy $a_{k+2}+a_k>2a_{k+1}$ Zarazem jednak $a_{k+2}+a_{k+1}>a_{k+2}+a_k$. Oznacza to, że suma $a_{k+2}+a_k$ nie została wymieniona w ciągu sum powyżej, czyli sum jest co najmniej $2n$. Ad.2) Analogicznie, zostawiam państwu jako ćwiczenie do domu. ----- Zasadniczo nie trzeba pokazywać w zadaniu, że dla elementów będących wyrazami ciągu arytmetycznego rzeczywiście mamy $|A+A|=2|A|-1$. |
strony: 1 |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj