Ile jest najkrótszych drog

[Big_Boss1997]

Witam. Ile jest różnych najkrótszych dróg prowadzących z punktu \(\displaystyle{ (0,0)}\) do punktu \(\displaystyle{ (40,40)}\) takich, które przechodzą przez przynajmniej jeden z punktów \(\displaystyle{ (10,10), (20,20), (30,30)}\), jeśli w jednym kroku możemy pokonać w pionie lub poziomie odcinek długości \(\displaystyle{ 1}\)?

Otrzymałem wynik: \(\displaystyle{ {80 \choose 40} - \left[ {80 \choose 40} - {20 \choose 10} - {40 \choose 20} - {60 \choose 30} \right]}\) (od wszysktich możliwych drog odejmujemy drogi, które napewno nie przechodzą przez zakazane punkty). Czy jest on prawidłowy?

[a4karo]

Nie, takich dróg jest nieskończenie wiele, bo każdą drogę możesz zacząć od dowolnie długiego ciągu
\(\displaystyle{ (0,0) \rightarrow (0,1) \rightarrow (0,0) \rightarrow (0,1)...}\)

Chyba że chodzi Ci o drogi, które wiodą tylko w prawo i do góry...

[Big_Boss1997]

a4karo, wydaje mi, że możemy iśc tylko wprawo, do góry/dól. Bo inaczej to zadanie nie ma za bardzo sensu)

[kerajs]

Otrzymałem wynik: \(\displaystyle{ {80 \choose 40} - \left[ {80 \choose 40} - {20 \choose 10} - {40 \choose 20} - {60 \choose 30} \right]}\) (od wszysktich możliwych drog odejmujemy drogi, które napewno nie przechodzą przez zakazane punkty). Czy jest on prawidłowy?

Nie jest. Przekształcając Twój wzór mam:
\(\displaystyle{ {80 \choose 40} - \left[ {80 \choose 40} - {20 \choose 10} - {40 \choose 20} - {60 \choose 30} \right]= {20 \choose 10} + {40 \choose 20} + {60 \choose 30}}\)
co pewnie miało być sumą dróg przechodzących przez \(\displaystyle{ A=(10,10)}\), przez \(\displaystyle{ B=(20,20)}\) oraz przez \(\displaystyle{ C=(30,30}\)). Jak widać tych co przechodzą przez C jest więcej niż tych co przechodzą przez A, a powinno ich być tyle samo. Jest tak, bo brakuje dróg po przejściu punktu A (analogicznie brakuje dróg po przejściu punktu C). Uzupełniając mam:
\(\displaystyle{ {20 \choose 10}{60 \choose 30} + {40 \choose 20} {40 \choose 20} + {60 \choose 30} {20 \choose 10}}\)
To tez nie jest dobry wynik bo niektóre zdarzenia zliczane są wielokrotnie.

Liczyłbym tak:
\(\displaystyle{ A+(B-A \cap B)+(C-A \cap C-B \cap C+A \cap B \cap C)=}\)

\(\displaystyle{ = {20 \choose 10} {60 \choose 30}+\left[ {40 \choose 20} {40 \choose 20}-
{20 \choose 10} {20 \choose 10} {40 \choose 20} \right]+}\)

\(\displaystyle{ +\left[ {60 \choose 10} {20 \choose 10}- {20 \choose 10} {40 \choose 20} {20 \choose 10}-
{40 \choose 20} {20 \choose 10} {20 \choose 10}+
{20 \choose 10} {20 \choose 10}{20 \choose 10} {20 \choose 10} \right]}\)

lub z włączeń i wyłączeń:
ilość dróg przechodzących tylko przez jeden punkt z A,B,C+ tylko dwa punkty + przez trzy punkty
ale miałbym więcej wklepywania.