Feladat: B.4295 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Ágoston Péter ,  Damásdi Gábor ,  Fonyó Viktória ,  Homonnay Bálint ,  Janzer Olivér ,  Kabos Eszter ,  Lenger Dániel ,  Máthé László ,  Simig Dániel ,  Strenner Péter ,  Szabó Attila ,  Tardos Jakab ,  Tossenberger Tamás ,  Vajda Balázs ,  Varnyú József ,  Viharos Andor ,  Weisz Gellért ,  Zelena Réka ,  Zilahi Tamás ,  Zsakó András 
Füzet: 2012/március, 141 - 142. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Számelrendezések, Egész számok összege, Elsőfokú (és arra visszavezethető) egyenlőtlenségek
Hivatkozás(ok):Feladatok: 2010/október: B.4295

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

 
Megoldás. Legfeljebb egy maradhat változatlan a 26 sor- és oszlopösszeg közül, ezért vagy minden sorban és/vagy minden oszlopban változtatunk meg számot. Feltehetjük, hogy minden sorban változtatunk (legalább egy) számot. Ez már legalább 13 változtatás. Tegyük föl, hogy először soronként 1, vagyis összesen 13 változtatást elvégezve, ezeken kívül legfeljebb csak hármat változtatunk. Ez a (legfeljebb) három változtatás 1, 2 vagy 3 sorba esik. Jelöljük x-szel, hogy ez a három változtatás hány sorban történt. Ebben az x sorban x+3 megváltoztatott mező van, ezek legfeljebb x+3 oszlop összegét változtatják meg.
A maradék 13-x sor mindegyikében pontosan egy helyen változtattunk. Vegyünk ezek közül egyet. Mivel nem lehet két azonos összeg, e mezőnek az oszlopában kell hogy legyen legalább még egy változtatás. Ebből következik, hogy a fent említett x+3 oszlopon kívül legfeljebb 13-x2 oszlop összegét tudják megváltoztatni ezek a változtatások. Tehát azt kaptuk, hogy legfeljebb x+3+13-x2=9,5+x2 oszlop összegét tudjuk így megváltoztatni, ami legfeljebb 11. Ez azt jelenti, hogy legalább 2 oszlop összege változatlan marad, amivel ellentmondásra jutottunk. Hasonlóan juthatunk ellentmondásra, ha csak 0, 1 vagy 2 változtatást végzünk a ,,kötelező'' 13 után. Tehát legalább 13+4=17 változtatásra van szükség. Ennyi viszont már elegendő is, például a következő növelésekkel: