Problema 4 SNS 2015

[tommy1996q]

Posto la mia soluzione al quarto problema, come per gli altri se avete consigli, domande, se vedete errori, se avete soluzioni alternative ecc. non esitate a scrivere!

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.

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.

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

[coleridge1]

"maCrobo":A questo punto avrei due quadrati magici distinti per una sola cella

Ma i due quadrati che ottieni non sono più magici: cambiano le somme su quella riga e su quella colonna.

[Macellaro]

Comunque, se gli unici numeri non esprimibili come media di due valori distinti sono 0 ed 1 ed un quadrato magico deve soddisfare questa proprietà per ogni cella, ne segue che le celle devono contenere per forza uno 0 oppure un 1.
Detto questo uno pensa a quanti 0 ed 1 possono effettivamente essere contenuti in un q. m. puro per soddisfare la condizione su righe e colonne.

[coleridge1]

Se si possono usare solo i numeri tra 0 e 1, gli unici numeri che non sono media di due numeri distinti sono 0 e 1.
Dunque un quadrato che non è media di due quadrati (anche non magici) distinti è formato solo da 0 e 1.
Ma un quadrato magico che non è media di due quadrati magici?

[Macellaro]

Dunque un quadrato che non è media di due quadrati (anche non magici) distinti è formato solo da 0 e 1.

Il tutto è valido nell'insieme $\{ Quadrati \quad qualunque \}$, dove righe e colonne possono soddisfare la condizione di quadrato magico oppure no, perché a questo punto la differenza tra un quadrato magico e uno non magico sta nel fare in modo che la somma dei termini su ogni riga sia pari a 1 e lo stesso valga per ogni colonna.
A questo punto $\{ Quadrati \quad magici \}$ è un sottoinsieme. Se è valido per l'insieme che lo contiene, sarà vero anche per il sottoinsieme.

[coleridge1]

"maCrobo":Se è valido per l'insieme che lo contiene, sarà vero anche per il sottoinsieme.

Questo in generale è falso. Ad esempio l'equazione $x+1=0$ ha soluzione nell'insieme $\mathbb{Z}$ ma non nel sottoinsieme $\mathbb{N}$.

Tu stai dicendo che se in un insieme posso trovare un $Q_1$ e un $Q_2$ che hanno media $Q$, allora anche in un insieme più piccolo posso trovare ancora un $Q_1$ e un $Q_2$ che hanno media $Q$... al massimo è vero il contrario.