Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4233. feladat (2010. január)

B. 4233. Egy hételemű halmaz háromelemű részhalmazait kell kiszíneznünk úgy, hogy ha két részhalmaz metszete üres, akkor színük különböző. Legalább hány színre van ehhez szükségünk?

(4 pont)

A beküldési határidő 2010. február 10-én LEJÁRT.


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.


Statisztika:

98 dolgozat érkezett.
4 pontot kapott:Á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 pontot kapott:5 versenyző.
2 pontot kapott:19 versenyző.
1 pontot kapott:8 versenyző.
0 pontot kapott:14 versenyző.
Nem versenyszerű:4 dolgozat.

A KöMaL 2010. januári matematika feladatai