Vai al contenuto

Qualche triangolo

11 ottobre 2012

Moltiplicare quadrati magici

Un quadrato magico, lo ricordiamo bene, è un griglia come questa

dove appaiono tutti i numeri consecutivi da 1 fino al completamento dei posti. La “magia” scaturisce naturalmente dalla somma di ogni riga, di ogni colonna e di ogni diagonale, che è sempre 15.

Stiamo parlando di magia, quindi sarà bene dotarci di un gergo particolare che escluda i non iniziati. Allora il lato del quadrato lo chiamiamo ordine. Se l’ordine è un generico n, il quadrato conterrà tutti i numeri da 1 a n^2. La somma complessiva, (1+n^2)\frac{n^2}{2}, deve essere ripartita equamente su ciascuna delle n righe, perciò la costante magica è c_n = (1+n^2)\frac{n}{2}. Nel nostro esempio, c_3 = 15.

Il quadrato magico di ordine 3 è unico, a meno di rotazioni e riflessioni. Costruirlo a partire da un foglio bianco è fattibile per tentativi in tempi brevissimi. Ma quanto ci vuole ad ordinare i numeri da 1 a 16 in un quadrato 4 \times 4 in modo che la somma di ogni riga, colonna e diagonale dia sempre 34? Questa volta ci sono svariate centinaia di soluzioni diverse, ma trovarne una a mano potrebbe rivelarsi frustrante.

Esistono semplici algoritmi che permettono di costruire quadrati grandi col minimo sforzo. Quello che segue l’avevo ricavato autonomamente, ma altri ci avevano già pensato. Così capita, ma neppure loro si sono arricchiti. In realtà il metodo è velocissimo e anche facile da ricordare e applicare, ma forse complicato da descrivere.

L’algoritmo opera una specie di prodotto tra due quadrati magici di partenza, che chiameremo guidamodulo. Come guida usiamo il nostro 3\times 3, e consideriamo il percorso che segue l’ordine dei numeri disposti al suo interno:

Ripetiamo il modulo in ciascuno dei posti visitati, aggiungendo a tutti i numeri del modulo una costante per mantenere la numerazione progressiva. Più per pigrizia che per altro, usiamo come modulo lo stesso quadrato usato come guida e vediamo come appare dopo averlo riportato le prime tre volte:

Una volta capito, il procedimento permette direttamente di scrivere il quadrato finale, che ha per ordine il prodotto degli ordini della guida e del modulo. Non è niente male, scrivere il quadrato magico di ordine 9 senza fare nessun calcolo! La sua costante magica è 369, provare per credere.

Da qui ad un quadrato di lato 27, o 81, o… basta solo avere sufficiente inchiostro o byte.

Vediamo una breve giustificazione del perché l’algoritmo produce il risultato desiderato. Sia N il quadrato di ordine n che usiamo come modulo e M il quadrato di ordine m che usiamo come guida. Le due costanti magiche sono c_n e c_m.

Seguendo l’algoritmo costruiamo un nuovo quadrato. Calcoliamo quanto vale la somma degli elementi della generica riga x, dove evidentemente lo stesso ragionamento vale per le colonne e per le diagonali. Dunque, questa riga x si costruisce usando una particolare riga del modulo N ed una particolare riga della guida M. I valori di queste due righe siano a_1, a_2, \ldots, a_n e b_1, b_2, \ldots, b_m.

Quando usiamo il modulo con il primo numero b_1, stiamo riportando tutti i valori a_1, a_2, \ldots, a_n, di somma c_n. Dobbiamo però tenere conto che questi numeri proseguono la numerazione generale del quadrato risultante, dove saranno già presenti (b_1-1) moduli, ciascuno con n^2 numeri. Questo sfasamento sarà ripetuto per ognuno degli n numeri del modulo, quindi (b_1-1)n^2 \cdot n + c_n sarà la somma degli elementi di x per il primo modulo della riga.

Si tratta adesso di sommare per tutti gli m moduli che interessano la nostra riga:

n^3(b_1-1) + c_n + n^3(b_2 - 1) + c_n + \ldots + n^3 (b_m - 1) + c_n =

n^3 (\sum b_j - m) + m c_n = n^3 (c_m - m) + m c_n.

Siamo arrivati alla fine. Facciamo ancora alcuni conti sostituendo le espressioni per le costanti magiche per avere una somma di

n^3 \frac{1+m^2}{2}m - mn^3 + m\frac{1+n^2}{2}n = \left(1 + n^2m^2\right)\frac{nm}{2} = c_{nm}

che riconosciamo essere proprio la costante magica di un quadrato n\times m.

Moltiplicare forme

Invece di tabelle di numeri, possiamo replicare l’algoritmo con tabelle di quadrati accesi e spenti. Il modulo verrà ripetuto, come se fosse uno stampino, in corrispondenza di ogni quadrato accesso presente nella guida. Non abbiamo più l’onere di dover rispettare una numerazione, e si può giocare liberamente. Dell’algoritmo resta solo l’ossatura, una specie di moltiplicazione tra tabelle di quadrati o, se consideriamo il disegno tracciato dai quadrati accesi, una specie di moltiplicazione tra forme.

Si vede subito che questa operazione non è commutativa. Se ad esempio moltiplicassimo un domino ed un trimino ad L, troveremmo due risultati diversi a seconda che sia il domino od il trimino ad essere usato come modulo.

Un singolo quadrato acceso rappresenta l’elemento neutro di questa moltiplicazione, perché lascia inalterata l’altra figura. Questo, sia che venga usato come guida che come modulo.

L’operazione non è invertibile perché non si possono moltiplicare due figure assieme per ottenere un solo quadrato acceso.

L’operazione sembra proprio essere associativa, e conseguentemente l’insieme delle figure, dotato di tale operazione, dovrebbe essere un monoide. Dimostrare o confutare l’associatività di questa operazione potrebbe richiedere formalismo noioso, anche se forse basterebbe solo qualche considerazione illuminata. Questa volta però cedo completamente il passo al lettore volenteroso.

Moltiplichiamo due domini tra di loro. Se uno è verticale e l’altro orizzontale, il risultato sarà un quadrato 2\times 2. Se i due domini hanno lo stesso orientamento, il risultato sarà una striscia di quattro quadrati. In generale n domini con lo stesso orientamento porteranno ad una striscia di 2^n quadrati. Non molto interessante.

Per avere un risultato interessante, non serve fare troppa strada. Prendiamo in esame il trimino ad L, e moltiplichiamolo successivamente per altri trimini a lui identici. Ecco cosa salta fuori:

Continuo? Massì, ancora un po’…

OK, adesso la smetto. Che bella cosa, però, i computer.

Qualche triangolo

Quella che abbiamo trovato è la celebre figura del triangolo di Sierpinski! E’ un’immagine frattale, perché ogni sua parte riproduce il tutto. In realtà esiste la versione continua del triangolo, dove iterativamente si divide il triangolo equilatero di partenza in quattro triangoli uguali e si leva quello centrale. Quella che abbiamo incontrato noi è la versione discreta, che solitamente si costruisce con un procedimento che ricorda un automa cellulare.

Il triangolo di Sierpinski si costruisce a partire da un singolo quadrato acceso. Successivamente si aggiungono quadrati, accesi o spenti, secondo le sei regole riportate in figura, dove per comodità la punta del triangolo è stata ruotata. Due regole sono in realtà casi particolari e possono essere trattate singolarmente: sotto un quadrato acceso e uno spazio vuoto “nasce” un quadrato acceso. Si formano così i due lati esterni del triangolo.

A parte queste due regole speciali, lo stato di un quadrato dipende unicamente dallo stato dei due quadrati sopra di lui: questo acceso se quelli hanno stati diversi, questo spento se quelli hanno stati uguali. Concettualmente è lo stesso della regola dei segni per il prodotto, o la regola di parità per la somma. Infatti il triangolo viene spesso presentato colorando in modo diverso gli elementi pari e dispari del triangolo di Pascal/Tartaglia, che sono costruiti per somma.

Il metodo di creazione del triangolo applicando le quattro regole può essere visto come un automatismo cellulare, interpretando i quadrati accesi come cellule vive. Ogni riga rappresenta l’intera popolazione di cellule, e scorrendo il triangolo dall’alto in basso è possibile vederne l’evoluzione.

E’ curioso che l’automa cellulare produca lo stesso risultato del prodotto tra figure sopra descritto. Si può però facilmente notare che applicare il prodotto per il trimino L ad una figura che rispetta le regole dell’automa cellulare porta ad un’altra figura che rispetta le regole.

Il triangolo può anche essere visto come una rappresentazione visuale della scomposizione di 3^n in fattori primi. Per vederlo meglio, conviene partire da un vertice del triangolo, che contiene il trimino L, rappresentazione del numero 3. Dopo un quadrato vuoto, è possibile trovare altre due copie del trimino, e tutte insieme sono una rappresentazione di 3^2. Lo stesso gruppo di trimini si presenta, identico, altre due volte, così da formare un gruppo più grande rappresentante, in questo caso, 3^3, e così di seguito.

Strutturalmente, osserviamo che si forma una colonna centrale di triangoli sempre più grande fatti di quadrati spenti. Il primo “triangolo” è solo il quadratino spento subito sotto quello di partenza. Segue un triangolo di area 6, e così via. Guardando i triangoli spenti centrali, si vede che sopra ognuno di questi se ne appoggiano altri di dimensioni diverse.

Ad esempio, sul terzo triangolo centrale si appoggiano tre triangoli. Sopra quale triangolo centrale se ne appoggiano più di 1000?

Qualche triangolo


Sia k il numero di riga dell’n-esima riga del triangolo di Pascal ad essere costituita, oltre che dagli 1 esterni, solo da numeri pari. Qual è il minimo n tale che k-2 contiene almeno 1000 numeri pari?

About these ads
2 commenti leave one →
  1. juhan permalink
    11 ottobre 2012 9:40 am

    Devo verificare su un’altra macchina, con un altro browser ma Firefox 16 su Ubuntu non mi visualizza le formule LaTeX. Peccato perché il post è bello (come al solito).

    • 11 ottobre 2012 9:28 pm

      Ti ringrazio per la segnalazione (e per il complimento). Adesso dovrebbe essere tutto a posto: banalmente si erano persi dei backslash che hanno fatto saltare i comandi LaTeX. Certo che se uno non può più fidarsi nemmeno del copia-incolla…
      La versione 15 di FF mi chiede di essere aggiornata, ma ho quasi paura!

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

%d blogger cliccano Mi Piace per questo: