Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

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 April 16, 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.

Problems in Mathematics of KöMaL, March 2007