Una matrice

[axpgn]

Sia data una matrice $n xx n$ il cui elemento alla riga $i$-esima e alla colonna $j$-esima è pari a $i+j-1$

Qual è il più piccolo prodotto di $n$ numeri presi da questa matrice, uno per ogni riga e per ogni colonna?



Cordialmente, Alex

[marmi1]

Io direi

(2n-1)!!

Ciao,
Andrea

[axpgn]

Perché?

[Mathita]

Rispondere ai tuoi problemi, axpgn, mi mette molto a disagio: ho sempre paura di malinterpretare il testo o, ancora peggio, di sottovalutare il quesito.

Dovrebbe essere pari al prodotto degli elementi sulla diagonale principale della matrice. \[\prod_{i=1}^{n}a_{ii}=\prod_{i=1}^{n}(2i-1)=(2n-1)!!\] L'obiettivo è minimizzare il prodotto di $n$ elementi della matrice $(a_{ij})_{i,j=1,...,n}$ con $a_{i,j}=i+j-1$ e per farlo è sufficiente minimizzare i fattori.

Dal momento che $a_{ij}$ è minimo se $i,j$ sono i valori più piccoli che abbiamo a disposizione, ragiono così: il più piccolo fattore estraibile dalla matrice è $a_{11}=1$, dopodiché considero la sottomatrice $(a_{ij})_{i,j=2,...,n}$ e ne considero il più piccolo, ossia $a_{22}=3$, al passo $k

Cita

Segnala

[axpgn]

"Mathita":Rispondere ai tuoi problemi, axpgn, mi mette molto a disagio: …

Addirittura?

Il risultato è quello, ok mentre per quanto riguarda la dimostrazione ho qualche dubbio ... Apparentemente mi pare una soluzione logica, che funziona però ...
Per esempio quando dici che

"Mathita":… e per farlo è sufficiente minimizzare i fattori. …

non è del tutto esatto, i fattori devono sottostare anche alla condizione "uno per riga e uno per colonna" …
Oppure quando dici che il minimo è $1$ e poi $3$ ecc. , è sensato ma non dimostrato.
Lo stesso quando passi a sottomatrici sempre più piccole: anche questo è sensato ma come puoi escludere che partendo da un valore della prima riga iniziale diverso, il prodotto finale sia minore?
Voglio dire, è vero che il minimo della prima riga è $1$ ma poi giungi a $2n-1$ ma, per esempio, se partissi da $n$ nella prima riga potresti avere $n$ anche nell'ultima (l'altra diagonale) e in tal caso quale sarebbe il prodotto minore?
In conclusione, il tuo metodo potrebbe anche essere corretto ma, a mio parere, andrebbe dimostrato in modo più formale … IMHO …

Mi pare chiaro che ho in mente una soluzione differente

Cordialmente, Alex

[axpgn]

@Mathita
[ot]

"Mathita":… ho sempre paura di malinterpretare il testo o, ancora peggio, di sottovalutare il quesito. …

Son cose molto diverse però … nel primo caso mi fai pensare che non sono mai chiaro mentre nel secondo che sono stato bravo [/ot]

Cordialmente, Alex

[marmi1]

Ciao.
L'idea iniziale e la -spero giusta- dimostrazione.

Per $a,b,c>0$ , vale:
$(a+b)(a+c) > a(a+b+c)$

Ogni "variazione elementare" in cui sposto solo 2 elementi, rispetto alla diagonale principale,
aumenta il prodotto, per via della disuguaglianza precedente, in cui $b=c$.
Questa sorta di minimo locale ( in tante direzioni), mi fa immaginare che questo sia anche un minimo globale.

La somma delle colonne degli n numeri è uguale alla somma delle righe degli n numeri.
Se nella n-plua esiste un numero in posizione $x_1 e se $x_2 Nella sequenza $(x_{j+1}, x_j)$ deve esistere $j$ per cui
$x_j< x_{j-1}$ e $x_{j+1}>x_j$ (non possono essere le colonne sempre in posizione minore delle righe).
Lo scambio $(x_j,x_{j-1})->(x_j,x_j)$; $(x_{j+1},x_j)->(x_{j+1},x_{j-1})$ riduce il prodotto
per la disuguaglianza iniziale.
Quindi un elemento fuori diagonale principale non puo' essere nella soluzione minima

Ciao,
Andrea

[axpgn]

L'idea è sostanzialmente giusta ma non mi è chiara la dimostrazione …

Perché quella disuguaglianza fa "aumentare il prodotto"? Voglio dire, quella è la tesi mentre invece la prendi per vera come ipotesi … il resto non mi è chiarissimo … IMHO …

Questa è la mia …

Definiamo le coordinate di un numero come $(i,i')$.
Supponiamo che i numeri del prodotto minimo non siano tutti sulla diagonale principale cioè non è $i=i'$ per tutti i numeri del prodotto. $(**)$
In tal caso per ogni numero in cui si abbia $i!=i'$ ne esiste almeno un altro per cui si ha $j!=j'$.
Questo perché se ce ne fosse solo uno "fuori" dalla diagonale, per la condizione posta inizialmente allora avremmo che $i'=j'$ per qualche $j'$ e ciò, appunto, non è possibile per ipotesi.
Quindi nel caso $(**)$ avremmo i due numeri $(i,i')$ e $(j,j')$ tali che $ij'$ (o viceversa ma è la stessa cosa).
Prendiamo allora i due numeri nelle posizioni $(i,j')$ e $(j,i')$ al posto dei due precedenti e manteniamo gli altri fattori del prodotto.
Allora si ha $(i+j'-1)(j+i'-1)-(i+i'-1)(j+j'-1)=(j-i)(j'-i')<0$
Ovvero il nuovo prodotto è minore di quello precedente e questo significa che ogni volta che prendo due numeri "fuori" dalla diagonale principale posso sempre trovarne altri due che mi danno un prodotto minore.
In conclusione, il minimo prodotto si ha quando i fattori si trovano tutti sulla diagonale principale.

Cordialmente, Alex

[marmi1]

Ciao,
immagino il punto oscuro sia questo:

$(x_j,x_{j-1})->(x_j,x_j)$; $(x_{j+1},x_j)->(x_{j+1},x_{j-1})$
comporta una riduzione del prodotto,
infatti posto
$a=2x_j-1$,
$ b=x_{j+1}+x_j-1 -a = x_{j+1} -x_j$,
$c=x_{j-1}+x_j-1 -a =x_{j-1} -x_j$,

si ha:
$x_j+x_{j+1}-1=b+a$
$x_j+x_{j-1}-1=c+a$
$x_{j+1}+x_{j-1}-1=a+b+c$

e quindi si ha
$(x_j+x_j-1)(x_{j+1}+x_{j-1}-1)<(x_j+x_{j-1}-1)(x_{j+1}+x_j-1)$
essendo
$a(a+b+c) < (a+b)(a+c)$

@Alex, la differenza rispetto alla tua, mi pare che stia nel fatto che uno dei nuovi punti, nel mio caso, finisce sulla
diagonale principale. Per il resto mi paiono non molto dissimili.

Ciao,
Andrea

[axpgn]

Essenzialmente sì.

Cordialmente, Alex

[Mathita]

@axpgn

[ot]Aspetta, non intendevo dire che i tuoi quesiti non sono chiari , tutt'altro. Volevo evidenziare la mia scarsa capacità di interpretare correttamente i testi che non sono già espressi in termini matematici. Grazie per aver messo in evidenza le criticità della "dimostrazione": tenterò di migliorare nell'esposizione. [/ot]

[axpgn]

@Mathita

[ot]

"Mathita":Aspetta, non intendevo dire che i tuoi quesiti non sono chiari , tutt'altro.

La mia era solo una battuta, don't worry

"Mathita": … la capacità di interpretare correttamente i testi che non sono già espressi in termini matematici.

Questo è un punto interessante, mi è capitato di parlarne nella stanza di "Giochi Matematici".
Diversamente dagli esercizi e problemi (tipici della "Matematica" e che ritroviamo normalmente anche in questa sezione), nei "puzzles (come di solito li chiamano gli anglosassoni e che di solito posto nella sezione "Giochi") anche il testo può far parte del gioco e quindi soggetto a "interpretazione".
È comunque ovvio che non deve essere ambiguo o del tutto incomprensibile, deve comunque permettere una soluzione precisa e definita … IMHO …[/ot]

Cordialmente, Alex