uniolympiads English

IMC 1999, Ημέρα 2, Θέμα 6

Let AA be a subset of Zn=Z/nZ\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z} containing at most 1100ln⁡n\frac{1}{100}\ln n elements. Define the rrth Fourier coefficient of AA for r∈Znr \in \mathbb{Z}_n by

f(r)=∑s∈Aexp⁡(2πinsr).f(r) = \sum_{s \in A} \exp\left(\frac{2\pi i}{n} sr\right).

Prove that there exists an r≠0r \ne 0, such that ∣f(r)∣≥∣A∣2|f(r)| \ge \frac{|A|}{2}.

Πρωτότυπο από το επίσημο PDF1 ln n elements. Define the rth Fourier coefficient 6. Let A be a subset of Z n = Z/nZ containing at most 100 of A for r ∈ Z n by X 2πi exp f (r) = sr . n s∈A Prove that there exists an r 6 = 0, such that f (r) ≥ |A| 2 . (20 points)

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

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

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

Επίσημη λύση

Solution. Let A={a1,…,ak}A=\{a_1,\dots,a_k\}. Consider the kk-tuples

(exp⁡2πia1tn,…,exp⁡2πiaktn)∈Ck,t=0,1,…,n−1.\left(\exp\frac{2\pi ia_1t}{n},\dots,\exp\frac{2\pi ia_kt}{n}\right)\in\mathbf{C}^k,\qquad t=0,1,\dots,n-1.
Each component is in the unit circle ∣z∣=1|z|=1. Split the circle into 6 equal arcs. This induces a decomposition of the kk-tuples into 6k6^k classes. By the condition k≤1100ln⁡nk\le\frac{1}{100}\ln n we have n>6kn>6^k, so there are two kk-tuples in the same class say for t1<t2t_1<t_2. Set r=t2−t1r=t_2-t_1. Then
Re⁡exp⁡2πiajrn=cos⁡(2πajt2n−2πajt1n)≥cos⁡π3=12\operatorname{Re}\exp\frac{2\pi ia_jr}{n}=\cos\left(\frac{2\pi a_jt_2}{n}-\frac{2\pi a_jt_1}{n}\right)\ge\cos\frac\pi3=\frac12
for all jj, so
∣f(r)∣≥Re f(r)≥k2.|f(r)|\ge\text{Re }f(r)\ge\frac k2.

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

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

Πώς πήγε;