A B. 3890. feladat (2006. február)

B. 3890. Egy nemzetközi konferencián 200 tudós vesz részt. Mindegyikük legfeljebb 4 nyelven beszél, továbbá bármely három között van kettő, akik beszélnek közös nyelven. Bizonyítsuk be, hogy van olyan nyelv, amit közülük legalább 26-an beszélnek.

(4 pont)

A beküldési határidő 2006. március 16-án LEJÁRT.

Megoldás: Alkalmazzuk az indirekt bizonyítás módszerét. Tegyük fel, hogy minden nyelvet a résztvevők közül legfeljebb 25-en beszélnek. Vegyünk egy A tudóst, ő bármelyik általa beszélt nyelven legfeljebb 24 másik tudóssal tud kommunikálni, ami azt jelenti, hogy van legalább 200-4^.24-1=103 tudós, aki nem beszél A-val közös nyelven. Ha ezek egyike B, akkor B is legfeljebb 96 másik tudóssal tud beszélni, marad tehát legalább 103-96-1=6 olyan tudós, aki sem A-val, sem B-vel nem beszél közös nyelvet. Ha ezek közül valamelyik C, akkor A,B,C közül semelyik kettő nem beszél közös nyelvet, ami ellentmond a feltételnek.

Statisztika:

64 dolgozat érkezett.
4 pontot kapott:	51 versenyző.
3 pontot kapott:	12 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2006. februári matematika feladatai