Problem B. 4295. (October 2010)

B. 4295. A 13×13 table is filled in with numbers, such that the sum of the numbers is the same in each of the 13 rows and 13 columns. What is the smallest possible number of fields in which the entries should be changed so that the 26 sums are all different?

(Based on a problem of the "Kavics Kupa" Competition, 2010)

(5 pont)

Deadline expired on November 10, 2010.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Tegyük fel, hogy \(\displaystyle t\) darab szám megváltoztatásával elértük, hogy a 26 darab összeg között ne legyenek egyenlők. Ekkor legalább 12 darab különböző sorból és ugyanakkor legalább 12 darab különböző oszlopból kellett választani a számokat, az azonban nem lehet, hogy pontosan 12 darab sorból és pontosan 12 darab oszlopból választottuk őket. Továbbá minden egyes kiválasztott számnak vagy a sorában, vagy az oszlopában kell lennie egy másik kiválasztott számnak. Jelölje \(\displaystyle s\) és \(\displaystyle o\) azon kiválasztott számok számát, melyeknek sorában, illetve oszlopában van másik kiválasztott szám; ekkor \(\displaystyle s+o\ge t\).

Nézzük most azokat a kiválasztott számokat, amelyeknek a sorában található másik kiválasztott szám; ezek legfeljebb \(\displaystyle s/2\) különböző sorban helyezkednek el. Ez azt jelenti, hogy legfeljebb \(\displaystyle s/2+(t-s)=t-s/2\) különböző sorból választottunk számokat. hasonóképpen az is igaz, hogy legfeljebb \(\displaystyle o/2+(t-o)=t-o/2\) különböző oszlopból választottunk számokat. A fentiek alapján

\(\displaystyle 25\le \left(t-\frac{s}{2}\right)+\left(t-\frac{o}{2}\right) =2t-\frac{s+o}{2}\le \frac{3t}{2},\)

ahonnan \(\displaystyle t\ge 17\) adódik.

Másrészről a feladat megoldható pontosan 17 szám megváltoztatása árán; az ábrán megszámoztuk ezeknek a számoknak a helyét.

Az egyszerűség kedvéért tegyük fel, hogy az eredeti táblázatban mind a 26 összeg 0. Ezt nyugodtan feltehetjük, hiszen minden sor és minden oszlop pontosan ugyanannyi számot tartalmaz. Ezért ha minden számot ugyanannyival megnövelünk, az eredetivel ekvivalens feladathoz jutunk. Nem nehéz ellenőrizni, hogy ha minden \(\displaystyle 1\le i\le 17\) esetén az \(\displaystyle i\)-vel jelölt mezőben álló számot megnöveljük \(\displaystyle 10^i\)-nel, akkor már valamennyi összeg kölönböző lesz.

Statistics:

94 students sent a solution.
5 points:	Á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ó 928 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.
4 points:	Bauer Barbara, Csősz Gábor, Hajnal Péter János, Kovács 737 Ármin, Maga Balázs, Mihálykó András, Nagy Róbert, Perjési Gábor.
3 points:	9 students.
2 points:	13 students.
1 point:	5 students.
0 point:	37 students.
Unfair, not evaluated:	2 solutionss.

Problems in Mathematics of KöMaL, October 2010