Câte drumuri minime sunt într-o rețea?
Lecția pe scurt · clasa a X-a · Probleme practice de numărare
Un drum minim de la un colț la cel opus, cu pași spre dreapta și pași în sus, este un șir de pași în care alegi doar pozițiile pașilor în sus. Numărul drumurilor este deci . Exemplu: pe o rețea de străzi cu pași spre est și spre nord, un curier are de drumuri minime. Dacă schimbi rolurile, dă același rezultat.
O problemă practică de numărare se rezolvă în doi pași: întâi scrii un exemplu real al lucrului numărat, apoi alegi regula. Exemplul arată dacă ai de-a face cu o listă ordonată, cu un grup fără ordine, cu un traseu sau cu o repartizare, iar asta hotărăște formula.
Secvențele de ADN cu un număr dat de litere de fiecare fel se numără cu combinări: stabilești unde stă fiecare literă, începând cu una dintre ele. Un traseu minim pe o grilă cu mutări spre dreapta și mutări în sus se alege în feluri; un punct de ocolit se tratează prin complement, înmulțind drumurile de dinainte și de după el. Elementele nevecine dintr-un șir se aleg prin metoda golurilor: elemente din în moduri.
Când grupele primesc tratamente diferite, fiecare se completează la rândul ei și nu se împarte la nimic; factorialul intervine doar pentru grupele de care nu te poate deosebi nimic. Cerințele de tipul „fiecare categorie reprezentată” se rezolvă prin complement, iar grupele cărora le lipsește o categorie se adună cu principiul includerii și al excluderii.
De reținut
- un drum minim cu pași se alege prin pozițiile pașilor în sus:
- „cel puțin un” se numără prin complement: toate minus cele fără
- înainte de formulă, scrie un exemplu concret al obiectului numărat
Greșeala tipică
Se numără drumurile ca , ca și cum fiecare pas ar fi liber; un drum minim are un număr fix de pași în fiecare direcție, deci se aleg doar pozițiile lor, .
Exerciții din această mini-lecție
Câte secvențe de lungime au exact două litere și trei litere ?
- a)
- b)
- c)
- d)
Vezi răspunsul
Răspuns corect: a)
Alegi pozițiile celor două litere dintre cele cinci: ; restul pozițiilor primesc .
Într-o rețea cu pași spre dreapta și în sus, câte drumuri minime trec prin nodul aflat cu pas la dreapta și în sus față de plecare?
- a)
- b)
- c)
- d)
Vezi răspunsul
Răspuns corect: c)
Până la nod sunt drumuri; de la nod mai sunt pași la dreapta și în sus, adică de drumuri. Prin nod trec .
Șapte parcele stau în linie. În câte moduri se pot alege parcele, oricare două nevecine?
- a)
- b)
- c)
- d)
Vezi răspunsul
Răspuns corect: b)
Cele parcele nealese lasă goluri, iar parcelele alese ocupă goluri diferite: .
Întrebări conexe
Câte echipe de din chimiști și fizicieni au cel mult un fizician?
„Cel mult unul” înseamnă zero sau unu, deci împarți în două cazuri care se exclud. Fără fizician: echipe. Cu exact un fizician: de echipe. Adunând cazurile obții de echipe.
Câte grupe de probe conțin cel puțin o probă contaminată?
Dintr-un lot de probe, dintre care contaminate, se pot forma de grupe. Grupele fără nicio probă contaminată se aleg doar din cele curate: . Rămân de grupe cu cel puțin o probă contaminată.
În câte feluri se pun probe diferite în incubatoare?
Fiecare probă primește unul dintre cele incubatoare, iar un incubator poate primi oricâte probe sau niciuna. Alegerile sunt independente, deci regula produsului dă de repartizări. Dacă niciun incubator nu are voie să rămână gol, numărătoarea se face prin complement.
În câte feluri se pot nimeri exact răspunsuri dintr-un test cu întrebări?
Pentru un test adevărat–fals, o foaie cu exact răspunsuri corecte e determinată de mulțimea întrebărilor la care ai răspuns corect. Alegi aceste întrebări din : de foi posibile, din totalul de .
Câte drumuri minime are un robot care se mișcă în trei dimensiuni?
Dacă robotul face pași pe fiecare dintre cele trei axe, drumul are pași. Alegi pozițiile pașilor pe prima axă, , apoi pe a doua, din cele rămase, ; restul revin celei de-a treia. Rezultă de drumuri.
Oamenii mai întreabă și: numărul drumurilor minime pe o grilă · drumuri cele mai scurte într-o rețea · câte trasee minime pe o tablă de șah · drumuri cu pași la dreapta și în sus