Filip Holl (Philip Hall, 1904-1982) - matematician englez, cea mai mare parte de lucru care face parte din teoria grupului și domeniile conexe de algebră. Astfel, prima teorema Hall se aplică grupurilor solubile. teorema lui Hall la nunti, sa dovedit a fi în 1935, este unul dintre principiile de bază combinatorii. Poate că contribuția sa cea mai importantă la matematică - polinoame Hall, care joacă un rol important în teoria reprezentărilor de grup.
Problema de nunti este necesar să se căsătorească cu fiecare dintre fete cu unul dintre băieți. Fiecare fată (după îndoieli și discuții lungi și debilitate) este o listă de băieți pe care îi place. De asemenea, vom face presupunerea că toți oamenii tineri sunt suficient de nobil nu pentru a rupe inima fetei, care l-au ales, prin refuzul său. Astfel, în timp ce fetele să ia inițiativa, exprimându-și preferințele lor, situația este complet simetrică și este cel mai bine este un tabel format din zerouri și cele.
Enumerăm numărul de băieți și fete din înainte. fete care nu scrie în jos rândurile, camere de băieți - coloane. Elementul în picioare în coloana rând i-lea și jth a tabelului este egal dacă și numai dacă o căsătorie între o fată cu un număr și un număr posibil de băieți, și în caz contrar. Câteodată o fată poate să se căsătorească, și, uneori, se căsătorească toate imposibil.
Aici este un exemplu de astfel de masă. Să băieți și patru fete, de asemenea, patru. Fie prima fată ca primul și al treilea om tânăr, al doilea - primul și al doilea, al treilea - al doilea, al treilea și al patrulea, al patrulea - prima și a patra.
1234 \\
\ hline
11010 \\
21100 \\
30111 \\
41001
\ End "title =" \ începe
1234 \\
\ hline
11010 \\
21100 \\
30111 \\
41001
\ End "style =" vertical-align: -52px; frontieră: none; „/>
În acest caz, este posibil să se căsătorească cu fete și băieți cu aceleași numere.
Un necesar și suficient pentru a se asigura că toți ar putea căsători, pot fi formulate în mai multe moduri echivalente:
1. Fiecare fată îi place cel puțin băieți.
Ia orice linii. Am găsit coloanele care conțin cel puțin unul din rândurile selectate. Numărul acestor coloane nu ar trebui să fie mai mică.
2. Fiecare tânăr se bucură de cel puțin fetele.
Ia orice coloane. Găsiți linia care conține cel puțin una din coloanele selectate. Numărul acestor linii nu ar trebui să fie mai mică.
3. Tabelul nu conține subtabele constând din toate zerouri în rânduri și coloane astfel încât.
Dacă o astfel de masă de acolo, unele femei pot intra în căsătorie doar cu băieții din afara sub-tabele. Deoarece tinerii sunt prea puțini să se căsătorească cu toate fetele.
Teorema lui Hall. Condițiile 1, 2, 3 sunt necesare și suficiente pentru a putea să se căsătorească toate.
Dovada. Necesitatea este evidentă.
Suficiență dovedesc prin inducție. În cazul în care există doar o pereche, și simpatie reciprocă, o formalitate necesară pentru a aranja o căsătorie. Să presupunem acum că teorema este adevărată pentru toate astfel încât. În cazul fetelor și băieților pot fi astfel încât fiecare () fetele ca cei mai tineri, și se poate ca le place chiar și băieți. În primul caz, prima fată se poate căsători cu oricare dintre oamenii care ii place, și apoi starea teoremei va fi efectuată la fel ca înainte, dar de data aceasta pentru fete și băieți. Într-adevăr, să presupunem că fiecare fată îi place mai mult decât băieții. Unul dintre acești tineri ar fi fost cel care sa căsătorit cu prima fată. Dar fără ea există încă cel puțin băieți cărora le plac fetele. Astfel, după căsătoria oricărui cuplu este fată și băiat, la care starea teoremei încă deține. Prin ipoteza de inducție, tot ce se poate căsători.
În al doilea caz, există fete cărora le plac băieții exact. Prin ipoteza de inducție, ne putem căsători cu aceste fete pentru băieții care le plac. Trucul este de a arăta că celelalte fete, de asemenea, poate fi căsătorit pentru băieții rămași. Luați în considerare oricare dintre celelalte fete. fete căsătorite, plus aceste fete trebuie să plac bărbații cel puțin tineri, prin ipoteză. Deoarece femeia căsătorită nu este ca ceilalți băieți, cu excepția celor cu care sunt căsătoriți, fetele trebuie să îți placă celălalt bărbat tânăr, nu cei care sunt căsătoriți. Astfel, fetele rămase pot fi căsătorit cu băieții necăsătoriți, precum și pentru starea lor teorema. Astfel, tot ce se poate căsători.
Problema nuntilor poate fi, de asemenea, reprezentat de un grafic. Acest grafic bipartit (toate nodurile pot fi împărțite în două seturi, astfel încât nervurile conecta doar nodurile de diferite seturi). Fetele va marca partea de sus într-un singur set, băieți - în cealaltă, marginile conecta nodurile corespunzătoare băieți și fete cărora le place reciproc. Acum, trage în loc de masa de la început, Count: