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

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 March 10, 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.

Problems in Mathematics of KöMaL, February 2017