Drumuri printre clădiri

Detalii: Categorie: Probleme de numărare şi distribuire Probleme de numărare şi distribuire; Publicat: 02 Iulie 2014 02 Iulie 2014; Accesări: 2585 2585

La una din întrunirile săptămânale ale cercului de logică pe oraș, profesorul Henri Brissard de la colegiul Saint-Etienne din Toulouse a prezentat elevilor săi următoarea diagramă a celor 16 colegii din oraș, precizând faptul că laturile trasate cu negru ale celor 16 pătrate din rețea reprezintă drumuri de acces printre clădiri.

o rețea de 4 pe 4 pătrate în interiorul cărora se află câte o clădire galbenă încadrată de un spațiu verde A fiind colțul din stânga jos iar C colțul din dreapta sus

Profesorul Brissard le-a cerut elevilor săi să determine câte drumuri diferite există din punctul A în punctul C, mergând doar în sus și la dreapta. Drumuri diferite pot avea, bineînțeles, așa cum se poate observa pe diagramă, porțiuni comune, a mai precizat profesorul Brissard.
Problema nu este deloc ușoară. Pentru a vă da o mână de ajutor, prezentăm mai jos, pe această diagramă, două drumuri care pleacă din A și ajung în C (unul trasat cu roșu, celălalt cu verde), compuse fiecare din 4 părți.

același desen ca mai sus în care pătratele de pe diagonala secundară au laturile de sus și din stânga trasate cu roșu iar laturile de jos și din dreapta trasate cu verde

Soluție:

După mărimea laturilor pătratelor de-a lungul cărora se merge, un drum care pleacă din A și ajunge în C poate fi format din:

4 părți (ca în figura de mai sus) și în care toate pătratele de-a lungul cărora se merge au latura egală cu cea a pătratelor din rețea;
3 părți (ca în figura de mai jos), în care unul din pătrate are latura de 2 ori mai mare decât latura unui pătrat din rețea;

aceeași rețea de pătrate ca și la cerință doar că primele două pătrate de pe diagonala secundară începând din A au laturile egale cu cele ale pătratelor din rețea iar al treilea are latura de două ori mai mare decât latura unui pătrat din rețea laturile de sus și din stânga fiind trasate cu roșu iar laturile de jos și din dreapta trasate cu verde

2 părți (ca în figura de mai jos), în care unul din pătrate are latura de trei ori mai mare decât latura unui pătrat din rețea iar celălalt latura egală cu latura unui pătrat din rețea, sau în care ambele pătrate au latura de două ori mai mare decât latura unui pătrat din rețea;

aceeași rețea de pătrate ca și la cerință doar că primul pătrat de pe diagonala secundară începând din A are latura egală cu latura unui pătrat din rețea iar al doilea are latura de 3 ori mai mare decât latura unui pătrat din rețea laturile de sus și din stânga fiind trasate cu roșu iar laturile de jos și din dreapta trasate cu verde

1 parte, în care se merge doar de-a lungul laturilor pătratului mare, cu latura de patru ori mai mare decât cea a unui pătrat din rețea.

Dar oricare ar fi varianta de drum aleasă (din 4, 3, 2 sau 1 părți), drumul de-a lungul conturului unui pătrat poate urma doar laturile de sus și din stânga (partea trasată cu roșu, R) sau laturile de jos și din dreapta (partea trasată cu verde, V) - nu neapărat în această ordine -, deoarece se merge doar în sus și la dreapta.
Cazul 1. Drumul este format din 4 părți
În funcție de culoarea (roșie sau verde) aleasă pentru fiecare din cele 4 părți de drum, există următoarele trasee posibile:
a) (V, V, V, V);
b) (R, V, V, V), (V, R, V, V), (V, V, R, V), (V, V, V, R);
c) (R, R, V, V), (R, V, R, V), (R, V, V, R), (V, R, R, V), (V, R, V, R), (V, V, R, R);
d) (R, R, R, V), (R, R, V, R), (R, V, R, R), (V, R, R, R);
e) (R, R, R, R).
Total: 16 trasee.
Cazul 2. Drumul este format din 3 părți
În funcție de culoarea (roșie sau verde) aleasă pentru fiecare din cele 3 părți de drum, există următoarele trasee posibile:
a) (V, V, V);
b) (R, V, V), (V, R, V), (V, V, R);
c) (R, R, V), (R, V, R), (V, R, R);
d) (R, R, R).
Și, întrucât există 3 moduri de a parcurge un drum din 3 părți, după cum pătratul cu latura dublă este primul, al doilea sau al treilea, există în total
3*8=24
de trasee posibile formate din 3 părți.
Cazul 3. Drumul este format din 2 părți
În funcție de culoarea (roșie sau verde) aleasă pentru fiecare din cele 2 părți de drum, există următoarele trasee posibile:
a) (V, V);
b) (R, V), (V, R);
c) (R, R).
Și, întrucât există 3 moduri de a parcurge un traseu din 2 părți - unul urmând laturile a două pătrate duble și două urmând laturile unui pătrat mic, respectiv cele ale unui pătrat triplu -, rezultă că există
3*4=12
de trasee posibile formate din 2 părți.
Cazul 4. Drumul este format dintr-o singură parte, care poate fi roșie sau verde, urmând laturile pătratului mare. Există astfel în acest caz 2 trasee posibile.
Prin urmare, numărul total de drumuri care duc din A în C este egal cu
16+24+12+2=54.