Un p?trat

este acoperit (pavat) cu 18 piese de domino

.
S? se arate c? exist? o dreapt? care taie p?tratul în 2 buc??i, f?r? a t?ia nici una dintre piesele de domino.

Exemplu:


Uploaded with ImageShack.us

(Mai multe exemple
http://www.mat.uniroma2.it/~tauraso/Javascript/Domino/domino.html

Jucatorii principali sunt
- cele 36/2 = 18 piese de domino si
- cele 5+5 = 10 linii, 5 orizontale, 5 verticale, dintre care speram sa aratam ca macar una separa patratul 6x6 in doua bucati dreptunghiulare.

Sa notam cele 5 linii orizontale cu L1, L2, L3, L4, L5.
Ele separa (in ansamblu) patratul 6x6 in mai multe dreptunghiuri 6x1.

Sa notam cele 5 linii verticale cu C1, C2, C3, C4, C5.
Ele separa (in ansamblu) patratul 6x6 in mai multe dreptunghiuri 1x6.

(A) Observam ca la orice amplasare (permisa) a dominourilor fiecare piesa este taiata de exact una din cele 10 linii.

(B) Aratam ca orice linie taie un numar par de piese de domino.
Ajunge sa ne legam de L-uri.
Un fel de inductie finita.
L1 taie un numar par de dominouri, deoarece amplasarea la margine permite plasarea orizontala doar pentru un numar par k1 de casute in piese orizontale (netaiate de L1), deci raman in numar par (6-k1) piese verticale taiate de L1.

Inductiv, L2 mosteneste de la L1 un numar par de (6-k1) casute deja ocupate (in piese verticale), care nu vor fi taiate de L2. Cateva dominouri orizontale vor mai lua un numar par de casute intre L1 si L2. Deci exista un numar par de dominouri (verticale) taiate de L2.

Mostenirea merge mai departe la fel de la L2 la L3.

(C) Daca toate piesele de domino ar fi taiate de o linie orizontala sau verticala, atunci toate aceste linii taie (in numar par) cel putin cate 2 piese de domino. Avem deci cel putin (2 ori) x (5+5 linii) = 20 de piese taiate.
Din pacate sunt doar 18 piese de domino.
Acel daca de mai sus nu se intampla. Deci exista o linie (orizontala sau verticala) care separa patratul 6x6 decorat cu piese de domino in doua dreptunghiuri cu (sub)amplasari regulate.

(Solutia adaptata dupa ce am vazut pe net...)

O observatie care scurteaza putin demonstratia de mai sus: daca o linie "taie" exact un domino, atunci, scotand acel domino, restul tablei este impartit in 2 regiuni, fiecare avand aria un numar impar. In mod evident, cele 2 regiuni nu pot fi pavate cu dominouri. Prin urmare, fiecare linie taie cel putin 2 dominouri, etc.