A B. 3982. feladat (2007. március)

B. 3982. 100 friss diplomás matematikus állást keres, ezért két fejvadász céget is felkeresnek. Mindkét cég kínálatában ugyanaz a 100 állás szerepel. Mindkét cég javaslatot tesz mindegyik jelentkezőnek, mindegyiknek különbözőt. Mindegyik jelentkező a két javaslat közül választ. Szerencsére így minden állás gazdára talál.

Három hónap próbaidő után után azonban mindenkiben felmerül a változtatás gondolata, és inkább a másik cég által ajánlott munkahelyet választja (ha ez megegyezett az éppen aktuális állással, akkor marad). Mutassuk meg, hogy ekkor ismét minden állás gazdára talál.

Javasolta: Csajbók Bence (Budapest)

(3 pont)

A beküldési határidő 2007. április 16-án LEJÁRT.

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.

Statisztika:

130 dolgozat érkezett.

3 pontot kapott: 98 versenyző.

2 pontot kapott: 18 versenyző.

1 pontot kapott: 6 versenyző.

0 pontot kapott: 5 versenyző.

Nem versenyszerű: 3 dolgozat.

A KöMaL 2007. márciusi matematika feladatai

130 dolgozat érkezett.
3 pontot kapott:	98 versenyző.
2 pontot kapott:	18 versenyző.
1 pontot kapott:	6 versenyző.
0 pontot kapott:	5 versenyző.
Nem versenyszerű:	3 dolgozat.

Már regisztráltál?
Új vendég vagy?