Drumuri pe grilă: cum numeri rutele minime

Numărul drumurilor minime pe o grilă se poate calcula adunând, în fiecare intersecție, numărul drumurilor care sosesc din cele două direcții permise. Dacă mergi numai la dreapta și în sus, orice drum către un punct vine fie din stânga, fie de jos. Cele două categorii nu se suprapun.

Pe o grilă în care destinația se află la trei pași la dreapta și doi în sus, există zece drumuri minime. Toate au cinci pași, însă ordinea pașilor diferă. Acesta este un exemplu de numărare a rutelor, nu de măsurare a lungimii lor.

Ce înseamnă drum minim în această problemă?

Imaginează-ți străzi desenate pe liniile unui caroiaj. Pleci din colțul stâng de jos și vrei să ajungi în colțul drept de sus. Te deplasezi între intersecții vecine, fără diagonale.

Dacă destinația este la trei segmente spre dreapta și două spre sus, orice drum are nevoie de cel puțin cinci segmente. Un pas spre stânga sau în jos ar trebui compensat ulterior și ar lungi traseul. Drumurile minime folosesc deci numai cele două direcții utile.

Această regulă presupune că segmentele au lungimi egale și că nu există alte restricții. Un sens unic schimbat, o stradă lipsă sau costuri diferite pentru segmente ar defini altă problemă. Mai jos introducem un singur tip de obstacol, precizat explicit.

Cum numeri direct o grilă mică?

Pentru două deplasări la dreapta și una în sus, scrie D pentru dreapta și S pentru sus. Rutele sunt DDS, DSD și SDD. Există trei, fiindcă pasul în sus poate ocupa prima, a doua sau a treia poziție.

Dacă scrii DDS de două ori, nu ai descoperit alt traseu. Pașii spre dreapta sunt identici ca tip, chiar dacă se află pe segmente diferite. Șirul complet de direcții identifică drumul pornit din aceeași intersecție.

La trei pași la dreapta și doi în sus, ai cinci poziții. Poți identifica un traseu prin cele două poziții ale pașilor S. Perechile sunt 1–2, 1–3, 1–4, 1–5, 2–3, 2–4, 2–5, 3–4, 3–5 și 4–5. Rezultă zece rute.

Lista este suficient de mică pentru a fi verificată complet. Pentru o grilă mai mare, însă, enumerarea devine greu de urmărit și riscul de repetare crește.

De ce aduni numerele din stânga și de jos?

Să presupunem că într-o intersecție poți ajunge pe trei drumuri din stânga și pe patru drumuri de jos. Ultimul segment arată imediat categoria fiecărui traseu: ori este orizontal, ori vertical. Niciun traseu nu poate avea ambele tipuri de ultim pas.

Prin urmare, există $3+4=7$ drumuri către intersecție. Nu înmulțești 3 cu 4, fiindcă nu alegi succesiv un drum din fiecare categorie. Alegi una dintre două alternative.

Pe marginea inferioară există o singură rută către fiecare intersecție: mergi numai la dreapta. Pe marginea stângă există tot una: mergi numai în sus. Aceste valori inițiale permit completarea interiorului prin adunare.

Înălțime / deplasare la dreapta	0	1	2	3
2	1	3	6	10
1	1	2	3	4
0	1	1	1	1

Tabelul se citește ca o hartă: plecarea este în stânga jos. De exemplu, 6 se obține din 3 aflat în stânga și 3 aflat dedesubt. La destinație, $6+4=10$ confirmă lista traseelor.

Cum eviți confuzia dintre pătrățele și intersecții?

Un dreptunghi cu trei pătrățele pe orizontală și două pe verticală are patru coloane și trei rânduri de intersecții. De la o margine la cealaltă faci trei pași orizontali, nu patru.

Numără segmentele dintre puncte, nu punctele de pe aceeași linie. Dacă ai cinci intersecții consecutive, între ele există patru segmente. Aceeași diferență dintre repere și spații apare frecvent în problemele de numărare.

În desen, notează coordonatele plecării cu $(0,0)$ și ale destinației cu $(3,2)$. Coordonatele indică exact numărul de pași necesari pe fiecare direcție. O etichetare clară economisește mai mult timp decât corectarea unui tabel pornit de la dimensiuni greșite.

Care este formula pentru o grilă fără obstacole?

Dacă ai $r$ pași la dreapta și $s$ în sus, drumul conține $r+s$ pași. Alegi care dintre poziții sunt ocupate de pașii la dreapta. Numărul rutelor este:

$$N=\binom{r+s}{r}=\frac{(r+s)!}{r!\,s!}.$$

Pentru patru pași la dreapta și trei în sus, obții $7!/(4!\,3!)=35$. Formula numără aceleași trasee ca tabelul, doar că le descrie prin pozițiile pașilor.

Nu folosești $(r+s)!$ singur. Acea valoare ar trata pașii de același tip ca și cum ar fi etichetați diferit și ar număra repetat aceeași rută. Simplificarea factorialelor elimină tocmai aceste repetări.

Dacă expresia cu factoriale este prea nouă, păstrează metoda tabelului. În parcursul pentru bazele de calcul poți identifica operațiile care merită consolidate înainte să comprimi explicația într-o formulă.

Cum numeri rutele care trec printr-un punct obligatoriu?

Pleci din $(0,0)$ către $(4,3)$ și trebuie să treci prin $P=(2,1)$. Până la P faci doi pași la dreapta și unul în sus: există trei rute.

De la P la destinație rămân doi pași la dreapta și doi în sus: există șase rute. Oricare dintre primele trei poate fi continuată cu oricare dintre ultimele șase. În total sunt $3\cdot6=18$ drumuri.

Aici înmulțești, deoarece construiești drumul în două etape succesive. Întâi alegi traseul până la P, apoi continuarea. La completarea unui punct din tabel adunai alternative pentru ultimul pas; întrebarea era diferită.

Fiecare drum care trece prin P are o singură astfel de împărțire. Cum te deplasezi doar în sus și la dreapta, nu te poți întoarce la P și nu apar vizite repetate care să încurce numărătoarea.

Ce se întâmplă dacă aceeași intersecție este blocată?

Pe aceeași grilă, există 35 de drumuri fără restricții și 18 trec prin P. Dacă P nu poate fi traversat, rămân $35-18=17$ drumuri permise.

Poți verifica și în tabel: scrii zero în P, deoarece niciun drum admis nu poate ajunge acolo, apoi continui adunările. Punctele din dreapta și de deasupra lui vor primi valori mai mici, reflectând rutele eliminate.

Nu confunda o intersecție blocată cu un singur segment închis. În al doilea caz, unele drumuri pot trece prin aceleași intersecții folosind alte segmente. Trebuie eliminată doar contribuția care traversează segmentul interzis.

Când compari cele două rezolvări, folosești verificarea printr-o metodă alternativă: scăderea traseelor interzise și tabelul cu obstacol trebuie să dea același total.

Exerciții cu răspunsuri explicate

1. Câte rute minime au un pas la dreapta și patru în sus? 5, după poziția unicului pas la dreapta.
2. Câte rute are o grilă cu doi pași pe fiecare direcție? 6. Poți enumera pozițiile celor doi pași la dreapta în patru locuri.
3. Pe grila de doi pe doi, câte rute trec prin centrul $(1,1)$? 4, deoarece ai două variante până la centru și două după el.
4. Dacă centrul aceleiași grile este blocat, câte rute rămân? 2, din cele șase inițiale, după eliminarea celor patru interzise.

Dacă încurci adunarea cu înmulțirea, explică întâi ce reprezintă fiecare alegere. Această diferență poate fi exersată pe desene mici cu un profesor ales din anunțurile pentru meditații la matematică.

Întrebări frecvente

Contează ordinea pașilor?

Da. DSD și DDS sunt trasee diferite, chiar dacă ajung în același loc și au aceeași lungime.

Formula se aplică dacă pot merge și pe diagonală?

Nu în forma prezentată. Diagonalele schimbă tipurile de pași și uneori chiar lungimea minimă.

Unde pot explora alte grile?

Activitatea NRICH despre drumuri prin oraș pornește de la străzi pe caroiaj. Dimensiunile, punctul obligatoriu și exercițiile din acest articol sunt alese separat.