Piccioni Viaggiatori
Ecco a voi un problemino che mi sono inventato in questi giorni e che ho scoperto essere più complesso di quanto immaginassi:
Sia data una striscia di carta suddivisa in $n$ caselle quadrate ($n$ naturale positivo $>=2$). La distanza tra due caselle contigue è per definizione unitaria. Tutte le caselle sono numerate progressivamente, da $1$ ad $n$.
Il gioco è il seguente, massimizzare la lunghezza aggregata ($l$)degli $n-1$ segmenti che congiungono i centri di tutte le $n$ caselle, partendo da uno di essi a piacere e tracciando il segmento che termina in un'altra casella, considerare dunque quest'ultima casa come punto di partenza per il secondo segmento e farlo terminare in una delle restanti $22$ caselle ancora libere. Il gioco termina i centri di tutte le case sono stati origine e/o punto terminale di un segmento.
Esempio: $n=2$-->$l=1$, $n=3$-->$l=3$, $n=4$-->$l=7$,...
Qual'è la regola generale?
Sia data una striscia di carta suddivisa in $n$ caselle quadrate ($n$ naturale positivo $>=2$). La distanza tra due caselle contigue è per definizione unitaria. Tutte le caselle sono numerate progressivamente, da $1$ ad $n$.
Il gioco è il seguente, massimizzare la lunghezza aggregata ($l$)degli $n-1$ segmenti che congiungono i centri di tutte le $n$ caselle, partendo da uno di essi a piacere e tracciando il segmento che termina in un'altra casella, considerare dunque quest'ultima casa come punto di partenza per il secondo segmento e farlo terminare in una delle restanti $22$ caselle ancora libere. Il gioco termina i centri di tutte le case sono stati origine e/o punto terminale di un segmento.
Esempio: $n=2$-->$l=1$, $n=3$-->$l=3$, $n=4$-->$l=7$,...
Qual'è la regola generale?
Risposte
Molto bello questo, vediamo se ho capito.
Faccio il caso $n=8$ ed $n=9$ per comodità:
e scusa per il pessimo design
Allora come visto nella figura il problema si riconduce nel contare da quante stanghette è attraversata ogni casella e sommare tutto. Considero una casella attraversata da una certa stanghetta anche se si tratta dell'origine o della fine. E alla fine chiaramente devo sottrarre $n-1$ al risultato finale perchè l'origine e la fine vanno contate una sola volta ai fini della distanza.
Ora.. come ho evidenziato in figura in rosso, si nota che le caselle ai bordi possono essere attraversate da massimo $2$ stanghette, quelle adiacenti verso l'interno da $4$, quelle ancora più interne da $6$ e così via..
Questo lo si può giustificare (in teoria per induzione) col fatto che una stanghetta che attraversa una casella al bordo deve avere necessariamente origine o fine in essa (ovvero $2$ possibilità)... una stanghetta che attraversa una casella adiacente al bordo deve avere necessariamente origine e fine in essa oppure origine e fine in quella al bordo quindi siamo a $4$.... Continuando così andando via via verso l'interno si nota che questo valore aumenta sempre di $2$ fino a raggiungere il massimo numero di stanghette che possono attraversare una casella (ovvero $n-1$).
(considerando una casella di posto $k$ rispetto al bordo più vicino ad essa, i possibile estremi delle stanghette che la attraversano sono $2k$).
Divido in casi:
n pari:
In questo caso quindi si tratta di sommare quindi tutti i massimi per ogni casella e sottrarre $n-1$
Ottengo come somma generica (senza mostrare i conti) $n(n/2)-1$
Per dimostrare che quel massimo è effettivamente ottenibile basta partire da una casella centrale, andare verso sinistra, arrivare in fondo a destra e ripetere quest'operazione arrivando di volta in volta fin dove possibile come si vede in figura..
(suvvia.. qua si verifica facilmente che funziona xD)
n dispari:
Si aggiunge una sottigliezza... Il massimo teorico non è ottenibile poichè si formano $3$ caselle centrali col valore $n-1$. Ora se tutte e $3$ fossero attraversate da $n-1$ segmenti (il massimo), allora la casella centrale non dovrebbe contenere nessun inizio e nessuna fine, poichè se contenesse un inizio o una fine allora una delle due caselle adiacenti non avrebbe il massimo dei segmenti non essendo attraversata dal segmento che inizia o finisce al centro. Quindi il massimo possibile stavolta diminuisce di $1$ rispetto a quello ottenuto con la precedente strategia. Ed è $(n^2-1)/2 -1$ (ometto i conti anche qui).
Per dimostrare che è davvero ottenibile, stessa strategia di prima, parto dalla casella centrale più a destra, vado verso sinistra, torno verso destra e così via arrivando di volta in volta fin dove riesco.
Faccio il caso $n=8$ ed $n=9$ per comodità:
e scusa per il pessimo design
Allora come visto nella figura il problema si riconduce nel contare da quante stanghette è attraversata ogni casella e sommare tutto. Considero una casella attraversata da una certa stanghetta anche se si tratta dell'origine o della fine. E alla fine chiaramente devo sottrarre $n-1$ al risultato finale perchè l'origine e la fine vanno contate una sola volta ai fini della distanza.
Ora.. come ho evidenziato in figura in rosso, si nota che le caselle ai bordi possono essere attraversate da massimo $2$ stanghette, quelle adiacenti verso l'interno da $4$, quelle ancora più interne da $6$ e così via..
Questo lo si può giustificare (in teoria per induzione) col fatto che una stanghetta che attraversa una casella al bordo deve avere necessariamente origine o fine in essa (ovvero $2$ possibilità)... una stanghetta che attraversa una casella adiacente al bordo deve avere necessariamente origine e fine in essa oppure origine e fine in quella al bordo quindi siamo a $4$.... Continuando così andando via via verso l'interno si nota che questo valore aumenta sempre di $2$ fino a raggiungere il massimo numero di stanghette che possono attraversare una casella (ovvero $n-1$).
(considerando una casella di posto $k$ rispetto al bordo più vicino ad essa, i possibile estremi delle stanghette che la attraversano sono $2k$).
Divido in casi:
n pari:
In questo caso quindi si tratta di sommare quindi tutti i massimi per ogni casella e sottrarre $n-1$
Ottengo come somma generica (senza mostrare i conti) $n(n/2)-1$
Per dimostrare che quel massimo è effettivamente ottenibile basta partire da una casella centrale, andare verso sinistra, arrivare in fondo a destra e ripetere quest'operazione arrivando di volta in volta fin dove possibile come si vede in figura..
(suvvia.. qua si verifica facilmente che funziona xD)
n dispari:
Si aggiunge una sottigliezza... Il massimo teorico non è ottenibile poichè si formano $3$ caselle centrali col valore $n-1$. Ora se tutte e $3$ fossero attraversate da $n-1$ segmenti (il massimo), allora la casella centrale non dovrebbe contenere nessun inizio e nessuna fine, poichè se contenesse un inizio o una fine allora una delle due caselle adiacenti non avrebbe il massimo dei segmenti non essendo attraversata dal segmento che inizia o finisce al centro. Quindi il massimo possibile stavolta diminuisce di $1$ rispetto a quello ottenuto con la precedente strategia. Ed è $(n^2-1)/2 -1$ (ometto i conti anche qui).
Per dimostrare che è davvero ottenibile, stessa strategia di prima, parto dalla casella centrale più a destra, vado verso sinistra, torno verso destra e così via arrivando di volta in volta fin dove riesco.
Complimenti davvero per la velocità... per giungere alla stessa conclusione ho impiegato varie ore (e non ero neppure certo che la soluzione fosse corretta) 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo