IMC 2013/2/5

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

Eukleidis
Δημοσιεύσεις: 669
Εγγραφή: Τετ Ιούλ 01, 2009 9:55 pm
Τοποθεσία: Θεσσαλονίκη

IMC 2013/2/5

#1

Μη αναγνωσμένη δημοσίευση από Eukleidis » Παρ Αύγ 09, 2013 4:54 pm

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

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


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

Re: IMC 2013/2/5

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Αύγ 21, 2013 11:27 am

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

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

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

Έστω a_n ο αριθμός των τρόπων. Είναι απλό ότι a_k = 2^k για 1 \leqslant k \leqslant 20 και a_{21} = 2^{21} - 1. Για n \geqlant 22, αν η n-οστή χάντρα είναι πράσινη, έχω 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}}

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

Επειδή 2013 = 3 \times 11 \times 61 η G αποτελείται από ένα ταυτοτικό στοιχείο, 2 περιστροφές τάξης 3, 10 τάξης 11, 60 τάξης 61, 20 = (3-1)(11-1) τάξης 33, 120 τάξης 183, 600 τάξης 671, 1200 τάξης 2013, και 2013 ανακλάσεις. Αν γράψουμε 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}

Τέλος για τα σταθερά σημεία των ανακλάσεων μπορούμε να θεωρήσουμε την ανάκλαση/στρίψιμο που κρατά την χάντρα 1 σταθερή και εναλλάσσει την χάντρα r+1 με την χάντρα 2014-r. Για τα σταθερά σημεία οι χάντρες που εναλλάσσονται έχουν το ίδιο χρώμα άρα ουσιαστικά μας ενδιαφέρει να χρωματίσουμε τις χάντρες από το 1 μέχρι το 1007 με τέτοιο τρόπο ώστε:
(α) Κάθε 21 συνεχόμενες χάντρες τουλάχιστον μία είναι πράσινη
(β) Από τις πρώτες 11 χάντρες τουλάχιστον μία είναι πράσινη (αλλιώς με τις συμμετρικές θα έχουμε 21 συνεχόμενες άσπρες)
(γ) Από τις τελευταίες 11 χάντρες τουλάχιστον μία είναι πράσινη (αλλιώς με τις συμμετρικές θα έχουμε 22 συνεχόμενες άσπρες)

Αν λοιπόν k η πρώτη πράσινη και 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.

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


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

Re: IMC 2013/2/5

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Αύγ 26, 2013 4:18 pm

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


Απάντηση

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

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

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