Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4099. (May 2008)

B. 4099. A digit is written in each field of a 10×10 table. Every digit occurs exactly 10 times. Prove that there is a row or column that contains at least 4 different digits.

(Kvant)

(5 pont)

Deadline expired on June 16, 2008.


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

Megoldás: Jelölje ai és bi azt, hogy az i számjegy hány különböző sorban, illetve oszlopban fordul elő. Tegyük fel, hogy minden sorban és minden oszlopban egyaránt legfeljebb 3 különböző szám fordul elő. Nevezzük blokknak az egy soron belül található egyforma számjegyek összességét. Indirekt feltevésünk értelmében minden sorban legfeljebb 3 blokk található, a blokkok száma tehát legfeljebb 30. Mivel az i számjegy pontosan ai darab blokkban fordul elő, innen a_0+a_1+\ldots+a_9\le 30 adódik. Ugyanezt az oszlopokra is elvégezve kapjuk, hogy b_0+b_1+\ldots+b_9\le 30. Ezért

\sum_{i=0}^9(a_i+b_i)= \sum_{i=0}^9a_i + \sum_{i=0}^9b_i\le 60,

vagyis kell legyen olyan i számjegy, amelyre ai+bi\le6. Ekkor aibi\le9, ami azt jelenti, hogy az i számjegy a táblázatban legfeljebb 9 helyen fordul elő. Ez az ellentmondás bizonyítja az állítást.


Statistics:

33 students sent a solution.
5 points:Bartha Zsolt, Blázsik Zoltán, Bodor Bertalan, Czeller Ildikó, Damásdi Gábor, Éles András, Fonyó Dávid, Frankl Nóra, Grósz Dániel, Huszár Kristóf, Kiss 243 Réka, Kovács 729 Gergely, Márkus Bence, Mészáros András, Nagy 648 Donát, Perjési Gábor, Somogyi Ákos, Szalkai Balázs, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Zelena Réka, Zsupanek Alexandra.
4 points:Aczél Gergely, Farkas Márton, Kovács 999 Noémi, Zieger Milán.
3 points:2 students.
0 point:3 students.

Problems in Mathematics of KöMaL, May 2008