Catena di torri

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Catena di torri

Messaggio da giobimbo »

Abbiamo una scacchiera mxn (m>=n) e t torri, con t numero pari. Disponiamo i pezzi in modo che ogni torre ne attacchi altre 2, una orizzontalmente e una verticalmente, in modo che una qualsiasi di esse con t mosse possa mangiare tutte le altre e tornare alla casella di partenza. Nell’esempio sotto con scacchiera 8x5 la torre 1 mangerebbe la 2, poi la 4, la 5, la 3 e infine la 7 (poi con 7 passi torna da dov’era partita); abbiamo la catena:
1-2, 2-4, 4-5, 5-3, 3-7, 7-1.

Catena di torri.png
Catena di torri.png (2.39 KiB) Visto 2271 volte
Il numero di ogni torre corrisponde al numero di passi, di caselle da percorrere nel senso della catena, per mangiare la torre successiva. La 1 per mangiare la 2 deve fare 1 passo, la 2 per mangiare la 4 deve fare 2 passi, la 4 per mangiare la 5…

Problema. Disporre 12 torri su una scacchiera mxn in modo che:
1) le torri formino una catena in cui i numeri di passi sono tutti diversi
2) il prodotto mxn sia il più piccolo possibile.

Quelo
Livello 7
Livello 7
Messaggi: 894
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Catena di torri

Messaggio da Quelo »

Per il momento il miglior risultao a cui sono arrivato è 13x8
Domani vi metto il ragionamento
Allegati
Catena di torri.png
Catena di torri.png (11.35 KiB) Visto 2171 volte
[Sergio] / $17$

Quelo
Livello 7
Livello 7
Messaggi: 894
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Catena di torri

Messaggio da Quelo »

Poniamo $m \ge n$ e $t=\{t_1,...,t_{12}\}$ l'insieme delle torri
Risulterà $m \ge t_{12} + 1$ in quanto a partire dalla torre con valore più elevato dovranno essere compiuti $t_{12}$ passi per raggiungere la torre successiva
Poiché una torre $t_n$ impegna $n$ caselle su una riga o una colonna, ignorando le sovrapposizioni sarà $\displaystyle m \cdot n \ge S_t=\sum_{n=t_1}^{t_{12}}t_n$
Per cui $\displaystyle n \ge \frac{S_t}{m}$

Cercando di minimizzare mxn scegliamo t = {1,...,12} e avremo che 13x6 il limite inferiore per la scacchiera

Affinché il percorso si chiuda, i passi verso destra devono corrispondere ai passi verso sinistra e lo stesso per il basso con l'alto.
m non potrà essere minore di 13, quindi dobbiamo minimizzare n e per farlo cercheremo di mettere tutte le torri di valore più alto in modo che muovano sul lato lungo, mentre quelle di valore più basso che muovano sul lato corto.
La soluzione ideale sarebbe {1,...,6} e {7,...,12} che porterebbe comunque la scacchiera a 13x7, nuovo limite inferiore.

Purtroppo le somme da 1 a 6 e da 7 a 12 sono dispari, quindi non è possibile compensare i movimenti destra-sinistra e basso-alto.
Scambiamo il 6 con il 7 e otteniamo t={1,2,3,4,5,7,6,8,9,10,11,12}, $\displaystyle \sum_{n=t_1}^{t_6}=22$ e $\displaystyle \sum_{n=t_7}^{t_{12}}=56$
Che possiamo dividere (ad esempio) in:
Verso destra 6+10+12=28
Verso sinistra 8+9+11=28
Verso il basso 7+3+1=11
Verso l'alto 2+4+5=11

Disponendo opportunamente le torri si ottiene lo schema in figura con scacchiera mxn = 13x8
Ultima modifica di Quelo il gio lug 08, 2021 5:36 pm, modificato 1 volta in totale.
[Sergio] / $17$

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Catena di torri

Messaggio da giobimbo »

Bravissimo! La mia scacchiera minima era di 13x11... Complimenti.

Rispondi