Data la griglia in figura
Contare quanti percorsi uniscono A e B senza passare due volte su uno stesso nodo della griglia?
- 1792 ✔
Data la griglia in figura
Contare quanti percorsi uniscono A e B senza passare due volte su uno stesso nodo della griglia?
peccato che non si tratta di calcolare il numero di percorsi di cammino minimo. Sarebbe stato più semplice!
Comunque penso che per ottenere il risultato richiesto si possa procedere nel seguente modo:
Abbiamo 2 cammini minimi passando sul contorno della griglia. Tutti gli altri cammini sono a slalom. Abbiamo ad esempio 2 cammini massimi di cui in figura ne è messo uno di questi: notiamo che interessano tutte le celle quadrate della griglia. (E’ facile individuare lo slalom contrapposto a questo)
Un altro slalom fra tutti quelli possibili, senza passare due volte sullo stesso nodo può essere quello di figura:
Nel caso di figura quindi:
2 celle da 2 +2 celle da 3+1 cella da 1
N° cammini possibili: 2·(5!/(2!·2!·1!)) = 60
Quindi il numero di cammini possibili tenendo presente che il numero delle celle della griglia è 11 è dato da:
2 sul contorno (interessa tutte le 11 celle) +
2 interessa ogni cella +
2·2! = 4 (interessa 1 cella e 10 celle) +
4 (interessa 2 celle e 9 celle)+
Ecc. ecc.
Penso che così si mettano in conto tutti i possibili cammini. Il conto è lungo ma penso che sia una strada logicamente possibile per raggiungere il fatidico risultato.
@lucianop non si può generalizzare?
I possibili percorsi sono 2^11=2048, per trovarci con il risultato dovremmo sottrarre 2^8=256 (in questo modo 2048-256=1792) ma non capisco con quale criterio dovremmo sottrarre questa quantità. Mi può aiutare gentilmente???
Ciao. Il risultato 2048 si trova anche facendo il mio ragionamento? Se posso ti aiuto però non ho adesso del tempo.
@lucianop la ringrazio enormemente, non so davvero come risolvere.
Ciao carissima @lola967
Ma da quale testo hai preso questo rompicapo? Sai dove trovare esempi simili con risoluzione?
@lucianop è un esercizio preso dalla prova indam 2021.. ho trovato solo due esercizi simili ma non penso aiutino, comunque li allego!