Moc zbioru a jego struktura

[Wojtolino]

Witam!
Proszę o jakieś wskazówki w poniższym zadaniu.
Mamy zbiór \(\displaystyle{ A \subseteq \mathbb{Z}}\) taki, że \(\displaystyle{ \left| A+A\right|=2\left| A\right|-1}\) (gdzie \(\displaystyle{ A+A=\left\{ a_{1}+a_{2},\quad a_{1},a_{2}\in A\right\}}\)). Trzeba pokazać, że \(\displaystyle{ A}\) jest ciągiem arytmetycznym.
Jasne jest, że pewne elementy w zbiorze sum muszą się powtarzać (bo inaczej \(\displaystyle{ \left| A\right| =\frac{1}{2}n(n+1)}\)). Wiemy też, że \(\displaystyle{ \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.

[Naed Nitram]

Na potrzeby tego postu przyjmijmy, że ciąg arytmetyczny ma co najmniej jeden wyraz.

Wynikanie w drugą stronę, to znaczy jeśli \(\displaystyle{ A}\) jest "arytmetyczny", to \(\displaystyle{ |A+A|=2|A|-1}\) można otrzymać minimalnie modyfikując, więc pokażę obie rzeczy, czyli

(*)\(\displaystyle{ |A+A|=2|A|-1}\) wtedy i tylko wtedy, gdy \(\displaystyle{ A}\) jest "arytmetyczny"

Warto zauważyć, że w rozwiązaniu nie korzystamy z tego, że \(\displaystyle{ A\subseteq\mathbb Z}\), równie dobrze mógłby by to być podzbiór \(\displaystyle{ \mathbb R}\).

Niech \(\displaystyle{ A=\{a_1,...,a_{n+1}\}}\), przy czym \(\displaystyle{ a_i<a_{i+1}}\) tam gdzie to ma sens.

Przypuśćmy, że dla wszystkich zbiorów mocy mniejszej niż \(\displaystyle{ n+1}\), zachodzi (*).

Niech \(\displaystyle{ A'=\{a_1,...,a_n\}}\). Wówczas elementy \(\displaystyle{ 2a_{n+1}}\), \(\displaystyle{ a_{n+1}+a_n}\) należące do \(\displaystyle{ A+A}\) nie należą do \(\displaystyle{ A'+A'}\), bo są za duże. Skąd \(\displaystyle{ |A'+A'|\ge|A+A|}\) i mamy krok indukcyjny dla wynikania w prawo.

Dla wynikania w lewo (o co nas w oryginalnym zadaniu nie pytają) zauważmy, że jeśli \(\displaystyle{ A'}\) jest "arytmetyczny" zbiór \(\displaystyle{ A+A}\) zawiera dokładnie dwa elementy nie należące do \(\displaystyle{ A'+A'}\): Oba zbiory są "arytmetyczne" z tą samą różnicą, więc wystarczy porównać elementy najmniejsze i największe w zbiorach. Do \(\displaystyle{ A'+A'}\) należy \(\displaystyle{ \min (A+A)}\), zaś jedyne elementy \(\displaystyle{ A+A}\) większe niż \(\displaystyle{ \max (A'+A')}\) to \(\displaystyle{ 2a_{n+1}}\) oraz \(\displaystyle{ a_{n}+a_{n+1}}\).

Pozostają więc do sprawdzenia warunki początkowe dowodów indukcyjnych obu wynikań. Dla wynikania w lewo jest łatwo, \(\displaystyle{ A}\) jednoelementowy spełnia: \(\displaystyle{ 1=|A+A|=2|A|-1}\).

Warunek początkowy wynikania w prawo jest nieco bardziej uciążliwy, bo trzeba rozważyć ciągi o co najmniej trzech wyrazach. Wystarczy jednak wypisać wszystkie możliwości.

Albo rozważyć wszystkie możliwości za pomocą jednej wygodnej:    

Przyjąć, dla wygody, że to są \(\displaystyle{ 0,1,x>1}\). Wówczas elementami \(\displaystyle{ A+A}\) są liczby \(\displaystyle{ 0,1,2, x,1+x, 2x}\). Wszystkie różne, co łatwo sprawdzić. Teraz zauważamy, że \(\displaystyle{ |pA+q|=|A|}\) oraz, że \(\displaystyle{ |(pA+q)+(pA+q)|=|p(A+A)+2q|=|A+A|}\). Symbole samoobjaśniające się.

[Wojtolino]

Niech \(\displaystyle{ A'=\{a_1,...,a_n\}}\). Wówczas elementy \(\displaystyle{ 2a_{n+1}}\), \(\displaystyle{ a_{n+1}+a_n}\) należące do \(\displaystyle{ A+A}\) nie należą do \(\displaystyle{ A'+A'}\), bo są za duże. Skąd \(\displaystyle{ |A'+A'|\ge|A+A|}\) i mamy krok indukcyjny dla wynikania w prawo.

Tu jest coś źle. Skoro do \(\displaystyle{ A+A}\) należało coś więcej, niż do \(\displaystyle{ A'+A'}\), to \(\displaystyle{ |A'+A'|\le|A+A|}\), co tezy nie daje.
Mimo wszystko udało mi się znaleźć dowód samemu. Przyjąłem indukcyjnie, że mamy wszystkie założenia o \(\displaystyle{ A}\) spełnione, po czym dołożyłem do niego kolejny element (dołożyłem go z góry, mógłbym równoważnie też z dołu, a z przypadkiem gdzieś pomiędzy elementami \(\displaystyle{ A}\) trzeba pokombinować, żeby go wyrzucić). Zauważam, że w "nowej" sumie jest o dwa elementy więcej, niż w "starej", a w ich domniemanej różnicy (tzn. wypisuję elementy symbolami i jest ich bodajże n+1, a ma być 2) wszystkie elementy są różne (bo układamy je ściśle rosnąco), więc muszą być równe pewnym elementom z "nowej" sumy. Okazuje się, że kandydatów na porównanie jest tyle samo, co tych, których jest za dużo w tej naszej domniemanej różnicy, więc przyporządkowanie (ze względu na ułożenie rosnące) jest jednoznaczne i dostajemy tezę.

[Naed Nitram]

Miało być: \(\displaystyle{ |A+A|\ge |A'+A'|+2}\) przecież widać, że o to chodziło. Szczególnie, że te dwa elementy są wskazane i to dwukrotnie. A to, co napisałeś jest nieprecyzyjnym szkicem (połowy) mojego dość precyzyjnego dowodu, więc stwierdzenie "Mimo wszystko udało mi się znaleźć" wygląda dość komicznie.

[Wojtolino]

Oczywiście, że jest szkicem Ale jak się to zapisze, to jest sto razy bardziej strawialne jak dla mnie niż Twój dowód. Mimo wszystko dzięki za chęci i pomoc