Let c≥1 be a real number. Let G be an abelian group and let A⊂G be a finite set satisfying ∣A+A∣≤c∣A∣, where X+Y:={x+y∣x∈X,y∈Y} and ∣Z∣ denotes the cardinality of Z. Prove that
∣k timesA+A+⋯+A∣≤ck∣A∣
for every positive integer k.
Πρωτότυπο από το επίσημο PDF
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Χρόνος σε αυτό το θέμα
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(Proposed by Przemyslaw Mazur, Jagiellonian University)
Solution. Let B be a nonempty subset of A for which the value of the expression c1=∣B∣∣A+B∣ is the least possible. Note that c1≤c since A is one of the possible choices of B.
Lemma 1. For any finite set D⊂G we have ∣A+B+D∣≤c1∣B+D∣.
Proof. Apply induction on the cardinality of D. For ∣D∣=1 the Lemma is true by the definition of c1. Suppose it is true for some D and let x∈/D. Let B1={y∈B∣x+y∈B+D}. Then B+(D∪{x}) decomposes into the union of two disjoint sets:
B+(D∪{x})=(B+D)∪((B∖B1)+{x})
and therefore ∣B+(D∪{x})∣=∣B+D∣+∣B∣−∣B1∣. Now we need to deal with the cardinality of the set A+B+(D∪{x}). Writing A+B+(D∪{x})=(A+B+D)∪(A+B+{x}) we count some of the elements twice: for example if y∈B1, then A+{y}+{x}⊂(A+B+D)∩(A+B+{x}). Therefore all the elements of the set A+B1+{x} are counted twice and thus
where the last inequality follows from the inductive hypothesis and the observation that ∣B∣∣A+B∣=c1≤∣B1∣∣A+B1∣ (or B1 is the empty set). □
Lemma 2. For every k≥1 we have ∣k timesA+…+A+B∣≤c1k∣B∣.
Proof. Induction on k. For k=1 the statement is true by definition of c1. For greater k set D=k−1 timesA+…+A in the previous lemma: ∣k timesA+…+A+B∣≤c1∣k−1 timesA+…+A+B∣≤c1k∣B∣. □
Remark. The proof above due to Giorgios Petridis and can be found at http://gowers.wordpress.com/2011/02/10/a-new-way-of-proving-sumset-estimates/
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.