uniolympiads English

IMC 2018, Ημέρα 1, Θέμα 5

Let pp and qq be prime numbers with p<qp < q. Suppose that in a convex polygon P1P2…PpqP_1P_2 \dots P_{pq} all angles are equal and the side lengths are distinct positive integers. Prove that

P1P2+P2P3+⋯+PkPk+1≥k3+k2P_1P_2 + P_2P_3 + \dots + P_kP_{k+1} \ge \frac{k^3 + k}{2}

holds for every integer kk with 1≤k≤p1 \le k \le p.

Πρωτότυπο από το επίσημο PDFLet p and q be prime numbers with p < q . Suppose that in a convex polygon P 1 P 2 . . . P pq all angles are equal and the side lengths are distinct positive integers. Prove that Problem 5. P 1 P 2 + P 2 P 3 + · · · + P k P k+1 ≥ holds for every integer k with 1 ≤ k ≤ p . k 3 + k 2

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

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

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

Επίσημη λύση

(Proposed by Ander Lamaison Vidarte, Berlin Mathematical School, Berlin)

Solution. Place the polygon in the complex plane counterclockwise, so that P2−P1P_2 - P_1 is a positive real number. Let ai=∣Pi+2−Pi+1∣a_i = |P_{i+2} - P_{i+1}|, which is an integer, and define the polynomial f(x)=apq−1xpq−1+⋯+a1x+a0f(x) = a_{pq-1}x^{pq-1} + \dots + a_1x + a_0. Let ω=e2πipq\omega = e^{\frac{2\pi i}{pq}}; then Pi+1−Pi=ai−1ωi−1P_{i+1} - P_i = a_{i-1}\omega^{i-1}, so f(ω)=0f(\omega) = 0.

The minimal polynomial of ω\omega over Q[x]\mathbb{Q}[x] is the cyclotomic polynomial Φpq(x)=(xpq−1)(x−1)(xp−1)(xq−1)\Phi_{pq}(x) = \frac{(x^{pq}-1)(x-1)}{(x^p-1)(x^q-1)}, so Φpq(x)\Phi_{pq}(x) divides f(x)f(x). At the same time, Φpq(x)\Phi_{pq}(x) is the greatest common divisor of s(x)=xpq−1xp−1=Φq(xp)s(x) = \frac{x^{pq}-1}{x^p-1} = \Phi_q(x^p) and t(x)=xpq−1xq−1=Φp(xq)t(x) = \frac{x^{pq}-1}{x^q-1} = \Phi_p(x^q), so by Bézout's identity (for real polynomials), we can write f(x)=s(x)u(x)+t(x)v(x)f(x) = s(x)u(x) + t(x)v(x), with some polynomials u(x),v(x)u(x), v(x). These polynomials can be replaced by u∗(x)=u(x)+w(x)xp−1x−1u^*(x) = u(x) + w(x)\frac{x^p-1}{x-1} and v∗(x)=v(x)−w(x)xq−1x−1v^*(x) = v(x) - w(x)\frac{x^q-1}{x-1}, so without loss of generality we may assume that deg⁡u≤p−1\deg u \le p-1. Since deg⁡a=pq−1\deg a = pq-1, this forces deg⁡v≤q−1\deg v \le q-1.

Let u(x)=up−1xp−1+⋯+u1x+u0u(x) = u_{p-1}x^{p-1} + \dots + u_1x + u_0 and v(x)=vq−1xq−1+⋯+v1x+v0v(x) = v_{q-1}x^{q-1} + \dots + v_1x + v_0. Denote by (i,j)(i,j) the unique integer n∈{0,1,…,pq−1}n \in \{0,1,\dots,pq-1\} with n≡i(modp)n \equiv i \pmod{p} and n≡j(modq)n \equiv j \pmod{q}. By the choice of ss and tt, we have a(i,j)=ui+vja_{(i,j)} = u_i + v_j. Then

P1P2+⋯+PkPk+1=∑i=0k−1a(i,i)=∑i=0k−1ui+vi=1k∑i=0k−1∑j=0k−1(ui+vj)=1k∑i=0k−1∑j=0k−1a(i,j)≥(∗)1k(1+2+⋯+k2)=k3+k2\begin{aligned} P_1P_2 + \dots + P_kP_{k+1} &= \sum_{i=0}^{k-1}a_{(i,i)} = \sum_{i=0}^{k-1}u_i + v_i = \frac{1}{k}\sum_{i=0}^{k-1}\sum_{j=0}^{k-1}(u_i + v_j) \\ &= \frac{1}{k}\sum_{i=0}^{k-1}\sum_{j=0}^{k-1}a_{(i,j)} \overset{(*)}{\ge} \frac{1}{k}\left(1 + 2 + \dots + k^2\right) = \frac{k^3+k}{2} \end{aligned}
where (∗)(*) uses the fact that the numbers (i,j)(i,j) are pairwise different.

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

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

Πώς πήγε;