uniolympiads English

IMC 2013, Ημέρα 2, Θέμα 4

Does there exist an infinite set MM consisting of positive integers such that for any a,b∈Ma, b \in M, with a<ba < b, the sum a+ba + b is square-free?

(A positive integer is called square-free if no perfect square greater than 11 divides it.)

Πρωτότυπο από το επίσημο PDFDoes there exist an infinite set M consisting of positive integers such that for any a, b ∈ M , with a < b, the sum a + b is square-free? (A positive integer is called square-free if no perfect square greater than 1 divides it.)

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

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

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

Επίσημη λύση

(Proposed by Fedor Petrov, St. Petersburg State University)

Solution. The answer is yes. We construct an infinite sequence 1=n1<2=n2<n3<…1 = n_1 < 2 = n_2 < n_3 < \ldots so that ni+njn_i + n_j is square-free for all i<ji < j. Suppose that we already have some numbers n1<…<nkn_1 < \ldots < n_k (k≥2)(k \ge 2), which satisfy this condition and find a suitable number nk+1n_{k+1} to be the next element of the sequence.

We will choose nk+1n_{k+1} of the form nk+1=1+Mxn_{k+1} = 1 + Mx, with M=((n1+…+nk+2k)!)2M = ((n_1 + \ldots + n_k + 2k)!)^2 and some positive integer xx. For i=1,2,…,ki = 1, 2, \ldots, k we have ni+nk+1=1+Mx+ni=(1+ni)min_i + n_{k+1} = 1 + Mx + n_i = (1+n_i)m_i, where mim_i and MM are co-prime, so any perfect square dividing 1+Mx+ni1 + Mx + n_i is co-prime with MM.

In order to find a suitable xx, take a large NN and consider the values x=1,2,…,Nx = 1, 2, \ldots, N. If a value 1≤x≤N1 \le x \le N is not suitable, this means that there is an index 1≤i≤k1 \le i \le k and some prime pp such that p2∣1+Mx+nip^2 | 1 + Mx + n_i. For p≤2kp \le 2k this is impossible because p∣Mp | M. Moreover, we also have p2≤1+Mx+ni<M(N+1)p^2 \le 1 + Mx + n_i < M(N+1), so 2k<p<M(N+1)2k < p < \sqrt{M(N+1)}.

For any fixed ii and pp, the values for xx for which p2∣1+Mx+nip^2 | 1 + Mx + n_i form an arithmetic progression with difference p2p^2. Therefore, there are at most Np2+1\dfrac{N}{p^2} + 1 such values. In total, the number of unsuitable values xx is less than

∑i=1k∑2k<p<M(N+1)(Np2+1)<k⋅(N∑p>2k1p2+∑p<M(N+1)1)<<kN∑p>2k(1p−1−1p)+kM(N+1)<N2+kM(N+1).\begin{aligned} \sum_{i=1}^k \sum_{2k<p<\sqrt{M(N+1)}} \left(\frac{N}{p^2} + 1\right) &< k\cdot\left(N\sum_{p>2k}\frac{1}{p^2} + \sum_{p<\sqrt{M(N+1)}} 1\right) < \\ &< kN\sum_{p>2k}\left(\frac{1}{p-1} - \frac{1}{p}\right) + k\sqrt{M(N+1)} < \frac{N}{2} + k\sqrt{M(N+1)}. \end{aligned}

If NN is big enough then this is less than NN, and there exist a suitable choice for xx.

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

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

Πώς πήγε;