IMC 2013/2/5

Eukleidis · #1

Θεωρούμε ένα κυκλικό βραχιόλι με $\displaystyle{2013}$ χάντρες. Κάθε χάντρα μπορεί να βαφεί άσπρη ή πράσινη. Ένα βάψιμο του βραχιολιού καλείται καλό αν ανάμεσα σε οποιεσδήποτε $\displaystyle{21}$ διαδοχικές χάντρες υπάρχει τουλάχιστον μία πράσινη. Αποδείξτε ότι ο αριθμός των καλών βαψιμάτων του βραχιολιού είναι περιττός.

( Δύο βαψίματα που διαφέρουν σε κάποιες χάντρες, αλλά μπορούν να αποκτηθούν από περιστροφή ή από στρίψιμο του βραχιολιού, θεωρούνται διαφορετικά βαψίματα )

#2

Είχα διαβάσει λάθος την άσκηση και θεωρούσα δυο βαψίματα που διαφέρουν μόνο κατά μία περιστροφή ή στρίψιμο ως ίδια και όχι ως διαφορετικά όπως έλεγε η άσκηση. Ο αριθμός και αυτών βγαίνει περιττός (αν έχω κάνει σωστά τις πράξεις).

Βάζω μια απόδειξη αυτού. Ενδιάμεσα θα αποδείξω και το ζητούμενο της άσκησης.

Πρώτα όμως ξεκινώ από παρόμοιο πρόβλημα στην ευθεία: Έστω ότι έχω

χάντρες σε ευθεία τις οποίες βάφω άσπρες ή πράσινες με τέτοιο τρόπο ώστε σε κάθε 21 διαδοχικές χάντρες να υπάρχει τουλάχιστον μία πράσινη. Με πόσους τρόπους μπορεί να συμβεί αυτό;

Έστω a_n

ο αριθμός των τρόπων. Είναι απλό ότι a_k = 2^k

για $1 \leqslant k \leqslant 20$ και $a_{21} = 2^{21} - 1$ . Για $n \geqlant 22$ , αν η

-οστή χάντρα είναι πράσινη, έχω $a_{n-1}$ τρόπους. Αν είναι άσπρη αλλά η n-1

είναι πράσινη, έχω $a_{n-2}$ τρόπους κ.ο.κ με την διαδικασία να σταματάει στο $a_{n-21}$ που εμφανίζεται αν οι χάντρες $n,n-1,\ldots,n-19$ είναι άσπρες και η n-20

πράσινη. Επομένως είναι $a_n = a_{n-1} + \cdots + a_{n-21}$ και μπορούμε αναδρομικά να υπολογίσουμε όλα τα a_n

.

Στην λύση του προβλήματος βέβαια δεν μας ενδιαφέρει ο αριθμός των χρωματισμών αλλά μόνο αν είναι άρτιος ή περιττός. Στο πιο πάνω πρόβλημα με τις χάντρες στην ευθεία αυτό που με ενδιαφέρει (θα φανεί μετά γιατί) είναι ο αριθμός $a_n \bmod 4$ . Επόμενό μου βήμα είναι να υπολογίσω λοιπόν αυτούς τους αριθμούς $\bmod 4$ . [Για το κανονικό πρόβλημα είναι αρκετό να δουλέψουμε $\bmod 2$ .]

Δεν είναι δύσκολο να ελεγχθεί ότι $\displaystyle{a_n \equiv \begin{cases} 0 \bmod 4 & n \not \equiv 0,1,21,22,43 \bmod 44 \\1 \bmod 4 & n \equiv 0,22,43 \bmod 44 \\ 2 \bmod 4 & n \equiv 1 \bmod 44 \\ 3 \bmod 4 & n \equiv 21 \bmod 44 \end{cases}}$

Έστω τώρα

το σύνολο των καλών χρωματισμών του περιδεραίου. Η ομάδα

των συμμετριών του περιδεραίου αποτελείται από 2013 περιστροφές και 2013 ανακλάσεις και δρα στο περιδέραιο ώστε δυο χρωματισμοί να θεωρούνται ίδιοι αν και μόνο αν ανήκουν στην ίδια τροχιά. Μας ενδιαφέρει λοιπόν ο αριθμός των τροχιών που από το λήμμα του Burnside ισούται με τον μέσο όρο σταθερών σημείων της δράσης της

στο

.

Επειδή $2013 = 3 \times 11 \times 61$ η

αποτελείται από ένα ταυτοτικό στοιχείο,

περιστροφές τάξης

,

τάξης

,

τάξης

,

τάξης

,

τάξης

,

τάξης

,

τάξης

, και

ανακλάσεις. Αν γράψουμε $b_1,b_3,\ldots,b_{2013},b$ για τον αριθμό των σταθερών τους σημείων αντίστοιχα τότε από το λήμμα του Burnside ο αριθμός των τροχιών ισούται με

$\displaystyle{ \frac{b_1 + 2b_3 + \cdots + 1200b_{2013} + 2013b}{4026}.}$

Θέλουμε να δείξουμε ότι αυτός είναι περιττός οπότε αρκεί να δείξουμε ότι $b_1 + 2b_3 + \cdots + 1200b_{2013} + 2013b \equiv 2 \bmod 4$ ή ισοδύναμα ότι $b_1 + 2b_3 + 2b_{11} + b \equiv 2 \bmod 4$ .

Πάμε λοιπόν.

Το b_1

είναι ακριβώς ο αριθμός των καλών χρωματισμών που ζητούσε η άσκηση. (Δυο χρωματισμοί είναι διαφορετικοί ακόμη και αν μπορούμε να πάρουμε τον ένα από τον άλλο με περιστροφή/στρίψιμο.) Τους μετράμε ως εξής:

Ας ονομάσουμε τις χάντρες $1,2,\ldots,2013$ με αυτήν την σειρά και έστω k+1

η πρώτη πράσινη χάντρα και $2013 - \ell$ η τελευταία πράσινη χάντρα. Τότε είναι $k,\ell \geqslant 0$ και επιπλέον $k+\ell \leqslant 20$ . Αν $k = \ell = 0$ έχουμε $a_{2011}$ καλούς χρωματισμούς αφού οι χάντρες 1,2013

είναι πράσινες και ο χρωματισμός των $2,\ldots,2012$ πρέπει να ικανοποιεί τις συνθήκες του προβλήματος στην ευθεία. Αν $k + \ell = 1$ αυτό μπορεί να συμβεί με δύο τρόπους με $a_{2010}$ καλούς χρωματισμούς ο κάθε ένας κ.τ.λ. Επομένως είναι

$\displaystyle{ b_1 = a_{2011} + 2a_{2010} + \cdots + 21a_{1991} \equiv a_{31} + \cdots + 21a_{11} \equiv 10a_{22} + 11a_{21} \equiv 3 \bmod 4.}$

Για το b_3

είναι ακριβώς το ίδιο πρόβλημα μόνο με περιδέραιο με 2013/3 = 671

χάντρες αφού για να είναι ένας χρωματισμός σταθερό σημείο μιας περιστροφής τάξης 3, πρέπει και αρκεί κάθε δυο χάντρες σε απόσταση 671

να έχουν ακριβώς το ίδιο χρώμα. Έχουμε λοιπόν

$\displaystyle{ b_3 = a_{669} + \cdots + 21a_{649} \equiv 10a_0 + 9a_1 + 11a_{43} \equiv 3 \bmod 4.}$

Ομοίως βρίσκουμε

$\displaystyle{ b_{11} = a_{181} + \cdots + 21a_{161} \equiv 6a_0 + 5a_1 + 7a_{43} \equiv 3 \bmod 4}$

Τέλος για τα σταθερά σημεία των ανακλάσεων μπορούμε να θεωρήσουμε την ανάκλαση/στρίψιμο που κρατά την χάντρα

σταθερή και εναλλάσσει την χάντρα r+1

με την χάντρα 2014-r

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

μέχρι το

με τέτοιο τρόπο ώστε:
(α) Κάθε 21 συνεχόμενες χάντρες τουλάχιστον μία είναι πράσινη
(β) Από τις πρώτες 11 χάντρες τουλάχιστον μία είναι πράσινη (αλλιώς με τις συμμετρικές θα έχουμε 21 συνεχόμενες άσπρες)
(γ) Από τις τελευταίες 11 χάντρες τουλάχιστον μία είναι πράσινη (αλλιώς με τις συμμετρικές θα έχουμε 22 συνεχόμενες άσπρες)

Αν λοιπόν

η πρώτη πράσινη και $1008 - \ell$ η τελευταία πράσινη τότε $1 \leqslant k,\ell \leqslant 11$ και οι υπόλοιπες $1007-k-\ell$ μπορούν να χρωματιστούν με $a_{1007-k-\ell}$ τρόπους. Έχουμε λοιπόν

$\displaystyle{ b = a_{1005} + 2a_{1004} + \cdots + 11a_{995} + 10a_{994} + \cdots + a_{985} \equiv 5a_{989} + 6a_{990} \equiv 5a_{21} + 6a_{22} \equiv 1 \bmod 4.}$

Βάζοντάς τα όλα μαζί βγάζουμε $b_1 + 2b_3 + 2b_{11}+b \equiv 0 \bmod 4$ .

---------------------
Χμ. Σπίτι έβγαλα περιττό, τώρα βγάζω άρτιο. Κάποια από τις δύο λύσεις μου είναι λάθος. Το σαβατοκύριακο που θα πάω σπίτι θα ψάξω να βρω την πρώτη μου λύση για να δω που διαφέρουν και θα κάνω αν χρειαστεί τις ανάλογες διορθώσεις. Η βασική ιδέα πάντως πιστεύω είναι σωστή αλλά κάπου στις πράξεις υπάρχει πρόβλημα.

#3

Demetres έγραψε: Χμ. Σπίτι έβγαλα περιττό, τώρα βγάζω άρτιο. Κάποια από τις δύο λύσεις μου είναι λάθος.

Τελικά λάθος ήταν η πρώτη μου λύση όπου για κάποιο ανεξήγητο λόγο πρόσθεσα 2011b

αντί

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

IMC 2013/2/5

IMC 2013/2/5

Re: IMC 2013/2/5

Re: IMC 2013/2/5

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