IMC 2018/1/5

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2018/1/5

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Ιούλ 25, 2018 12:30 pm

Έστω πρώτοι αριθμοί p,q με p<q. Έστω κυρτό πολύγωνο P_1,P_2,…,P_{pq} με όλες τις γωνίες του ίσες και όλες τις πλευρές του να έχουν διακεκριμένα ακέραια μήκη. Να δειχθεί ότι

\displaystyle P_1P_2+P_2P_3+\cdots +P_kP_{k+1}\geqslant \frac{k^3+k}{2}

για κάθε 1\leqslant k\leqslant p.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2018/1/5

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Αύγ 12, 2018 10:43 pm

Γράφω a_i για το μήκος του P_{i-1}P_{i}. (0 \leqslant i \leqslant pq-1). Γράφω επίσης \omega = e^{2\pi i/q}.

Κάθε γωνιά του πολυγώνου ισούται με \displaystyle  \frac{(pq-2)\pi}{pq} οπότε οι εξωτερικές γωνιές ισούνται με \frac{2\pi}{pq}.

Επομένως έχουμε \displaystyle  a_0 + a_1\omega + a_2 \omega^2 + \cdots + a_{pq-1}\omega^{pq-1} = 0

Άρα το \omega είναι ρίζα του πολυωνύμου P(x) = a_0 + a_1x + \cdots + a_{pq-1}x^{pq-1}. Το ελάχιστο πολυώνυμο του \omega είναι το κυκλοτομικό πολυώνυμο \Phi_{pq}(x). Δηλαδή υπάρχει πολυώνυμο Q(x) ώστε P(x) = \Phi_{pq}(x)Q(x). Από το λήμμα του Gauss, το Q(x) έχει ακέραιους συντελεστές.

Έχουμε \displaystyle  \Phi_{pq}(x) = \frac{x^{pq}-1}{\Phi_1(x)\Phi_p(x)\Phi_q(x)} = \frac{x^{pq}-1}{(x^q-1)\Phi_p(x)}

Σε τυπικές δυναμοσειρές έχουμε

\displaystyle  \frac{P(x)}{1-x^{pq}} = P(x)(1+x^{pq} + x^{2pq} + \cdots) = \sum_{n=0}^{\infty}a_nx^n

όπου οι δείκτες είναι modulo pq.

Παίρνουμε λοιπόν ότι

\displaystyle  (1+x+x^2+\cdots + x^{p-1}) \sum_{n=0}^{\infty}a_nx^n = (1+x^q+x^{2q}+\cdots)Q(x)

Έχουμε δύο τυπικές δυναμοσειρές. Στην δεξιά οι συντελεστές, τουλάχιστον από ένα σημείο και μετά, επαναλαμβάνονται κάθε q όρους. Άρα το ίδιο συμβαίνει και στην αριστερή.

Δηλαδή για κάθε n θα έχουμε a_n + \cdots + a_{n+p-1} = a_{n+rq} + \cdots + a_{n+rq+p-1} για κάθε φυσικό r. (Αυτό συμβαίνει σίγουρα από κάποιο n και μετά, άρα και για όλα τα n λόγω περιοδικότητας.

Επειδή

a_n + \cdots + a_{n+p-1} = a_{n+rq} + \cdots + a_{n+rq+p-1}

και

a_{n+1} + \cdots + a_{n+p} = a_{n+rq+1} + \cdots + a_{n+rq+p}

αφαιρώντας παίρνουμε a_n - a_{n+p} = a_{n+rq} - a_{n+rq+p}. Επαγωγικά καταλήγουμε στο a_n - a_{n+sp} = a_{n+rq} - a_{n+rq+sp} για κάθε r,s.

Ισοδύναμα a_n + a_{n+rq+sp} = a_{n+rq} + a_{n+sp}. Γράφοντας m = n+rq+sp έχουμε a_n + a_m = a_u + a_v όπου u = n+rq = m - sp \equiv m \bmod p και u \equiv n \bmod q. Ομοίως v \equiv m \bmod q και v \equiv n \bmod p.

Για κάθε 1 \leqslant i < j \leqslant k παίρνουμε u= u(i,j),v = v(i,j) ώστε a_i + a_j = a_u + a_v όπως στην πιο πάνω παράγραφο. Όμως από κάθε ένα από τα u,v, τα i,j καθορίζονται πλήρως ακριβώς επειδή k \leqslant p < q. Άρα όλα τα u(i,j),v(i,j) είναι διαφορετικά ανά δύο. Μάλιστα είναι και διαφορετικά από τα a_1,\ldots,a_k.

Έχουμε τώρα

\displaystyle  k(a_1 + \cdots +a_k) = (a_1 + \cdots + a_k) + \sum_{1 \leqslant i < j \leqslant k} (a_i + a_j) = (a_1 + \cdots + a_k) + \sum_{1 \leqslant i < j \leqslant k} (a_{u(i,j)} + a_{v(i,j)})

Το τελευταίο είναι άθροισμα k + 2\binom{k}{2} διαφορετικών μεταξύ τους a_i. Οπότε είναι μεγαλύτερο ή ίσο από 1 + 2 + \cdots + k^2 = \frac{k^2(k^2+1)}{2}.

Το ζητούμενο έπεται.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης