Matematyka dyskretna, zadanie nr 1573

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