Salti della pulce!

[Albirz]

Quanti cammini minimi congiungono due angoli opposti di una scacchiera 8×8 senza passare dalle quattro caselle centrali?

[Albirz]

Ditemi se questa soluzione è corretta per favore: parlando di cammini minimi, significa che ci viene chiesto il numero di percorsi di 14 passi che congiungono due angoli opposti di una scacchiera 8x8. I percorsi in totale sono 3432.
Da questi dobbiamo escludere quelli che passano per le quattro caselle centrali che in tutto mi vengono 160. Dunque alla fine il numero di percorsi cercato è 3432−160=3272.

[karlosson_sul_tetto]

Il numero totale di percorsi è quello, ma quelli passanti sono di più... posta il tuo ragionamento

[Albirz]

Ho contato i vari percorsi che portano ad ognuno delle 4 caselle centrali (sempre col metodo degli anagrammi) e alla fine li ho sommati e sottratti ai totali. Immaginavo di aver sbagliato qualcosa xD. Come avrei dovuto fare?

[karlosson_sul_tetto]

Prima prova a fare un problema più semplice: quanti percorsi (minimali da un angolo all'altro eccetera eccetera) ci sono che passano per il quadratino $(3,3)$? e $(1,8)$? e $(2,6)$? e in generale, per un quadratino $(m,n)$ contenuto in una scacchiera $(a,b)$? (le coordinate si intendono "contando" i quadratini )

[Albirz]

Ho capito l'errore di prima nel senso che non bastava contare con quanti percorsi si arriva ad ognuna di quelle 4 caselle ma anche i modi in cui i percorsi vengono poi continuati per arrivare a B. Giusto? Quindi calcolo per esempio il numero di percorsi di arrivare a quadratino (4,4) e li moltiplico con il modo di continuarli fino a B, ripetendo tale procedimento per tutti i 4 quadratini centrali e infine li sommo. Il fatto è che tale numero mi viene maggiore dei percorsi totali!!Cosa ho stavolta sbagliato?

[Albirz]

Per risolvere il problemino più semplice devo contare i percorsi fino alla casella (m,n) e poi li moltiplico con i percorsi che conducono all'angolo in cui bisogna approdare?
Quindi, se m indica le colonne ed n le righe, questi percorsi sono: $ \binom{m+n-2}{m-1} $ X $ \binom{b-m+a-n}{b-m} $ ??

[karlosson_sul_tetto]

Per risolvere il problemino più semplice devo contare i percorsi fino alla casella (m,n) e poi li moltiplico con i percorsi che conducono all'angolo in cui bisogna approdare?
Quindi, se m indica le colonne ed n le righe, questi percorsi sono: $ \binom{m+n-2}{m-1} $ X $ \binom{b-m+a-n}{b-m} $ ??

Si (stai attento però che devi sottrarre -2 e -1 anche nel secondo binomiale) EDIT: no, non è vero.

Riguardo a prima, il problema è che cosi conti più volte uno stesso percorso: se chiami ABCD le quattro caselle (in senso antiorario, in modo che A sia quella in basso a sinistra e che i percorsi che cerchiamo stiano tra la casella in basso a sinistra e quella in alto a destra), allora un percorso che passa per A o D deve passare per forza anche per B o C, per non parlare di quelli che passano per ABD o ACD...
Quindi ti consiglio di vedere in che "zone" può entrare il percorso e da quali può uscire (rispetto al quadratino, esempio: entra sotto A ed esce a destra di C, esce a sinistra di B ed esce a destra di D, entra a sinistra di A ed esce sopra D ecc) e per ognuno di questi calcolare il numero di modi per muoversi nello spazio rimanente per arrivare ai vertici.

[Albirz]

Sicuro che devo aggiugnere al secondo binomiale quel -2 e -1? Comunque a questo punto potresti scrivermi per cortesia la tua soluzione perchè mi sono un po' perso su questo fatto di esce a destra/sinistra di A/B/C/D ecc...??

[karlosson_sul_tetto]

Sicuro che devo aggiugnere al secondo binomiale quel -2 e -1?

Uhm, no, hai ragione tu

Ok, per semplicità partendo dall'angolo in basso a sinistra, numero le righe e le colonne da 1 a 8; dobbiamo cercare i percorsi che passano per almeno una tra le caselle $(4,4),(4,5),(5,4),(5,5)$.
Divido in vari casi, a seconda per quali caselle passi il percorso

1) Ad un certo punto del percorso si passa dalla casella $(4,3)$ alla casella $(4,4)$
2) Ad un certo punto del percorso si passa dalla casella $(5,3)$ alla casella $(5,4)$
3) Ad un certo punto del percorso si passa dalla casella $(3,4)$ alla casella $(4,4)$
4) Ad un certo punto del percorso si passa dalla casella $(3,5)$ alla casella $(4,5)$

...con i loro bellissimi sottocasi!
1a) Ad un certo punto del percorso si passa dalla casella $(4,5)$ alla casella $(4,6)$
1b) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(5,6)$
1c) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(6,5)$
1d) Ad un certo punto del percorso si passa dalla casella $(5,4)$ alla casella $(6,4)$
1e) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(5,6)$
1f) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(6,5)$
Se ripeto il procedimento per i casi 2), 3), 4) ottengo tutti i possibili percorsi che passano per il quadratino centrale, siccome ho determinato il punto in cui devono entrare e quello in cui devono uscire (con un solo possibile percorso interno), quindi: spegniamo il cervello e conti!

1a) Ad un certo punto del percorso si passa dalla casella $(4,5)$ alla casella $(4,6)$
$\binom{5}{2}\cdot\binom{6}{2}=150$
1b) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(5,6)$
$\binom{5}{2}\cdot\binom{5}{2}=100$
1c) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(6,5)$
$\binom{5}{2}\cdot\binom{5}{2}=100$
1d) Ad un certo punto del percorso si passa dalla casella $(5,4)$ alla casella $(6,4)$
$\binom{5}{2}\cdot\binom{6}{2}=150$
1e) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(5,6)$
$\binom{5}{2}\cdot\binom{5}{2}=100$
1f) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(6,5)$
$\binom{5}{2}\cdot\binom{5}{2}=100$
Totale=700

2a) Ad un certo punto del percorso si passa dalla casella $(5,4)$ alla casella $(6,4)$
$\binom{6}{2}\cdot\binom{6}{2}=225$
2b) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(6,5)$
$\binom{6}{2}\cdot\binom{5}{2}=150$
2c) Ad un certo punto del percorso si passa dalla casella $(5,5)$ alla casella $(5,6)$
$\binom{6}{2}\cdot\binom{5}{2}=150$
Totale=525

Ora, noto che i casi di 3) sono gli stessi di 1) e i casi di 4) sono gli stessi di 2) (basta fare la simmetria rispetto alla diagonale, non è che mi scocciavo di scrivere altri 9 casi ) quindi il numero di percorsi è $2\cdot (700+525)=2450$ e il complementare cercato è $3432-2450=982$.


Personalmente, ho inizialmente fatto il problema nell'altro modo, ovvero contando i percorsi che non passavano per i quattro quadratini centrali. Ci sono due casi (simmetrici e con lo stesso numero di percorsi): o passo il quadratino da sopra a sinistra, oppure da sotto a destra; analizzo il primo.
Devo quindi necessariamente passare per il quadrato $3\times 3$ delimitato dalle caselle $(1,6),(1,8),(3,8),(3,6)$.
Una cosa bella da notare è che date le tre caselle $(1,8), (2,7), (3,6)$, devo passare per una e soltanto una di queste.
Il numero di percorsi per $(1,8)$ è $\binom{7}{0}\cdot \binom{7}{0}=1$.
Il numero di percorsi per $(2,7)$ è $\binom{7}{1}\cdot \binom{7}{1}=49$.
Il numero di percorsi per $(3,6)$ è $\binom{7}{2}\cdot \binom{7}{2}=441$
Il numero totale cercato è $2\cdot(1+49+441)=982$ e con grande gioia notiamo che è lo stesso di sopra

[Albirz]

Scervellandomi ho capito il tutto. Solo una cosa: nei 6 sottocasi di 1) ce ne sono due uguali, quando dici
1b) Ad un certo punto del percorso si passa dalla casella (5,5) alla casella (5,6)
1c) Ad un certo punto del percorso si passa dalla casella (5,5) alla casella (6,5)
1e) Ad un certo punto del percorso si passa dalla casella (5,5) alla casella (5,6)
1f) Ad un certo punto del percorso si passa dalla casella (5,5) alla casella (6,5)
Non sono uguali?

E un'altra cosa: perchè i casi 3) e 4) sono rispettivamente simili a 1) e 2)...in 3) non c'è l'uscita in (6,4)[che c'è in 1)] e in 4) non c'è l'uscita in (6,4) [che c'è in 2)]?

[karlosson_sul_tetto]

Mi sono dimenticato di specificare, nei casi 1b) e 1c) il percorso passa anche per $(4,5)$, mentre in 1e) e 1f) passa per $(5,4)$

Per dire che sono simili, basta che inverti le coordinate di ciascuna coppia (sto formalizzando troppo un concetto tutto sommato non troppo difficile...) cosi come da (4,3) puoi uscire in (4,6), (5,6), (6,5), (6,4), anche da (3,4) puoi uscire in (6,4), (6,5), (5,6), (4,6). Da (3,5) puoi uscire in (4,6) ma non in (6,4), cosi come in (5,3) puoi uscire da (6,4) ma non da (4,6)
In pratica: inverti le righe con le colonne e ti dovrebbe tornare

[Albirz]

Perfetto. Grazie mille e scusami se ti ho fatto essere ripetitivo.