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

 

Problem B. 4855. (February 2017)

B. 4855. A table is filled in with digits of 0 and 1 such that there are no two identical rows, but there are two identical rows in any \(\displaystyle 4\times 2\) sub-table formed by two columns and four rows. Show that there exists a column in which one kind of digit occurs exactly once.

(Proposed by Á. Lelkes)

(6 pont)

Deadline expired on 10 March 2017.


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

Megoldás. Az állítást a sorok számára vonatkozó teljes indukcióval igazoljuk. Ha csak 1 sor van, akkor az állítás nyilvánvalóan teljesül. Tegyük fel most, hogy a \(\displaystyle k\)-nál kevesebb sort tartalmazó táblázatokra már igazoltuk az állítást, és vegyünk egy a feltételeknek megfelelő táblázatot, amelynek \(\displaystyle k\) sora van. Legyen \(\displaystyle s\) a táblázat egy tetszőleges sora. Ha \(\displaystyle s\)-et elhagyjuk a táblázatból, akkor továbbra is kielégíti a feltételeket, így az indukciós feltevés szerint lesz olyan \(\displaystyle o\) oszlopa, amelyben a 0 vagy az 1 pontosan egyszer szerepel. A szimmetria miatt feltehetjük, hogy \(\displaystyle o\)-ban az 1-es szerepel pontosan egyszer, mondjuk az \(\displaystyle s'\) sorban. Ha az \(\displaystyle o\) oszlopba eső helyen az \(\displaystyle s\) sorban 0 van, akkor az \(\displaystyle o\) oszlopban az eredeti táblázatban is pontosan egy 1-es szerepel, és készen vagyunk. Tegyük fel tehát, hogy az eredeti táblázatban az \(\displaystyle o\) oszlop két 1-est tartalmaz: az \(\displaystyle s\) és az \(\displaystyle s'\) sorokban. A feltétel szerint nincs két azonos sor, így van egy olyan \(\displaystyle o'\ne o\) oszlop, amelynek \(\displaystyle s\)-beli és \(\displaystyle s'\)-beli eleme különböző, vagyis az egyik 0, a másik pedig 1. Ha \(\displaystyle o'\)-ben az \(\displaystyle s\)-be és \(\displaystyle s'\)-be eső elemeken kívül is lenne még 0 és 1 is, mondjuk a \(\displaystyle t,t'\) sorokban, akkor az \(\displaystyle s,s',t,t'\) sorok és \(\displaystyle o,o'\) oszlopok által meghatározott \(\displaystyle 4\times 2\)-es résztáblázatnak nem lenne két azonos sora. Így \(\displaystyle o'\)-ben az \(\displaystyle s,s'\) sorokon kívüli elemek között vagy a 0, vagy az 1 már nem szerepel, és így ez a szám az \(\displaystyle o'\) oszlopban pontosan egyszer fordul elő (az \(\displaystyle s\)-be vagy az \(\displaystyle s'\)-be eső mezőben). Ezzel az állítást igazoltuk.


Statistics:

30 students sent a solution.
6 points:Baran Zsuzsanna, Beke Csongor, Borbényi Márton, Döbröntei Dávid Bence, Fuisz Gábor, Gáspár Attila, Győrffy Ágoston, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Klász Viktória, Kovács 246 Benedek, Németh 123 Balázs, Saár Patrik, Szemerédi Levente, Tiszay Ádám, Tóth 827 Balázs, Tóth Viktor, Vári-Kakas Andor, Velkey Vince, Weisz Máté.
5 points:Simon Dániel Gábor, Szabó 417 Dávid, Szabó Kristóf.
4 points:2 students.
2 points:1 student.
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