Problema 4 SNS 2015
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.
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
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.
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
Risposte
Nella seconda parte della dimostrazione hai dimenticato che i quadrati devono essere magici.
Per inciso, non vedo il vantaggio di calcolare \(\displaystyle n \) medie anziché una sola.
Per inciso, non vedo il vantaggio di calcolare \(\displaystyle n \) medie anziché una sola.
Nella seconda parte ho manipolato l'espressione di $d(i)$ che avevo già dimostrato essere sempre magico. Poi ho posto che si voglia avere come media un certo valore $q$, così che $d(i)=q$. Ho ricavato poi $b(i)$ e ho posto tale valore compreso tra 0 e 1, come imposto dal problema. Manipolando ancora ottengo la disequazione finale.
Il fatto che i quadrati devono essere magici è già compreso nella prima equazione per trovare d(i). Non l'ho scritto ma si vede che facendo la sommatoria dei termini d(i), a(i) e b(i) su una riga o su una colonna il risultato torna 1. Poi è scontato che se voglio un certo quadrato magico con certi elementi devo prima verificare che sia magico. Di certo non potrò ottenerne uno con somme negative o maggiori di 1 altrimenti, la somma totale deve essere 1 e non variare.
Le medie n-esime in effetti non erano necessarie, le ho messe per cercare di "generalizzare" la cosa e mostrare che un elemento di un quadrato magico può sempre essere ottenuto per certi valori di a(i) e b(i), al più con un certo numero di medie consecutive. Sinceramente avevo pensato al teorema dei 2 carabinieri per mostrare che per certi n e a(i) le due espressioni tendono allo stesso limite q, ma effettivamente è una complicazione inutile.
Il fatto che i quadrati devono essere magici è già compreso nella prima equazione per trovare d(i). Non l'ho scritto ma si vede che facendo la sommatoria dei termini d(i), a(i) e b(i) su una riga o su una colonna il risultato torna 1. Poi è scontato che se voglio un certo quadrato magico con certi elementi devo prima verificare che sia magico. Di certo non potrò ottenerne uno con somme negative o maggiori di 1 altrimenti, la somma totale deve essere 1 e non variare.
Le medie n-esime in effetti non erano necessarie, le ho messe per cercare di "generalizzare" la cosa e mostrare che un elemento di un quadrato magico può sempre essere ottenuto per certi valori di a(i) e b(i), al più con un certo numero di medie consecutive. Sinceramente avevo pensato al teorema dei 2 carabinieri per mostrare che per certi n e a(i) le due espressioni tendono allo stesso limite q, ma effettivamente è una complicazione inutile.
Non ho capito, puoi davvero manipolare $a(i)$ a piacimento senza guardare cosa succede al resto del quadrato?
Probabilmente sono un po' lento io, ma ancora non capisco: mi sembra che per dimostrare che Q non è puro tu stia aggiungendo tra le ipotesi che Q è la media di due quadrati magici...
Allora, io ho posto $q=d(i)$ dove $d(i)$ è la media di 2 quadrati magici per come l'abbiamo definito (in realtà sarebbe la media fatta più volte nel modo che ho descritto, ma lasciamo stare). Manipolando l'equazione nella maniera che hai visto ottengo che $((2^n-1)/2^n)a(i)
Praticamente dico: se ho un quadrato magico con non soli 0 e 1, allora posso costruirlo come media dia altri quadrati magici
Allora vediamo che per $q=0$ abbiamo necessariamente $a(i)=0 e b(i)=0$, e stessa cosa per $q=1$, (comunque questa cosa si vede meglio nella prima parte, o per n=1) il che ci porta a concludere la tesi del problema, cioè che quadrati magici con solo 0 e 1 possono essere ottenuti, per così dire, solo come media di 2 quadrati magici identici a loro stessi (quindi non distinti).
Se q è diverso da 0 e 1, invece, può essere ottenuto per infiniti valori di $a(i)$ (ripeto: lavoriamo in un insieme denso, l'intervallo in cui a(i), per certi valori di n, verifica la disequazione, sarà piccolo a piacere, ma conterrà SEMPRE infiniti numeri reali).
Provo a mostrartelo con un esempio semplice, che poi è quello che mi avevi suggerito, cioè per $n=1$.Allora:
$(1/2)a(i)<=q<=(1/2)a(i)+1/2$
Vedi da solo che problemi insorgono solo se $q=0 o q=1$, mentre per q compreso fra 0 e 1 abbiamo che l'intervallo in cui $a(i)$ soddisfa le nostre richieste è:
$2(q-1/2)<=a(i)<=2q$
E quindi infiniti valori di $a(i)$. Ora potresti obiettare (giustamente aggiungerei) che scegliendo "a caso" $a(i)$ poi il quadrato magico di elementi $a(i)$ non sarebbe più un quadrato magico, e avresti ragione. 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. Basta vedere che la somma minima 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.
Praticamente dico: se ho un quadrato magico con non soli 0 e 1, allora posso costruirlo come media dia altri quadrati magici
Allora vediamo che per $q=0$ abbiamo necessariamente $a(i)=0 e b(i)=0$, e stessa cosa per $q=1$, (comunque questa cosa si vede meglio nella prima parte, o per n=1) il che ci porta a concludere la tesi del problema, cioè che quadrati magici con solo 0 e 1 possono essere ottenuti, per così dire, solo come media di 2 quadrati magici identici a loro stessi (quindi non distinti).
Se q è diverso da 0 e 1, invece, può essere ottenuto per infiniti valori di $a(i)$ (ripeto: lavoriamo in un insieme denso, l'intervallo in cui a(i), per certi valori di n, verifica la disequazione, sarà piccolo a piacere, ma conterrà SEMPRE infiniti numeri reali).
Provo a mostrartelo con un esempio semplice, che poi è quello che mi avevi suggerito, cioè per $n=1$.Allora:
$(1/2)a(i)<=q<=(1/2)a(i)+1/2$
Vedi da solo che problemi insorgono solo se $q=0 o q=1$, mentre per q compreso fra 0 e 1 abbiamo che l'intervallo in cui $a(i)$ soddisfa le nostre richieste è:
$2(q-1/2)<=a(i)<=2q$
E quindi infiniti valori di $a(i)$. Ora potresti obiettare (giustamente aggiungerei) che scegliendo "a caso" $a(i)$ poi il quadrato magico di elementi $a(i)$ non sarebbe più un quadrato magico, e avresti ragione. 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. Basta vedere che la somma minima 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.
Scusa se sono poco chiaro ma mi sa che l'ho fatta molto più complicata di quanto non sia, forse un utente più esperto te la spiega e la dimostra in modo migliore e più semplice
Dato un quadrato magico $a$ $n \times n$ che non abbia solo $0$ e $1$, il problema diventa equivalente a costruire un quadrato $b$ delle stesse dimensioni tali che:
- se $a(i)$ vale $0$ o $1$ allora $b(i)=0$ (per ogni indice $i$)
- la somma su ogni riga e colonna di $b$ deve essere $0$
- $b$ non abbia tutte le caselle nulle
Ma magari così diventa più difficile di quello che avevi in mente, non ho capito il tuo procedimento
- se $a(i)$ vale $0$ o $1$ allora $b(i)=0$ (per ogni indice $i$)
- la somma su ogni riga e colonna di $b$ deve essere $0$
- $b$ non abbia tutte le caselle nulle
Ma magari così diventa più difficile di quello che avevi in mente, non ho capito il tuo procedimento
Ehm.... mi sto confondendo anche io ora! Comunque io volevo solo far vedere che gli unici problemi si avevano per ottenere 0 e 1 come media, mentre se si volevano valori diversi c'era almeno una coppia di quadrati magici che risolvevano il problema. Considerare n medie è stata una complicazione inutile, devo ammettere, ma se si pone n=1 sempre il procedimento dovrebbe tornare....
Credo che il nocciolo del problema stia proprio nel dimostrare che è possibile scegliere gli \(\displaystyle a(i) \) in modo da ottenere un quadrato magico.
Quindi devi verificare che possano essere soddisfatte contemporaneamente le condizioni sulle righe e quelle sulle colonne (pur senza ottenere il quadrato di partenza).
Quindi devi verificare che possano essere soddisfatte contemporaneamente le condizioni sulle righe e quelle sulle colonne (pur senza ottenere il quadrato di partenza).
no devi verificare che ogni quadrato magico che non ha solo 1 o 0 può essere ottenuto come media di altri 2, ma non sono sicuro sulla correttezza della dimostrazione....
Nel modo che avevo scritto prima dovresti riuscire a costruire esplicitamente un quadrato da sommare e sottrarre a quello di partenza, in modo da ottenerlo come media. Non mi vengono alternative per ora.
"xXStephXx":
Nel modo che avevo scritto prima dovresti riuscire a costruire esplicitamente un quadrato da sommare e sottrarre a quello di partenza, in modo da ottenerlo come media. Non mi vengono alternative per ora.
Credo che basti
Potresti spiegarti un po' meglio? nn ho idea di cosa siano le mosse di cui parli....
Puoi aggiungere qualcosa ad una casella $a(1)$, ma per far tornare la somma sulle righe devi anche devi toglierlo ad un'altra casella $a(2)$ sulla stessa riga di $a(1)$.
Ora per far tornare la somma sulla colonna di $a(2)$ devi aggiungerlo ad un'altra casella $a(3)$ sulla stessa colonna di $a(2)$.
E poi toglierlo ad una casella sulla stessa riga di $a(3)$, e così via...
Ora per far tornare la somma sulla colonna di $a(2)$ devi aggiungerlo ad un'altra casella $a(3)$ sulla stessa colonna di $a(2)$.
E poi toglierlo ad una casella sulla stessa riga di $a(3)$, e così via...
ah ok ho capito
PREMESSA: del topic ho letto solo il problema per evitare di leggere la soluzione.
Prendendo due quadrati magici $X$ e $Y$, avrò ogni cella denominata con un indice, quindi per due celle con lo stesso indice appartenenti ai due quadrati magici avrò $x_i$ e $y_i$ come valori che trovo nelle celle.
Faccio la loro media aritmetica $m_i=0.5*(x_i+y_i)$ e vedo quali sono i risultati possibili.
Avrò che $m_i$ è sempre un valore compreso tra 0 e 1, quindi posso avere 0 solo se $x_i=y_i=0$ e 1 se $x_i=y_i=1$.
Può un valore di cella compreso tra 0 e 1 essere espresso come media aritmetica di due distinti? La risposta è si perché è sempre possibile avere in due celle distinte i due valori $x_i=a+\delta$ e $y_i=a-\delta$ con $\delta$ piccolo a piacere tale da non uscire dall'intervallo $[0,1]$.
Quando stai su 0 oppure 1 è chiaro quindi che non c'è modo di esprimere il valore con la media tra due altri numeri distinti nell'intervallo, quindi come media di due celle di due altri quadrati.
Dunque, ogni cella di un quadrato magico puro deve avere un valore di 0 oppure 1, in modo però da soddisfare la condizione di somma tra celle sulla stessa riga o colonna. È ovvio che non è possibile avere un quadrato con tutti uno o tutti zero. Si dovrà perciò avere che ogni quadrato avrà $n$ celle pari ad $1$ e le restanti pari a $0$. Il motivo è che una singola cella con valore $1$ è sufficiente a soddisfare la condizione richiesta lungo la riga e la colonna di cui fa parte, dato che ci sono $n$ colonne e $n$ righe, ma una cella di valore $1$ copre sia una riga che una colonna, allora ci devono essere esattamente $n$ celle con valore $1$. Se ce ne fossero di più, una riga o colonna non soddisferebbe la condizione, se ce ne fossero meno idem.
Prendendo due quadrati magici $X$ e $Y$, avrò ogni cella denominata con un indice, quindi per due celle con lo stesso indice appartenenti ai due quadrati magici avrò $x_i$ e $y_i$ come valori che trovo nelle celle.
Faccio la loro media aritmetica $m_i=0.5*(x_i+y_i)$ e vedo quali sono i risultati possibili.
Avrò che $m_i$ è sempre un valore compreso tra 0 e 1, quindi posso avere 0 solo se $x_i=y_i=0$ e 1 se $x_i=y_i=1$.
Può un valore di cella compreso tra 0 e 1 essere espresso come media aritmetica di due distinti? La risposta è si perché è sempre possibile avere in due celle distinte i due valori $x_i=a+\delta$ e $y_i=a-\delta$ con $\delta$ piccolo a piacere tale da non uscire dall'intervallo $[0,1]$.
Quando stai su 0 oppure 1 è chiaro quindi che non c'è modo di esprimere il valore con la media tra due altri numeri distinti nell'intervallo, quindi come media di due celle di due altri quadrati.
Dunque, ogni cella di un quadrato magico puro deve avere un valore di 0 oppure 1, in modo però da soddisfare la condizione di somma tra celle sulla stessa riga o colonna. È ovvio che non è possibile avere un quadrato con tutti uno o tutti zero. Si dovrà perciò avere che ogni quadrato avrà $n$ celle pari ad $1$ e le restanti pari a $0$. Il motivo è che una singola cella con valore $1$ è sufficiente a soddisfare la condizione richiesta lungo la riga e la colonna di cui fa parte, dato che ci sono $n$ colonne e $n$ righe, ma una cella di valore $1$ copre sia una riga che una colonna, allora ci devono essere esattamente $n$ celle con valore $1$. Se ce ne fossero di più, una riga o colonna non soddisferebbe la condizione, se ce ne fossero meno idem.
"maCrobo":
Quando stai su 0 oppure 1 è chiaro quindi che non c'è modo di esprimere il valore con la media tra due altri numeri distinti nell'intervallo, quindi come media di due celle di due altri quadrati.
Perché? Ovvero: se in una casella hai 0 o 1 allora è media di due caselle uguali, ma perché anche i quadrati intorno devono essere uguali?
In quel passaggio lì volevo solo dire di due celle appartenente a due quadrati distinti. Per intervallo intendo quello che va da 0 a 1, non righe o colonne. Il ragionamento in quel punto è ancora solo per singole coppie di celle di quadrati magici.
D'accordo.
Qui però stai passando dalla casella singola all'intero quadrato magico... come?
In altre parole, ogni casella $m_i$ la puoi scrivere come media di $x_i$ e $y_i$ nell'intervallo, va bene; ma come fai a sceglierli in modo che il quadrato formato dagli $x_i$ sia magico?
"maCrobo":
Dunque, ogni cella di un quadrato magico puro deve avere un valore di 0 oppure 1
Qui però stai passando dalla casella singola all'intero quadrato magico... come?
In altre parole, ogni casella $m_i$ la puoi scrivere come media di $x_i$ e $y_i$ nell'intervallo, va bene; ma come fai a sceglierli in modo che il quadrato formato dagli $x_i$ sia magico?
Quando stai su 0 oppure 1 è chiaro quindi che non c'è modo di esprimere il valore con la media tra due altri numeri distinti nell'intervallo, quindi come media di due celle di due altri quadrati.
Il testo diceva che un quadrato magico puro non può essere formato come media aritmetica cella per cella di due quadrati magici distinti; dove siamo d'accordo che "cella per cella" significa che partendo da una cella di $X$ con posizione $i$ e un'altra di $Y$ con stessa posizione $i$ si arriva al valore della cella in posizione $i$, che sarà $m_i=(x_i+y_i)0.5$, di un'altro quadrato magico.
Adesso, se gli unici numeri che non sono esprimibili come media di due numeri distinti sono 0 e 1, una qualsiasi cella del quadrato magico puro deve avere al suo interno uno 0 oppure un 1. Deve essere così per tutte le celle perché se anche una sola delle celle contiene un numero diverso da 0 oppure 1 si possono creare due quadrati magici distinti in cui si avranno tutte le celle con 0 e 1 identiche e quelle la cui media dovrà fare il numero diverso da 1 o 0 possono essere distinte (per il motivo del $\delta$ piccolo a piacere). A questo punto avrei due quadrati magici distinti per una sola cella, ma distinti, e facendone la media otterrei comunque il quadrato di cui sono interessato, che quindi non sarà puro.
Segue...
Dunque, ogni cella di un quadrato magico puro deve avere un valore di 0 oppure 1, in modo però da soddisfare la condizione di somma tra celle sulla stessa riga o colonna.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo