Συνδυαστική

Mikesar · #1

Κάθε μοναδιαίο τετράγωνο ενός $2\times n$ πλέγματος βάφεται κόκκινο ή μπλε, με τέτοιο τρόπο ώστε να μην υπάρχει κανένα $2\times2$ κόκκινο τετράγωνο. Έστω c_n

το πλήθος αυτών των χρωματισμών. Να προσδιοριστεί, με απόδειξη, ο μέγιστος ακέραιος

που είναι τέτοιος ώστε ο 3^k

να διαιρεί τον $c_{2001}$

Tolis97 · #2

Για

υπάρχουν

τρόποι για να βαφτούν τα

τετραγωνάκια και μόνο ένας από αυτός δεν είναι επιτρεπτός(να είναι όλα κόκκινα), άρα c_2 = 2^4-1 = 15

. Όμοια βρίσκουμε πως c_3 = 65

. Η απόδειξη είναι εύκολη... τα 2 τελευταία τετραγωνάκια μπορούν να βαφτούν με

τρόπους άμα τα όλα τα από πάνω μπορούν να πάρουν ότι χρώμα θέλουν ( =3c_2=45

) ενώ άμα τα 2 τελευταία είναι και τα 2 κόκκινα τα 2 "από πάνω" μπορούν να βαφτούν με 2^3+2^3+2^2 = 20

τρόπους!

Τώρα γενικά έστω πως έχουμε ένα πλέγμα $2 \times n$ προσθέτοντας μια δυάδα κάτω παίρνουμε ένα πλέγμα $2 \times (n+1)$ . Άμα οι 2 τελευταίες γραμμές δεν είναι και οι δύο κόκκινες υπάρχουν 3c_n

τρόποι βαφής. Άμα και οι δύο κόκκινες πρέπει οι 2 προτελευταίες να μην είναι κ οι δύο κόκκινες, το οποίο γίνεται με $3c_{n-1}$ τρόπους! Άρα $c_{n+1} = 3(c_n+c_{n-1})$ .

Έστω k_i

η μεγαλύτερη δύναμη του

που διαιρεί το το c_i

τότε $k_{i+1} = min\{k_i, k_{i-1}\}+1 = k_{i-1} +1 \Rightarrow k_n = \left[ \dfrac{n}{2} \right] - 1 \Rightarrow \fbox{\displaystyle k = k_{2001} = 999}$ .

Επειδή είναι λίγο αργά και νυστάζω μπορεί να έχω κάνει κάποιο λάθος...

#3

Βρίσκω

και όχι

. [Βγαίνει και από τον τύπο $c_{n+1} = 3(c_n + c_{n-1})$ αφού c_1=4,c_2=15

.

Για τα k_n

θέλει περισσότερη προσοχή αφού αν $k_{n} = k_{n-1}$ τότε το μόνο που μπορούμε να πούμε για το $k_{n+1}$ χωρίς περισσότερες πληροφορίες είναι ότι $k_{n+1} \geqslant k_n + 1$ .

Θα δείξω με επαγωγή στο

ότι $k_{2n} \geqslant n$ και $k_{2n+1} = n$ . Για n=1

είναι απλό. Έστω ότι ισχύει για n=r

. Αφού $k_{2r} \geqslant r$ και $k_{2r+1} = r$ απαραίτητα πρέπει $k_{2(r+1)} = k_{2r+2} \geqslant r+1$ . Επίσης αφού $k_{2r+2} \geqslant r+1$ και $k_{2r+1} = r$ απαραίτητα πρέπει $k_{2(r+1)+1} = k_{2r+3} = r+1$ . Οπότε ο ισχυρισμός είναι αληθής.

Επομένως η μεγαλύτερη δύναμη του 3 που διαιρεί το $c_{2001}$ είναι η $k_{2001} = 1000$ .

Συνδυαστική

Συνδυαστική

Re: Συνδυαστική

Re: Συνδυαστική

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