IMC 2012/2/5

#1

Έστω $c \ge 1$ ένας πραγματικός αριθμός.
Έστω επίσης

μια αβελιανή ομάδα και $A \subset G$ ένα πεπερασμένο σύνολο τέτοιο ώστε $|A+A| \le c|A|$ , όπου $X+Y:= \{x+y| x \in X, y \in Y\}$
και |Z|

η πληθικότητα του συνόλου

.
Να δείξετε ότι $\displaystyle{|\underbrace{A+A+\dots+A}_k| \le c^k |A|}$ για κάθε θετικό ακέραιο

.

#2

Είναι ειδική περίπτωση της ανισότητας Plünnecke. Η απόδειξη βρίσκεται σίγουρα στο βιβλίο "Additive combinatorics" των Tao και Vu. Περισσότερα άλλη φορά αφού είμαι εξωτερικό και η σύνδεσή μου σέρνεται.

Nick1990 · #3

Demetres έγραψε:Είναι ειδική περίπτωση της ανισότητας Plünnecke. Η απόδειξη βρίσκεται σίγουρα στο βιβλίο "Additive combinatorics" των Tao και Vu. Περισσότερα άλλη φορά αφού είμαι εξωτερικό και η σύνδεσή μου σέρνεται.

Να σημειώσουμε ότι το πρόβλημα αυτό προτάθηκε από τον Przemyslaw Mazur που τα τελευταία χρόνια είχε σπάσει κάθε ρεκόρ στο συγκεκριμένο διαγωνισμό.

Paki · #4

Καλησπερα
κατι μου λεει πως ισως λυνεται με την μεθοδο της μαθηματικης επαγωγης....

#5

Αποδεικνύεται πράγματι με επαγωγή και αν κάποιος διαβάσει την απόδειξη δεν είναι «ιδιαίτερα δύσκολη». Όμως δεν είναι καθόλου απλό να την σκεφτεί κάποιος. Οι αρχικές αποδείξεις της ανισότητας Plünnecke (στην γενική της μορφή) ήταν πολύ πιο δύσκολες και μόλις πρόσφατα ο Γιώργος Πετρίδης έδωσε μια επαγωγική απόδειξη της ανισότητας. Την απόδειξη την εξηγεί ο Gowers στο ιστολόγιό του εδώ.

Βάζω μια δική μου σύνοψη εδώ για να την έχουμε.

Επιλέγουμε ένα υποσύνολο

του

τέτοιο ώστε το $\displaystyle{ \frac{|A+B|}{|B|}}$ να είναι το ελάχιστο δυνατό. Έστω |A+B| = K|B|

. (Άρα $K \leqslant c$ αφού $|A+A| \leqslant c|A|$ .) Αρκεί να δείξουμε ότι για κάθε

ισχύει η ανισότητα $\displaystyle{ |A+B+C| \leqslant K|B+C|}$

Πράγματι τότε επαγωγικά έχουμε

$\displaystyle{ |nA| \leqslant |B+nA| \leqslant K|B+ (n-1)A| \leqslant \cdots \leqslant K^{n-1}|B+A| \leqslant K^n|B| \leqslant c^n|B| \leqslant c^n|A|}$

Πάμε λοιπόν πίσω στον ισχυρισμό ότι για κάθε

ισχύει η ανισότητα $\displaystyle{ |A+B+C| \leqslant K|B+C|}$ τον οποίο θα αποδείξουμε με επαγωγή στο |C|

.

Για

είναι προφανές αφού |A+B+C| = |A+B| = K|B| = K|B+C|

. Έστω λοιπόν $|C| \geqslant 2$ και έστω $x \in C$ . Θέτουμε $C' = C \setminus \{x\}$ . Τότε

$\displaystyle{ A+B+C = (A+B+C') \cup [(A+B+\{x\}) \setminus (A + B' + \{x\})]}$

όπου $B' = \{b \in B: A+b+\{x\} \subseteq A+B+C\}$ .

Από την επαγωγική υπόθεση έχουμε $|A+B+C'| \leqslant K|B+C'|$ και $|A+B+\{x\}| \leqslant K|B|$ . Επίσης από την επιλογή του

έχουμε $|A+B'+\{x\}| = |A+B'| \geqslant K|B'|$ . Επομένως

$\displaystyle{ |A+B+C| \leqslant K(|B+C'| + |B| - |B'|)}$

Αρκεί λοιπόν να δείξουμε ότι $|B+C'| + |B| - |B'| \leqslant |B+C|$ . Όμως

$B+C = (B+C') \cup [(B+\{x\}) \setminus (B'' + \{x\})$

όπου $B'' = \{b \in B: b+x \in B+C\}$ . Άρα |B+C| = |B+C'| + |B| - |B''|

και επειδή προφανώς $B'' \subseteq B'$ το ζητούμενο έπεται.

IMC 2012/2/5

IMC 2012/2/5

Re: IMC 2012/2/5

Re: IMC 2012/2/5

Re: IMC 2012/2/5

Re: IMC 2012/2/5

Μέλη σε σύνδεση