Diskret matematik · 2025-08-12

Uppgift 2

Uppgift 2

Agda bor i ett kvarter i ett rutnät med gator. Hon vill promenera från sitt hem till affären, genom att gå tre sträckor norrut och sex sträckor österut. Hon måste alltså gå 9 sträckor totalt. I figuren är en sådan promenad markerad.

A 6-by-3 street grid shows Agda at the lower-left and the shop at the upper-right, with a highlighted example path and a marked forbidden horizontal street between two houses.

(a)

Hur många olika promenader totalt kan Agda gå, med tre sträckor norr och sex sträckor öster?

(b)

Ester och Gerd är grannar med en gemensam gata. Agda vill inte promenera på just denna sträcka mellan husen eftersom då Esters pudel har för vana att skälla så förfärligt om hon går där. På hur många sätt kan Agda ta sig till affären utan att gå mellan de två husen i figuren?

Visa lösningDölj lösning

Agda ska gå $9$ sträckor, och tre av dessa ska vara i nordlig riktning. Detta ger totalt $\binom{9}{3} = 84$ olika promenader.
Först räknar vi ut antalet promenader som passerar Ester och Gerds hus. En sådan promenad består av tre delar:
- $5$ sträckor ($2$ norr, $3$ öster),
- ett sträckor österut, mellan husen,
- $3$ sträckor ($1$ norr, $2$ öster).
Första delen kan väljas på $\binom{5}{2}=10$ sätt och den andra delen har $\binom{3}{1}=3$ sätt. Totalt finns då 30 promenader som passerar den arga pudeln. Vi kan då konstatera att Agda har $84-30 = 54$ pudelfria promenader att välja bland.