Esercizio 4:
Un quadrato magico è una griglia n×n in cui ogni cella contiene un numero reale compreso tra 0 e 1 e tale che la somma dei numeri di ogni riga e di ogni colonna sia 1. La media di due quadrati magici A e B della stessa dimensione è una griglia che si ottiene facendo la media aritmetica cella per cella dei quadrati magici di partenza. Un quadrato magico è puro se non si può esprimere come media di due quadrati magici distinti. Dimostra che un quadrato magico è puro se e solo se contiene solamente 0 e 1.
Testo nascosto, fai click qui per vederlo
consideriamo 2 quadrati magici definiti in tal modo. Chiamiamo gli elementi di una qualsiasi riga o colonna del primo $a(i)$, mentre del secondo li chiamiamo $b(i)$. Possiamo costruire un altro quadrato magico facendo la media casella per casella di $a(i)$ e $b(i)$, ottenendo che l'elemento generico $c(1)$ sarà:
$c(i)=(a(i)+b(i))/2$
Ma allora possiamo fare nuovamente la media fra c(i) e a(i) e ottenere un altro quadrato magico. Poi possiamo ripetere la cosa quante volte vogliamo ottenendo sempre quadrati magici. L' n-esimo quadrato magico ottenuto in questo modo avrà come elemento generico $d(i)$ il valore:
$d(i)=((2^(n)-1)a(i)+b(i))/(2^n)$
notiamo che una casella generica darò come valore 0 se e solo se $a(i)=b(i)=0$, mentre notiamo (anche dalla prima equazione) che affinché la media di due numeri reali compresi fra 0 e 1 sia 1, allora $a(i)=b(i)=1$.
Dunque affinché la media di due quadrati perfetti sia un quadrato perfetto con solo 0 e 1 bisogna avere che per ogni casella $a(i)=b(i)=0$ oppure $a(i)=b(i)=1$. Ciò significa che per ottenere tale quadrato magico come media bisognerebbe fare la media del quadrato magico con sé stesso, e quindi i 2 quadrati non possono essere distinti. Per essere pignoli, mostriamo che un quadrato magico puro esiste sempre per ogni lato k in quanto un semplicissimo quadrato magico puro è la matrice unità di rango k.
Dimostriamo ora che i quadrati magici puri sono solo questi. Manipoliamo un po' la seconda equazione e otteniamo che:
$d(i)=a(i)+(1/2^n)(b(i)-a(i))$
Ponendo d(i) uguale a un generico numero reale (compreso tra 0 e 1 ovviamente) q, abbiamo che:
$q=a(i)+ (1/2^n)(b(i)-a(i))$, da cui assumendo un valore assegnato per q otteniamo:
$b(i)=(2^n)(q-a(i))+a(i)$
Tale valore è però accettabile se e solo se $0<(2^n)(q-a(i))+a(i)<1$
Manipolando ulteriormente tale equazione otteniamo che:
$((2^n-1)/2^n)a(i)<=q<=((2^n-1)/2^n)a(i)+1/2^n$
Visto che la prima equazione è sempre minore della seconda (per via del $+1/2^n$) e che operiamo nei numeri reali, (un insieme denso) è sempre possibile trovare dei valori di n e di a(i) per i quali le due equazioni contengono il valore di q richiesto, a meno che esso non sia 1 o 0. (Ciò lo abbiamo già dimostrato, ma si vede ancora meglio dalle equazioni che gli unici valori per cui q=0 e q=1 sono a(i)=0 e a(i)=1, con conseguente b(i)=0 e b(i)=1).
Ora si potrebbe obiettare (giustamente aggiungerei) che scegliendo "a caso" $a(i)$ poi il quadrato magico di elementi $a(i)$ non sarebbe più un quadrato magico. Ma il problema chiede di dimostrare che è possibile fare una cosa del genere, che scegliendo opportunamente (non ci interessa come, lo ripeto) un certo valore di $a(i)$ i conti tornano, per così dire. Dimostrare ciò è semplice. Consideriamo il caso semplice $n=1$. Allora:
$(1/2)a(i)<=q<=(1/2)a(i)+1/2$ da cui:
$2(q-1/2)<=a(i)<=2q$
Basta vedere che la somma lungo una riga di $k$ caselle vale come minimo 0 (in realtà l'espressione a sinistra ci dà un valore negativo, e ciò può essere spiegato col fatto che se q è maggiore di 1/2 allora anche a deve essere superiore a un certo valore, altrimenti b(i) dovrebbe essere >1) e al massimo 2 (sommiamo tutti i q della riga e visto che $q=d(i)$ la loro somma sarà 1).
Visto che la somma di tutti gli a(i) potrà assumere tutti i valori tra 0 e 2, potrà assumere anche valore 1.
Per b(i) non ci sono problemi, basta definirlo come $b(i)=2q-a(i)$, e sarà sempre compreso tra 0 e 1, e la sua somma su ogni riga varrà 2-1=1.
$c(i)=(a(i)+b(i))/2$
Ma allora possiamo fare nuovamente la media fra c(i) e a(i) e ottenere un altro quadrato magico. Poi possiamo ripetere la cosa quante volte vogliamo ottenendo sempre quadrati magici. L' n-esimo quadrato magico ottenuto in questo modo avrà come elemento generico $d(i)$ il valore:
$d(i)=((2^(n)-1)a(i)+b(i))/(2^n)$
notiamo che una casella generica darò come valore 0 se e solo se $a(i)=b(i)=0$, mentre notiamo (anche dalla prima equazione) che affinché la media di due numeri reali compresi fra 0 e 1 sia 1, allora $a(i)=b(i)=1$.
Dunque affinché la media di due quadrati perfetti sia un quadrato perfetto con solo 0 e 1 bisogna avere che per ogni casella $a(i)=b(i)=0$ oppure $a(i)=b(i)=1$. Ciò significa che per ottenere tale quadrato magico come media bisognerebbe fare la media del quadrato magico con sé stesso, e quindi i 2 quadrati non possono essere distinti. Per essere pignoli, mostriamo che un quadrato magico puro esiste sempre per ogni lato k in quanto un semplicissimo quadrato magico puro è la matrice unità di rango k.
Dimostriamo ora che i quadrati magici puri sono solo questi. Manipoliamo un po' la seconda equazione e otteniamo che:
$d(i)=a(i)+(1/2^n)(b(i)-a(i))$
Ponendo d(i) uguale a un generico numero reale (compreso tra 0 e 1 ovviamente) q, abbiamo che:
$q=a(i)+ (1/2^n)(b(i)-a(i))$, da cui assumendo un valore assegnato per q otteniamo:
$b(i)=(2^n)(q-a(i))+a(i)$
Tale valore è però accettabile se e solo se $0<(2^n)(q-a(i))+a(i)<1$
Manipolando ulteriormente tale equazione otteniamo che:
$((2^n-1)/2^n)a(i)<=q<=((2^n-1)/2^n)a(i)+1/2^n$
Visto che la prima equazione è sempre minore della seconda (per via del $+1/2^n$) e che operiamo nei numeri reali, (un insieme denso) è sempre possibile trovare dei valori di n e di a(i) per i quali le due equazioni contengono il valore di q richiesto, a meno che esso non sia 1 o 0. (Ciò lo abbiamo già dimostrato, ma si vede ancora meglio dalle equazioni che gli unici valori per cui q=0 e q=1 sono a(i)=0 e a(i)=1, con conseguente b(i)=0 e b(i)=1).
Ora si potrebbe obiettare (giustamente aggiungerei) che scegliendo "a caso" $a(i)$ poi il quadrato magico di elementi $a(i)$ non sarebbe più un quadrato magico. Ma il problema chiede di dimostrare che è possibile fare una cosa del genere, che scegliendo opportunamente (non ci interessa come, lo ripeto) un certo valore di $a(i)$ i conti tornano, per così dire. Dimostrare ciò è semplice. Consideriamo il caso semplice $n=1$. Allora:
$(1/2)a(i)<=q<=(1/2)a(i)+1/2$ da cui:
$2(q-1/2)<=a(i)<=2q$
Basta vedere che la somma lungo una riga di $k$ caselle vale come minimo 0 (in realtà l'espressione a sinistra ci dà un valore negativo, e ciò può essere spiegato col fatto che se q è maggiore di 1/2 allora anche a deve essere superiore a un certo valore, altrimenti b(i) dovrebbe essere >1) e al massimo 2 (sommiamo tutti i q della riga e visto che $q=d(i)$ la loro somma sarà 1).
Visto che la somma di tutti gli a(i) potrà assumere tutti i valori tra 0 e 2, potrà assumere anche valore 1.
Per b(i) non ci sono problemi, basta definirlo come $b(i)=2q-a(i)$, e sarà sempre compreso tra 0 e 1, e la sua somma su ogni riga varrà 2-1=1.
P.S. Non sono sicuro che sia il quarto, semmai scrivete nei commenti il numero e poi lo cambio, ringrazio poi l'utente coleridge che mi ha fatto notare un'incompletezza nell'ultima parte del problema
