A B. 4295. feladat (2010. október)

B. 4295. Egy 13×13-as táblázat mezőibe úgy írtak számokat, hogy a 13 sorban és a 13 oszlopban ugyanannyi a számok összege. Legalább hány számot kell a táblázatban ahhoz megváltoztatni, hogy a 26 darab összeg között ne legyenek egyenlők?

(Kavics Kupa 2010 feladata nyomán)

(5 pont)

A beküldési határidő 2010. november 10-én LEJÁRT.

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.

Statisztika:

94 dolgozat érkezett.
5 pontot kapott:	Á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 pontot kapott:	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 pontot kapott:	9 versenyző.
2 pontot kapott:	13 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	37 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2010. októberi matematika feladatai