Πίνακας 2 x 13

#1

Χρωματίζουμε κάθε τετράγωνο ενός πίνακα 2 × 13 με ένα ακριβώς από τέσσερα διαφορετικά διαθέσιμα χρώματα.
Με πόσους τρόπους μπορεί να γίνει αυτό αν δεν πρέπει να υπάρχουν γειτονικά τετράγωνα με το ίδιο χρώμα?
(Θεωρούμε ότι δύο τετράγωνα του πίνακα είναι γειτονικά αν έχουν κοινή πλευρά.)

abfx · #2

Ονομάζω τους χρωματισμούς που δεν έχουν γειτονικά τετράγωνα ίδιου χρώματος 'νόμιμους'.
Ας είναι a_n

το πλήθος νόμιμων χρωματισμών ενός $2\times n$ πίνακα και a,b,c,d

τα δοσμένα χρώματα.
Είναι $a_1=4\cdot 3=12$ χωματισμοί.
Έστω τώρα χωρίς βλάβη της γενικότητας ένας νόμιμος χρωματισμός ενός $2\times n$ πίνακα με τελευταία στήλη $\begin{center} \begin{tabular}{ |c| } \hline a \\ \hline b \\ \hline \end{tabular} \end{center}$ .
Για να σχηματίσουμε έναν νόμιμο $2\times (n+1)$ χρωματισμό συμπληρώνουμε την τελευταία στήλη με 7 δυνατούς τρόπους:
1. $\begin{tabular}{ |c|c| } \hline a & b \\ \hline b & a \\ \hline \end{tabular} \end{center}$ 2. $\begin{tabular}{ |c|c| } \hline a & b \\ \hline b & c \\ \hline \end{tabular} \end{center}$ 3. $\begin{tabular}{ |c|c| } \hline a & b \\ \hline b & d \\ \hline \end{tabular} \end{center}$

4. $\begin{tabular}{ |c|c| } \hline a & c \\ \hline b & a \\ \hline \end{tabular} \end{center}$ 5. $\begin{tabular}{ |c|c| } \hline a & c \\ \hline b & d \\ \hline \end{tabular} \end{center}$

6. $\begin{tabular}{ |c|c| } \hline a & d \\ \hline b & a \\ \hline \end{tabular} \end{center}$ 7. $\begin{tabular}{ |c|c| } \hline a & d \\ \hline b & c \\ \hline \end{tabular} \end{center}$

Έτσι βλέπουμε ότι $a_{n+1}\geq 7a_n$ .Έστω τυχαίος νόμιμος $2\times (n+1)$ χρωματισμός.
Τότε αφαιρώντας την τελευταία στήλη θα έχουμε νόμιμο $2\times n$ χρωματισμό οπότε και ο αρχικός μας θα προκύπτει με την παραπάνω μέθοδο.
Έτσι, για κάθε

θα είναι $a_{n+1}=7a_n$ οπότε $a_n=12\cdot 7^{n-1}$ και το ζητούμενο:
$a_{13}=12\cdot 7^{12}$ .

#3

Πίνακας 2 x 13

Πίνακας 2 x 13

Re: Πίνακας 2 x 13

Re: Πίνακας 2 x 13

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