O tabla de sah cu 3 coloane si 7 linii (deci 3 x 7 patratele) are fiecare patratel colorat aleator in rosu sau albastru. Demonstrati ca exista un dreptunghi care are in colturi patratele toate de aceasi culoare. Ramane afirmatia adevarata pentru o tabla de forma 3 x 6 ?

[Citat] O tabla de sah cu 3 coloane si 7 linii (deci 3 x 7 patratele) are fiecare patratel colorat aleator in rosu sau albastru. Demonstrati ca exista un dreptunghi care are in colturi patratele toate de aceasi culoare. Ramane afirmatia adevarata pentru o tabla de forma 3 x 6 ?

BÄ?nuiesc cÄ? atunci când aÅ£i spus dreptunghi aÅ£i exclus pÄ?tratul, cÄ?ci problema ar fi prea simplÄ?. Dar în acest caz, existÄ? o mulÅ£ime de contra exemple. IatÄ?

douÄ?:

[Citat] [Citat] O tabla de sah cu 3 coloane si 7 linii (deci 3 x 7 patratele) are fiecare patratel colorat aleator in rosu sau albastru. Demonstrati ca exista un dreptunghi care are in colturi patratele toate de aceasi culoare. Ramane afirmatia adevarata pentru o tabla de forma 3 x 6 ? BÄ?nuiesc cÄ? atunci când aÅ£i spus dreptunghi aÅ£i exclus pÄ?tratul, cÄ?ci problema ar fi prea simplÄ?. Dar în acest caz, existÄ? o mulÅ£ime de contra exemple. IatÄ? douÄ?: Am sÄ? scriu culorile cu A Å?i R, Å?i ca sÄ? fie mai uÅ?or de scris întorc tabla, astfel cÄ? voi avea 3 linii Å?i 7 coloane.

Patratele le consideram tot dreptunghiuri, deci sunt acceptate in acest enunt. Altfel este drept, contraexemplul pe care-l dati ar fi mers.

[Citat] Patratele le consideram tot dreptunghiuri, deci sunt acceptate in acest enunt. Altfel este drept, contraexemplul pe care-l dati ar fi mers.

DupÄ? cum spuneam, în acest caz, problema nu mi se pare dificilÄ?, ci mai dificil modul de a redacta rezolvarea. Dar cred cÄ? am gÄ?sit o posibilitate destul de simplÄ?.
Pentru o culoare am sÄ? folosesc cifra 1 Å?i pentru alta cifra 0. Ã?n felul acest am sÄ? acopÄ?r tabla cu numerele 1, 2, ...,7 scrise câte unul pe linie, în baza 2, (aliniate la dreapta)Å?i pun 0 în pÄ?trÄ?Å£elele rÄ?mase goale.(Ca la completarea tabelelor de adevÄ?r cu 3 propoziÅ£ii simple)Ã?n felul acesta pe ultima linie sunt nevoit sÄ? scriu 7,adicÄ? 111 sau dacÄ? nu-mi convine 000, dar în ambele cazuri obÅ£inem trei dreptunghiuri de care se vorbea în enunÅ£.Completând tabla cum am spus, am evitat la maxim formarea acelui dreptunghi cu colÅ£urile de aceeaÅ?i culoare. E clar cÄ? enunÅ£ul nu e valabil dacÄ? tabla nu are ultima linie, cÄ?ci am gÄ?sit contra exemplul pe care l-am descris. De observat cÄ? se putea cere în problemÄ? sÄ? se arate cÄ? sunt cel puÅ£in trei astfel de dreptunghiuri.

[Citat] [Citat] Patratele le consideram tot dreptunghiuri, deci sunt acceptate in acest enunt. Altfel este drept, contraexemplul pe care-l dati ar fi mers. DupÄ? cum spuneam, în acest caz, problema nu mi se pare dificilÄ?, ci mai dificil modul de a redacta rezolvarea. Dar cred cÄ? am gÄ?sit o posibilitate destul de simplÄ?. Pentru o culoare am sÄ? folosesc cifra 1 Å?i pentru alta cifra 0. Ã?n felul acest am sÄ? acopÄ?r tabla cu numerele 1, 2, ...,7 scrise câte unul pe linie, în baza 2, (aliniate la dreapta)Å?i pun 0 în pÄ?trÄ?Å£elele rÄ?mase goale.(Ca la completarea tabelelor de adevÄ?r cu 3 propoziÅ£ii simple)Ã?n felul acesta pe ultima linie sunt nevoit sÄ? scriu 7,adicÄ? 111 sau dacÄ? nu-mi convine 000, dar în ambele cazuri obÅ£inem trei dreptunghiuri de care se vorbea în enunÅ£.Completând tabla cum am spus, am evitat la maxim formarea acelui dreptunghi cu colÅ£urile de aceeaÅ?i culoare. E clar cÄ? enunÅ£ul nu e valabil dacÄ? tabla nu are ultima linie, cÄ?ci am gÄ?sit contra exemplul pe care l-am descris. De observat cÄ? se putea cere în problemÄ? sÄ? se arate cÄ? sunt cel puÅ£in trei astfel de dreptunghiuri.

Foarte frumoasa ideea cu numerele in baza 2!

Cred ca totusi nu putem cere existenta a 3 dreptunghiuri dupa cum se vede din exemplul (in care am lua in baza 2) 1,1,2,3,4,5,6. Avem un singur dreptunghi in acest caz.

Ca alternativa iata o solutie fara scriere in baza 2:

Notam cu R patratele rosii si cu A pe cele albastre. Daca tabla are doua linii cu aceasi configuratie de culori, atunci avem un dreptunghi de tipul cerut.

Presupunem ca toate liniile tablei sunt diferite. Deoarece exista 2x2x2=8 linii distincte ce putem forma, rezulta ca tabla contine una din liniile AAA sau RRR. Fara restrangerea generalitatii putem presupune ca avem linia AAA. Intre celelalte 6 linii exista cel putin 1 linii care contin doi de A(caci exista doar 4 linii care contin cel mult un A). Atunci linia aceasta si cu AAA ne dau dreptunghiul cerut.

[Citat] Presupunem ca toate liniile tablei sunt diferite. Deoarece exista 2x2x2=8 linii distincte ce putem forma, rezulta ca tabla contine una din liniile AAA sau RRR. Fara restrangerea generalitatii putem presupune ca avem linia AAA. Intre celelalte 6 linii exista cel putin 1 linii care contin doi de A(caci exista doar 4 linii care contin cel mult un A). Atunci linia aceasta si cu AAA ne dau dreptunghiul cerut.

Aceasta de fapt este exact cum aÅ? spune cÄ? scriu în baza 2 numerele de la 1 la 6 Å?i apoi trebuie sÄ? completez încÄ? o linie Å?i nu am de ales decât unul din numerele 0 sau 7 (ca sÄ? fie toate liniile distincte). Ã?n ambele cazuri se formeazÄ? dreptunghiuri de care cÄ?utÄ?m cÄ?ci avem Å?i linii cu doi de 0(în cazul în care îl adug pe 0) Å?i cu doi de 1(în cazul în care îl adug pe 7)