Una matrice

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

Io direi

Testo nascosto, fai click qui per vederlo

(2n-1)!!

Ciao,
Andrea

Perché?

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

Testo nascosto, fai click qui per vederlo

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<n$ considero la sottomatrice $(a_{ij})_{i,j=\{k,...,n\}}$ da cui estraggo $a_{kk}=2k-1$ e così via fino a $n$. Funziona?

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

Addirittura?

Testo nascosto, fai click qui per vederlo

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

… 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

@Mathita

Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.

… 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

Cordialmente, Alex

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

Testo nascosto, fai click qui per vederlo

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<y_1=x_0$ ( fuori dalla diagonale principale) esiste un punto $(x_2,x_1)$,
e se $x_2<x_1$ esiste $(x_3,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

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

Testo nascosto, fai click qui per vederlo

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 …

Testo nascosto, fai click qui per vederlo

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 $i<j$ e $i'>j'$ (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

Ciao,
immagino il punto oscuro sia questo:

Testo nascosto, fai click qui per vederlo

$(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

Essenzialmente sì.

Cordialmente, Alex