Zadanie z macierzy-najmniejsza wartosc sumy

[liu]

W trakcie buszowania po necie natrafilem na pewne zadanko z jakiegos amerykanskiego konkursu. Oto ono:

Niech dana bedzie pewna macierz rozmiaru nxn o elementach rzeczywistych, spelniajaca warunek:
Dla dowolnego wiersza i kolumny suma 2n-1 liczb znajdujacych sie na nich (taki "krzyz") jest nie mniejsza niz X. Jaka jest najmniejsza wartosc sumy wszystkich wyrazow macierzy?

Oto moje rozwiazanie:
Niech \(\displaystyle{ s_{ij}}\) bedzie suma 2n-1 liczb z tresci zadania. Zauważmy, że

\(\displaystyle{ s_{ij} = \Bigsum_{k=1}^n a_{ik} + \Bigsum_{k=1}^n a_{kj} - a_{ij}}\)
(sumujac wyrazy z wiersza i kolumny liczbe na ich przecieciu policzylismy 2 razy, wiec odejmujemy).
Zsumujmy teraz po i:

\(\displaystyle{ \Bigsum_{i=1}^n s_{ij} = \Bigsum_{i=1}^n \Bigsum_{k=1}^n a_{ik} + \Bigsum_{i=1}^n\Bigsum_{k=1}^n a_{kj} - \Bigsum_{i=1}^n a_{ij}}\)
Pierwszy wyraz po prawej stronie równy jest sumie wszystkich wyrazów macierzy (oznaczymy to jako S) - jest to suma sum kolumn. Drugi wyraz jest rowny \(\displaystyle{ n\Bigsum_{k=1}^n a_{kj}}\), trzeci zas \(\displaystyle{ \Bigsum_{k=1}^n a_{kj}}\), gdyz nie jest wazne jakiego wskaznika uzyjemy. Wobec tego:
\(\displaystyle{ \Bigsum_{i=1}^n s_{ij} = S + (n-1) \Bigsum_{k=1}^n a_{kj}.}\)
Zsumujmy to po j:
\(\displaystyle{ \Bigsum_{j=1}^n \Bigsum_{i=1}^n s_{ij} = \Bigsum_{j=1}^n S + (n-1)\Bigsum_{j=1}^n \Bigsum_{k=1}^n a_{kj}}\)
Analogicznie jak wyzej mamy:
\(\displaystyle{ \Bigsum_{j=1}^n \Bigsum_{i=1}^n s_{ij} = nS + (n-1)S = (2n-1)S}\)
Stad:
\(\displaystyle{ S = \frac{1}{2n-1} \Bigsum_{j=1}^n \Bigsum_{i=1}^n s_{ij} q \frac{1}{2n-1} \Bigsum_{j=1}^n\Bigsum_{i=1}^n X = \frac{n^2}{2n-1}X}\)
Skoro mamy ograniczenie to jak wartosc ma byc najmniejsza to sprawdzmy, ze dla jakiejs macierzy jest rownosc. Istotnie, wezmy macierz zlozona z nxn jedynek, wtedy \(\displaystyle{ S=n^2}\), \(\displaystyle{ X=2n-1}\), i oczywiscie \(\displaystyle{ n^2 = \frac{n^2(2n-1)}{n^2}}\).

Czy to sie kupy trzyma?

[półpasiec]

chyba nalezaloby pokazac ze oszacowanie jest dokladnie przez wziecie dowolnego X i znalezienie dla niego optymalnej macierzy, a ty sobie X przyjales
chociaz akurat tutaj wyrazy mozna przeskalowac i przyjac X jakie sie chce, ale to trzeba napisac