Nemam bas dokaz, ali ovo je neko moje misljenje (ne znam da li je 100% ispravno).
Ako posmatramo zbirove na dijagonalama, primetimo da se u svakom potezu, svaka dijagonala poveca tacno za 1. Dakle razlika dijagonala je stalna. Sada, bilo koju matricu mozemo pomocu ponudjenih operacija dovesti u poziciju da na jednoj dijagonali ima dva maksimuma (ne obavezno pocetni maksimumi). U dva poteza mozemo povecati maksimume za po jedan, a jedan broj na drugoj dijagonali za dva. Ako dovedemo matricu u takvu poziciju da i na drugoj dijagonali postoji jedan broj jednak maksimumu, klackavost nase matrice ce biti tacno d1-d2. Sada imamo ovakvu matricu.
max max
a max
Najmanju klackavost dobijamo kada nam i druga dijagonala bude u ravnotezi, odnosno kada a dovedemo do maks. Ako povecamo a za dva, svaki od max na d1 ce se povecati za 1. Dakle da bi doveli a do max, povecacemo ga za max-a. A max na drugoj dijagonali ce se povecati za (max-a)/2. Dakle najmanja klackavost je
Naravno, gornji ceo deo, jer ako je max-a neparno, u jednom preostalom potezu moramo povecati jedan od maksimuma na d1.
Ponavljam, to je samo moje misljenje, ispravite me ako gresim.