Problem B. 4233. (January 2010)

B. 4233. The three-element subsets of a seven-element set are coloured. If the intersection of two sets is empty then they have different colours. What is the minimum number of colours needed?

(4 pont)

Deadline expired on February 10, 2010.

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

Megoldás. Legyen a halmaz \(\displaystyle \{1,2,3,4,5,6,7\}\). Az \(\displaystyle \{1,2,3\}\), \(\displaystyle \{4,5,6\}\), \(\displaystyle \{7,1,2\}\), \(\displaystyle \{3,4,5\}\), \(\displaystyle \{6,7,1\}\), \(\displaystyle \{2,3,4\}\), \(\displaystyle \{5,6,7\}\), \(\displaystyle \{1,2,3\}\) sorozatban minden egyes részhalmaz más színű kell legyen, mint az azt megelőző. Látszik tehát, hogy két szín még nem elegendő, hiszen a sorozat tagjait felváltva színezve, az utolsó tagnál azt tapasztaljuk, hogy azt más színnel kell kiszíneznünk, mint a vele megegyező első tagot.

Három színnel azonban a feladat már megoldható. Színezzük pirosra azokat a részhalmazokat, amelyekben benne van a 7, a többi háromelemű részhalmazt pedig színezzük kékre, illetve zöldre szerint, hogy a bennük lévő elemek összege páros-e, avagy páratlan. Tegyük fel, hogy \(\displaystyle \{a,b,c\}\) és \(\displaystyle \{d,e,f\}\) metszete üres. Ha valamelyik piros, akkor a másik nyilván nem lehet az, hiszen a 7 nem szerepelhet mindkét halmazban. Ha viszont egyik sem piros, akkor \(\displaystyle \{a,b,c,d,e,f\}=\{1,2,3,4,5,6\}\), tehát \(\displaystyle (a+b+c)+(d+e+f)=21\). Ezért a két részhalmazban szereplő elemek összege különböző paritású, vagyis egyik részhalmaz kék, a másik pedig zöld kell legyen.

Statistics:

98 students sent a solution.
4 points:	Ágoston Péter, Ágoston Tamás, Balog Dóra, Barczel Nikolett, Beke Lilla, Bogár Blanka, Cséke Balázs, Csere Kálmán, Csuka Róbert, Czipó Bence, Damásdi Gábor, Dudás 002 Zsolt, Éles András, Énekes Péter, Győrfi 946 Mónika, Hajdók Soma, Havasi 0 Márton, Janzer Olivér, Karkus Zsuzsa, Karl Erik Holter, Keceli-Mészáros Emese, Kiss 232 Dóra, Kiss 902 Melinda Flóra, Klincsik Gergely, Korondi Zénó, Kovács 888 Adrienn, Márkus Bence, Máthé László, Mester Márton, Mészáros András, Nagy Róbert, Nánási József, Nguyen Milán, Nguyen Noémi, Perjési Gábor, Rábai Domonkos, Remete László, Somogyi Ákos, Szabó 928 Attila, Szenczi Zoltán, Tossenberger Tamás, Tóth 222 Barnabás, Uray Marcell János, Varnyú József, Weisz Ágoston, Weisz Gellért, Zelena Réka, Zsakó András.
3 points:	5 students.
2 points:	19 students.
1 point:	8 students.
0 point:	14 students.
Unfair, not evaluated:	4 solutionss.

Problems in Mathematics of KöMaL, January 2010