KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 3982. (March 2007)

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 pont)

Deadline expired on 16 April 2007.


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

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:

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.

Our web pages are supported by:   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