IMC 2012/2/5

Συντονιστής: Demetres

socrates
Επιμελητής
Δημοσιεύσεις: 6157
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

IMC 2012/2/5

#1

Μη αναγνωσμένη δημοσίευση από socrates » Κυρ Ιούλ 29, 2012 7:21 pm

Έστω c \ge 1 ένας πραγματικός αριθμός.
Έστω επίσης G μια αβελιανή ομάδα και A \subset G ένα πεπερασμένο σύνολο τέτοιο ώστε |A+A| \le c|A|, όπου X+Y:= \{x+y| x \in X, y \in Y\}
και |Z| η πληθικότητα του συνόλου Z.
Να δείξετε ότι \displaystyle{|\underbrace{A+A+\dots+A}_k| \le c^k |A|} για κάθε θετικό ακέραιο k.


Θανάσης Κοντογεώργης
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8586
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2012/2/5

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιούλ 30, 2012 12:09 am

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


Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: IMC 2012/2/5

#3

Μη αναγνωσμένη δημοσίευση από Nick1990 » Πέμ Αύγ 02, 2012 11:51 am

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


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Paki
Δημοσιεύσεις: 1
Εγγραφή: Κυρ Σεπ 23, 2012 3:09 am

Re: IMC 2012/2/5

#4

Μη αναγνωσμένη δημοσίευση από Paki » Κυρ Σεπ 23, 2012 3:28 am

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


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8586
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2012/2/5

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Σεπ 23, 2012 7:58 pm

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

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

Επιλέγουμε ένα υποσύνολο B του A τέτοιο ώστε το \displaystyle{ \frac{|A+B|}{|B|}} να είναι το ελάχιστο δυνατό. Έστω |A+B| = K|B|. (Άρα K \leqslant c αφού |A+A| \leqslant c|A|.) Αρκεί να δείξουμε ότι για κάθε C ισχύει η ανισότητα \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|}

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

Για |C| = 1 είναι προφανές αφού |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|. Επίσης από την επιλογή του 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' το ζητούμενο έπεται.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης