KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 16 June 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley