Dou? foi de hârtie, de form? p?trat?, au, fiecare, aria egal? cu

. Fiecare dintre foi este împ?r?it?, în mod arbitrar, în 2010 poligoane, ficare având aria egal? cu

. Se suprapun cele 2 foi. S? se arate c? putem "în?epa" de 2010 ori cele 2 foi suprapuse, astfel încât fiecare dintre cele 4020 de poligoane s? fie "în?epat" exact o dat?.

Cu sau f?r? teorema lui Hall?

[Citat] Cu sau f?r? teorema lui Hall?

Cu
De fapt am propus problema tocmai pentru a prezenta lema mariajelor.

Not?m cu

mul?imile ce constituie cele dou? parti?ii ale p?tratului. Introducem matricea

definit? prin

Trebuie s? ar?t?m existen?a unei permut?ri

cu proprietatea

Matricea A este bistohastic?, adic? are elemente pozitive, iar suma oric?rei linii sau coloane este egal? cu 1. Mul?imea

a acestor matrici este o mul?ime convex? ?i compact? în

. Conform teoremei lui Krein-Milman mul?imea

este închiderea acoperirii convexe a punctelor ei extremale. Nu este dificil de ar?tat c? punctele extremale cu pricina sunt matrici ob?inute printr-o permutare a liniilor ?i coloanelor matricii identice. Acestea sunt în num?r finit! Prin urmare matricea noastr? A este o combina?ie convex? de astfel de matrici. Cum combina?ia convex? are un coeficient stric pozitiv, prolema este rezolvat?...

În acest moment mi-am amintit de teorema lui Hall... care simplific? lucrurile. A?tept?m solu?ia direct?!

Lema mariajelor: avem

b?ie?i ?i

fete. Fiecare b?iat este prieten cu câteva fete. În ce condi?ii este posibil ca s? asociem fiecare b?iat cu o fat? pe care o cunoa?te?

Evident, este necesar ca fiecare b?iat s? cunoasc? cel pu?in o fat?. Apoi, din nou evident, pentru orice 2 b?ie?i, mul?imea fetelor cunoscute de (cel pu?in unul dintre) ei trebuie s? aib? m?car 2 elemente. În mod similar, pentru orice mul?ime având

b?ie?i, mul?imea fetelor cunoscute de (cel pu?in unul dintre) ace?tia trebuie s? aib? cel pu?in

elemente.
Desigur, acestea reprezint? o condi?ie evident necesar? pentru a defini o asociere precum cea descris?.
Lema mariajelor (teorema lui Phillip Hall) spune c? aceste condi?ii sunt ?i suficiente.
Una din demonstra?iile teoremei este induc?ia dup?

,
considerând dou? cazuri:
1) Pentru orice

b?ie?i, sunt cel pu?in

fete cunoscute de ei
2) Exist? o mul?ime având

b?ie?i care cunosc exact

fete.
Dac? e nevoie, revin cu detalii.

Acum problema: b?ie?ii sunt poligoanele de pe prima foaie, fetele poligoanele de pe a doua. Rela?ia de cunoa?tere e evident?: un b?iat cunoa?te o fat? dac? cele 2 poligoane au, prin suprapunere, cel pu?in un punct comun.
Dac? lu?m

poligoane de pe prima foaie, ele determin? o suprafa?? de arie

. Atunci poligoanele "fete" sunt cel pu?in tot în num?r de

, în mod evident.
Condi?ia lui Hall fiind îndeplinit?, fiec?rui poligon de pe prima foaie i se asociaz? un poligon de pe a doua foaie, având, prin suprapunere, cel pu?in un punct comun.
Ei, în punctele alea în?ep?m...

[Citat] Una din demonstra?iile teoremei este induc?ia dup? , considerând dou? cazuri: 1) Pentru orice b?ie?i, sunt cel pu?in fete cunoscute de ei 2) Exist? o mul?ime având b?ie?i care cunosc exact fete. Dac? e nevoie, revin cu detalii.

Este nevoie...

Induc?ie dup?

: cazurile ini?iale sunt evidente. Presupunem afirma?ia adev?rat? pentru orice num?r

?i consider?m acum

b?ie?i.

Dac? pentru orice grup de

b?ie?i mul?imea fetelor cunoscute are cel pu?in

elemente, atunci asociem un b?iat (oricare) cu una dintre fetele cunoscute de el. Mul?imea celor

b?ie?i rama?i verific? evident condi?ia Hall (mul?imea fetelor cunoscute de orice

b?ie?i are cel pu?in

elemente) ?i din ipoteza de induc?ie rezult? concluzia.

Dac? exist? un anumit grup

de

b?ie?i care cunosc exact

fete, atunci pe ace?tia îi asociem cu cele

fete. Condi?ia Hall e îndeplinit? pentru mul?imea celor

b?ie?i r?ma?i. Într-adev?r, fie

o mul?ime cu

elemente format? de ace?tia. Dac? fetele cunoscute de ei sunt mai pu?ine de

, atunci fetele cunoscute de b?ie?ii din mul?imea

sunt mai pu?ine de

, ceea ce contrazice ipoteza. A?adar, ?i b?ie?ii r?ma?i pot fi asocia?i cu

fete.