MIPT 2013/2/5

Mikesar · #1

Δίνονται δύο διαφορετικές ακολουθίες με

και

μήκους

. Δείξτε ότι υπάρχουν φυσικοί αριθμοί $m\leq5\sqrt{n}$ και

τέτοιοι ώστε οι ακολουθίες να διαφέρουν στο πλήθος των άσσων που υπάρχουν στις θέσεις που οι αριθμοί τους είναι ισοϋπόλοιποι με $a\ (mod \ m)$ .

#2

Για $n \leqslant 25$ είναι $n \leqslant 5\sqrt{n}$ και το ζητούμενο είναι προφανές παίρνοντας m=n

και

οποιαδήποτε θέση στην οποία διαφέρουν οι ακολουθίες. Μπορούμε λοιπόν να υποθέσουμε ότι $n \geqslant 26$ .

Έστω

το σύνολο των θέσεων όπου η πρώτη ακολουθία έχει άσσους, και

το σύνολο των θέσεων όπου η δεύτερη ακολουθία έχει άσσους. Ορίζουμε

$\displaystyle{ f(x) = \sum_{r \in A} x^r - \sum_{s \in B} x^s}$

Από τα δεδομένα, το f(x)

είναι μη μηδενικό πολυώνυμο βαθμού το πολύ

. Επίσης, για κάθε $t \leqslant 5\sqrt{n}$ , αν θέσουμε $\omega_t = e^{2\pi i/t}$ έχουμε $f(\omega_t^k) = 0$ για κάθε

αφού κάθε $r \in A$ με $r \equiv a \bmod t$ συνεισφέρει $\omega_t^{ak}$ στο f(x)

, και κάθε $s \in B$ με $s \equiv a \bmod t$ συνεισφέρει $-\omega_t^{ak}$ στο f(x)

.

Άρα x^t-1|f(x)

για κάθε $t \leqslant 5\sqrt{n}$ .

Θέτω $k = \lfloor \sqrt{n} \rfloor, m = 5k$ , και $T = \{k+1,\ldots,5k\}$ . Για $t_1,t_2 \in T$ έχουμε $\gcd(t_1,t_2) \leqslant 4$ οπότε $\gcd(x^{t_1}-1,x^{t_2}-1) \in \{x-1,x^2-1,x^3-1,x^4-1\}$ .

Επίσης:

Για κάθε $t \in T$ , όλα τα πολυώνυμα x^t-1

είναι πολλαπλάσια του x-1

.
Υπάρχουν ακριβώς

ακέραιοι $t \in T$ , ώστε το πολυώνυμο x^t-1

να είναι πολλαπλάσιο του x^2-1

.
Υπάρχουν το πολύ $\frac{4k+2}{3}$ ακέραιοι $t \in T$ , ώστε το πολυώνυμο x^t-1

να είναι πολλαπλάσιο του x^3-1

.
Υπάρχουν ακριβώς

ακέραιοι $t \in T$ , ώστε το πολυώνυμο x^t-1

να είναι πολλαπλάσιο του x^4-1

.

Άρα το $\displaystyle{ g(x) = \prod_{t \in T} (x^t-1)}$ διαιρεί το πολυώνυμο $\displaystyle{h(x) = f(x)(x-1)^{4k}(x+1)^{2k}(x^2+x+1)^{(4k+2)/3}(x^2+1)^k}$

Από την μία ο βαθμός του h(x)

είναι το πολύ $\displaystyle{ n + 32k/3 + 4/3.}$

Από την άλλη όμως, ο βαθμός του g(x)

είναι τουλάχιστον

$\displaystyle{ (k+1) + \cdots + 5k = \frac{(6k+1)(4k)}{2} = 12k^2+2k > n-1 + 11k^2 + 2k \geqslant n + 32k/3 + 4/3}$

αφού η τελευταία σχέση είναι ισοδύναμη με $33k^2 -26k + 7 \geqslant 0$ που ισχύει αφού $k = \lfloor \sqrt{n} \rfloor \geqslant 5$ .

Αυτό όμως είναι άτοπο οπότε η απόδειξη ολοκληρώθηκε.

MIPT 2013/2/5

MIPT 2013/2/5

Re: MIPT 2013/2/5

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