Colorare

[Claudiu Mindrila]

Patratele unitate ale unei table \( 2008 \times 2008 \) se coloreaza cu \( 3 \) culori date, astfel incat sa se respecte simultan conditiile:
(i) orice patrat \( 2 \times 2 \) format din patrate unitate contine toate cele trei culori;
(ii) doua patrate unitate cu o latura comuna au culori diferite.
Cate astfel de colorari exista?

Alexandru Ciolan, concursul "Nicolae Coculescu" 2007 (sectiunea "Ion Minulescu")

[Andi Brojbeanu]

Ne alegem una dintre cele trei culori pentru a colora primul patrat unitate de pe prima coloana a tablei. In functie de alegerea facuta, patratul \( 2\times 2 \)fromat din patrate unitate va putea fi colorat in mai multe moduri.
Pe prima linie a tablei \( 2008\times 2008 \), imediat dupa patratul unitate pe care l-am colorat, putem colora urmatorul patrat unitate cu doua culori diferite de cea aleasa inainte, conform conditiei (ii). La fel vom proceda si cu colorarea patratului unitate imediat urmator celui anterior, pe prima coloana a tablei \( 2008\times 2008 \).
Colorarea celui de-al patrulea patrat unitate al patratului \( 2\times 2 \) pe care am colorat pana acum va fi determinata, confrom conditiei (i), de colorarea aleasa pana acum a celorlalte patrate unitate ale aceluiasi patrat \( 2\times 2 \), in felul urmator:pe prima linie a patratului \( 2008\times 2008 \), in continuarea primului patrat unitate colorat putem alege una dintre cele doua culori ramase pentru a colora patratul unitate urmator, iar in continuarea primului patrat unitate colorat, dar pe prima coloana a tablei \( 2008\times 2008 \), putem alege aceasi culoare cu care am colorat al doilea patrat al primei linii (cazul I) sau ultima culoare ramasa (cazul II). Astfel, conform conditiei (i), cel de-al patrulea patrat unitate al patratului \( 2\times 2 \) pe care am colorat pana acum va fi colorat cu ultima cu ultima culoare ramasa (in cazul I) sau cu una dintre cele trei culori pe care am ales-o initial in colorarea primului patrat unitate (in cazul II).
O reprezentare a numarului modalitatilor de colorare a patratului \( 2\times 2 \) ar fi:
\( \overline{\underline{|3\|2|}} \)
\( \overline{\underline{|2\|1|}} \)
Toate celelalte patrate unitate de pe prima linie a tablei \( 2008\times 2008 \) aflate in continuarea celor doua colorate pana acum vor fi colorate dupa 2 posibilitati, conform conditiei (ii). Analog si in cazul primei coloane a tablei \( 2008\times 2008 \). Restul patratelor unitate vor fi colorate in functie de prima coloana si prima linie a tablei \( 2008\times 2008 \), conform conditiei (ii).
O reprezentare a numarului modalitatilor de colorare a tablei \( 2008\times 2008 \) ar fi:
\( \overline{\underline{|3\|2\|2\|2\|......\|2\|2|}} \)
\( \overline{\underline{|2\|1\|1\|1\|......\|1\|1|}} \)
\( \overline{\underline{|2\|1\|1\|1\|......\|1\|1|}} \)
\( \overline{\underline{|...|...|...|...|....|...|...|}} \)
\( \overline{\underline{|...|...|...|...|....|...|...|}} \)
\( \overline{\underline{|2\|1\|1\|1\|......\|1\|1|}} \)
\( \overline{\underline{|2\|1\|1\|1\|......\|1\|1|}} \)
Asadar, numarul colorarilor posibile ale tablei \( 2008\times 2008 \) este egal cu \( 3\times 2^{2007} \times 2^{2007}=3\times 2^{4014} \).