half-space can be either closed or open according to
whether or not points of the plane should be consid-
ered as part of this region.
Hall’s matching theorem (Hall’s marriage theorem)
In 1935 English mathematician Philip Hall estab-
lished the following result, now known as Hall’s
matching theorem:
Given nsets A1, A2, … , Anwith the property
that the union of any kof them (1 ≤k≤n)
contains at least kdistinct elements, it is
always possible to select ndistinct objects, one
from each set.
The condition placed on these sets is not trivial—some
sets could be empty, or the same element could appear
in more than one set, for example.
The theorem is certainly true for the case n= 1: a
single set satisfying the condition of the theorem con-
tains at least one element. Two sets satisfying the con-
ditions of the theorem together contain at least two
distinct elements. As neither set is allowed to be empty,
one set contains one element, and the other another
distinct element. Thus the theorem also holds true for
the case n= 2. One can build up a general proof of the
theorem using a proof by
INDUCTION
.
The validity of the theorem can be demonstrated
with an amusing game of solitaire: divide a shuffled deck
of cards into 13 piles of four cards. The challenge is to
select an ace from one pile, a two from another, a three
from a third, all the way down to king from a 13th pile.
Hall’s matching theorem ensures that this game can
always be won, no matter how the cards are shuffled.
(Think of each pile as a set containing one, two, three,
or four elements—the distinct denominations that
appear in that pile. Among any kpiles it must be the
case that at least kdistinct denominations appear.)
Hall gave another interpretation to his theorem
(explaining the alternative name to the result):
Suppose nwomen each list the names of the
men they would like to marry. As long as any k
women mention at least kdistinct names
among them, 1 ≤k≤n, then it is possible to
make satisfactory matches for all.
See also
SEMI
-
MAGIC SQUARE
.
halting problem In 1936 computer theorist Alan Tur-
ing contemplated whether or not it would ever be possi-
ble to write a computer program that could read any
other program and determine whether that program will
come to a stop or will run forever (by falling into an infi-
nite loop, for example). This question has since become
known as the halting problem. Turing concluded that
such a program could not possibly exist. He reasoned via
a clever
ARGUMENT
of
SELF
-
REFERENCE
:
Suppose a program HALT(P) exists that can
read a computer program P and print yes or
no according to whether P will or will not
halt. Consider then another program, which
we will call TROUBLE, that takes a pro-
gram P and does the following:
TROUBLE (P):
If HALT(P) = “yes” then perform an infinite
loop.
If HALT(P) = “no” then halt.
That is, TROUBLE takes a program P and
goes into an infinite loop if P is a program
that halts, and it halts if P is a program that
does not. Now ask: what does TROUBLE
(TROUBLE) do? We have that TROUBLE
halts if TROUBLE does not halt, and does
not halt if it does! This absurdity shows that
no such program HALT(P) could exist.
There are technical difficulties with this argument (one
must be careful to properly distinguish between the roles
of a program and the input of a program, for example),
but Turing was able to overcome these concerns and
show that this argument is fundamentally sound.
Hamilton, Sir William Rowan (1805–1865) Irish
Algebra, Graph theory, Number theory, Mathematical
physics Born on August 4, 1805, in Dublin, Ireland,
William Rowan is generally considered Ireland’s great-
est mathematician of all time. He is remembered for
his development of an entirely new algebraic system,
the
QUATERNIONS
, which, seven decades later, proved
to be crucial for the development of quantum mechan-
ics and the mathematical physics of the internal struc-
ture of an atom.
Hamilton was a child prodigy, mastering 12 differ-
ent languages by the age of 13. During the teen years,
244 Hall’s matching theorem