O problema de sah

[cristina.vuscan]

Care este numărul maxim de cai ce pot fi aşezaţi pe o tablă de şah astfel ca nici unul să nu ameninţe pe altul?
Se cere nu doar numarul, ci si argumentarea raspunsului. Succes, Cristina

[Andreea Neagu]

Calul merge in L, astfel incat va ataca doar piese aflate pe un camp de culoare diferita de cea pe care se afla el. Numarul maxim de cai care pot fi asezati pe o tabla de sah astfel incat sa nu se atace reciproc este 32, daca sunt toti pe patratele de aceeasi culoare.
Andy

[cristina.vuscan]

Da, corect... Aceasta e partea cea mai simpla a intrebarii... Dar ccum justifici ca acesta este numarul maxim? Cris

[Andreea Neagu]

Simplu: tabla de sah este o matrice de 8 pe 8. Total, 64 de patratele. Din astea, 32 sunt albe si 32 negre. Orice cal mai asez pe tabla in afara de cei 32 plasati, sa zicem, pe alb, va fi pe negru. Si am stabilit ca un cal plasat pe alb va ataca numai piese plasate pe negru.
Un cal plasat pe un patrat alb poate ataca cel putin 2 pozitii negre - ca sa zic asa face cel putin un L pe orizontala si unul pe verticala. Asadar n cai plasati pe patratele de aceeasi culoare pot ataca minim n+1 cai plasati pe culori diferite, unde n este intre 1 si 32. Deci n cai de o culoare permit cel mult 32 - (n+1) cai pe culoarea diferita. Daca plasez pe culori diferite voi avea in total maxim 32 - 1 adica 31 de cai. Prin urmare, numarul maxim este 32.
O explicatie bazata strict pe aspectul unei table de sah ar fi: daca ocup toate cele 32 pozitii de o culoare cu cai, toate pozitiile de culoarea cealalta vor fi atacate, deci nu se mai poate plasa nici un cal in plus.
Numai bine,
Andy

[cristina.vuscan]

Marturisesc ca nu prea inteleg explicatia... Spui ca: "Un cal plasat pe un patrat alb poate ataca cel putin 2 pozitii negre - ca sa zic asa face cel putin un L pe orizontala si unul pe verticala. Asadar n cai
plasati pe patratele de aceeasi culoare pot ataca minim n+1 cai plasati pe culori diferite, unde n este intre 1 si 32." Deci din ce spui tu , daca n este 32, atunci cei 32 de cai asezati pe patratele de aceeasi culoare, ar ataca minimum 33 pozitii de culoare opusa. Absurd! Cris

[Andreea Neagu]

Da, stiu, dupa ce plasez 32 de cai nu mai am decat 32 de patratele libere, stiu ca respectivii cai vor ataca aceleasi patratele si nu nshpe mii de patratele diferite, formula de calcul e scoasa doar pentru a vedea cati cai pe culoare diferita ar fi permisi, maximal si ipotetic, pe tabla. Ma bazez doar pe ideea ca o diferenta e maxima atunci cand scazatorul e minim

[Emanuel.Selaru]

Wow, concursul acesta imi aduce aminte de un joc, Hale pe numele lui. Cine il mai stie? Vreau sa jucam virtual! Sau de ce nu, real... Este foarte comic si simplu, la mintea oricui.

[cristina.vuscan]

Da, stiu, dupa ce plasez 32 de cai nu mai am decat 32 de patratele libere, stiu ca respectivii cai vor ataca aceleasi patratele si nu nshpe mii de patratele diferite, formula de calcul e scoasa doar pentru a vedea cati cai pe culoare diferita ar fi permisi, maximal si ipotetic, pe tabla. Ma bazez doar pe ideea ca o diferenta e maxima atunci cand scazatorul e minim

????????
Pai, ori e formula, ori nu e... In matematica nu merge asa... Daca nu e formula, ci e numai asa... de ce o folosesti ca sa justifici cu ea ceva?
Cris

[cristina.vuscan]

Adevarul e ca justificarea faptului ca 32 e numarul maxim nici nu e chiar atat de dificila... Mai mult a complicat-o autorul... Dar va veti exprima parerea atunci cand o voi prezenta... Deci, Andy, curaj! Haide... Cris

[Andreea Neagu]

Curaj este, timp nu. Scriu intre 2 etape de modelare, din laboratorul de la facultate. Pentu moment o explicatie de 2 lei, revin la noapte cu una serioasa: am 32 de cai pe tabla de sah, toti pe o culoare. Prin urmare, orice alt cal as vrea sa asez pe tabla, va fi asezat pe o culoare diferita de a primilor. Dar fiecare cal ataca, dupa cum ziceam, minim 2 pozitii de culoare diferita. Cei 32 de cai vor ataca fiecare minim 2 pozitii de culoare opusa, deci daca n-am tine cont de faptul ca fiecare pozitie neagra poate fi atacata de cel putin 2 cai de pe alb, atunci cei 32 de cai ar putea ataca 64 de pozitii. Dar cum fiecare pozitie poate fi atacata de 2 cai, 64 se imparte la 2 si avem 32 de cai care ataca 32 de pozitii de alta culoare. Prin urmare, nu mai pot adauga nici un cal.
Andy

[cristina.vuscan]

Acest ultim cal pe cine poate ataca, micutul si dragutul de el ?... Cris

[Andreea Neagu]

Ok, un al 33-lea cal va fi plasat, sa zicem, pe negru. In aceste conditii, va putea ataca minim 2 pozitii albe, deci 2 cai existenti.
Andy

[cristina.vuscan]

Asa este... Si e suficient sa atace un singur cal din cei 32 pentru ca numarul maxim de cai care pot fi asezati pe tabla fara sa se ameninte reciproc sa se opreasca la 32... Cris

[cristina.vuscan]

Iata si solutia propusa de autor :
Deoarece un cal care stă pe un pătrat alb ţine sub ameninţare numai pătrate negre, este evident că pot fi aşezaţi 32 de cai, astfel încît să nu se ameninţe doi cîte doi. Pentru aceasta, este suficient să-i aşezăm pe pătratele albe ale tablei (în număr de 64:2=32). Mai delicat este să arătăm că numărul maxim cerut de problemă este exact 32. în acest scop, vom împărţi tabla de şah în opt părţi egale, în formă de dreptunghiuri cu baza de două pătrate şi înălţimea de patru pătrate. Observăm că un cal, aşezat într-un astfel de dreptunghi ţine sub ameninţare un singur pătrat din acest dreptunghi, iar pentru doi cai, pătratele ameninţate sînt diferite. Deducem atunci că în fiecare dintre aceste dreptunghiuri (compuse din 8 pătrate) nu pot fi aşezaţi mai mult de 4 cai, care să nu se ameninţe unul pe altul. Astfel, numărul total de cai pe care putem să-i aşezăm pe tabla de şah nu este mai mare decît 4x8=32.

Cris

[Apolonia]

Dupa parerea mea ar fi imposibil sa asezi mai multi cai pe o tabla de sah decat 4