KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 3982. 100 freshly graduated mathematicians are looking for jobs. They consult two headhunter companies that have the same 100 positions to offer. Each company makes an offer to each applicant, a different one to each of them. Each applicant chooses from the two offers and, luckily, all positions are filled. Three months later, however, each of them decides to change for the job offered by the other company. (If it is the same as his actual job, then he decides to stay.) Show that all positions will be filled again.

Suggested by B. Csajbók (Budapest)

(3 points)

Deadline expired on 16 April 2007.


Google Translation (Sorry, the solution is published in Hungarian only.)

Megoldás: Rajzoljunk fel egy páros gráfot a következő módon. Az egyik osztály csúcsai legyenek m_1,m_2,\ldots,m_{100}, ezek reprezentálják a matematikusokat, a másik osztály csúcsai pedig az állásoknak megfelelően legyenek a_1,a_2,\ldots,a_{100}. Ha minden mi csúcsot egy kék él segítségével összekötünk azzal az aj csúccsal, amely annak az állásnak felel meg, amit először választott, akkor egy teljes párosítást kapunk. A változtatás utáni állapothoz tartozó éleket pirossal húzzuk be, azt kell belátnunk, hogy ezek is teljes párosítást hoznak létre.

Márpedig ha ez nem így lenne, akkor valamelyik aj csúcsba két piros él is befutna. De akkor abba már legalább 3 él futna be, vagyis az az állást valamelyik cég legalább két különböző matematikusnak javasolta volna, ellentétben a feladat szövegével.


Statistics on problem B. 3982.
130 students sent a solution.
3 points:98 students.
2 points:18 students.
1 point:6 students.
0 point:5 students.
Unfair, not evaluated:3 solutions.


  • Problems in Mathematics of KöMaL, March 2007

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley