uniolympiads English

IMC 2012, Ημέρα 2, Θέμα 5

Let c≥1c \ge 1 be a real number. Let GG be an abelian group and let A⊂GA \subset G be a finite set satisfying ∣A+A∣≤c∣A∣|A + A| \le c|A|, where X+Y:={x+y∣x∈X, y∈Y}X + Y := \{x + y \mid x \in X,\ y \in Y\} and ∣Z∣|Z| denotes the cardinality of ZZ. Prove that

∣A+A+⋯+A⏟k times∣≤ck∣A∣|\underbrace{A + A + \dots + A}_{k \text{ times}}| \le c^k|A|

for every positive integer kk.

Πρωτότυπο από το επίσημο PDFLet 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 | A {z . . . + A } | ≤ c |A| | + A + k times for every positive integer k.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(Proposed by Przemyslaw Mazur, Jagiellonian University)

Solution. Let BB be a nonempty subset of AA for which the value of the expression c1=∣A+B∣∣B∣c_1=\frac{|A+B|}{|B|} is the least possible. Note that c1≤cc_1\le c since AA is one of the possible choices of BB.

Lemma 1. For any finite set D⊂GD\subset G we have ∣A+B+D∣≤c1∣B+D∣|A+B+D|\le c_1|B+D|.

Proof. Apply induction on the cardinality of DD. For ∣D∣=1|D|=1 the Lemma is true by the definition of c1c_1. Suppose it is true for some DD and let x∉Dx\notin D. Let B1={y∈B∣x+y∈B+D}B_1=\{y\in B\mid x+y\in B+D\}. Then B+(D∪{x})B+(D\cup\{x\}) decomposes into the union of two disjoint sets:

B+(D∪{x})=(B+D)∪((B∖B1)+{x})B+(D\cup\{x\})=(B+D)\cup\big((B\setminus B_1)+\{x\}\big)
and therefore ∣B+(D∪{x})∣=∣B+D∣+∣B∣−∣B1∣|B+(D\cup\{x\})|=|B+D|+|B|-|B_1|. Now we need to deal with the cardinality of the set A+B+(D∪{x})A+B+(D\cup\{x\}). Writing A+B+(D∪{x})=(A+B+D)∪(A+B+{x})A+B+(D\cup\{x\})=(A+B+D)\cup(A+B+\{x\}) we count some of the elements twice: for example if y∈B1y\in B_1, then A+{y}+{x}⊂(A+B+D)∩(A+B+{x})A+\{y\}+\{x\}\subset(A+B+D)\cap(A+B+\{x\}). Therefore all the elements of the set A+B1+{x}A+B_1+\{x\} are counted twice and thus
∣A+B+(D∪{x})∣≤∣A+B+D∣+∣A+B+{x}∣−∣A+B1+{x}∣==∣A+B+D∣+∣A+B∣−∣A+B1∣≤c1(∣B+D∣−∣B∣−∣B1∣)=c1∣B+(D∪{x})∣,\begin{aligned} |A+B+(D\cup\{x\})|&\le|A+B+D|+|A+B+\{x\}|-|A+B_1+\{x\}|=\\ &=|A+B+D|+|A+B|-|A+B_1|\le c_1(|B+D|-|B|-|B_1|)=c_1|B+(D\cup\{x\})|, \end{aligned}
where the last inequality follows from the inductive hypothesis and the observation that ∣A+B∣∣B∣=c1≤∣A+B1∣∣B1∣\frac{|A+B|}{|B|}=c_1\le\frac{|A+B_1|}{|B_1|} (or B1B_1 is the empty set). □\square

Lemma 2. For every k≥1k\ge 1 we have ∣A+…+A⏟k times+B∣≤c1k∣B∣|\underbrace{A+\ldots+A}_{k\text{ times}}+B|\le c_1^k|B|.

Proof. Induction on k. For k=1k=1 the statement is true by definition of c1c_1. For greater kk set D=A+…+A⏟k−1 timesD=\underbrace{A+\ldots+A}_{k-1\text{ times}} in the previous lemma: ∣A+…+A⏟k times+B∣≤c1∣A+…+A⏟k−1 times+B∣≤c1k∣B∣|\underbrace{A+\ldots+A}_{k\text{ times}}+B|\le c_1|\underbrace{A+\ldots+A}_{k-1\text{ times}}+B|\le c_1^k|B|. □\square

Now notice that

∣A+…+A⏟k times∣≤∣A+…+A⏟k times+B∣≤c1k∣B∣≤ck∣A∣.|\underbrace{A+\ldots+A}_{k\text{ times}}|\le|\underbrace{A+\ldots+A}_{k\text{ times}}+B|\le c_1^k|B|\le c^k|A|.

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. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;