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 m_i csúcsot egy kék él segítségével összekötünk azzal az a_j 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 a_j 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 solutionss.

Problems in Mathematics of KöMaL, March 2007

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 solutionss.

Already signed up?
New to KöMaL?