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 régi honlapot akarom!!! :-)

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