MathDB
Problems
Contests
Undergraduate contests
Putnam
1964 Putnam
B2
B2
Part of
1964 Putnam
Problems
(1)
Putnam 1964 B2
Source: Putnam 1964
3/5/2022
Let
S
S
S
be a set of
n
>
0
n>0
n
>
0
elements, and let
A
1
,
A
2
,
…
A
k
A_1 , A_2 , \ldots A_k
A
1
,
A
2
,
…
A
k
be a family of distinct subsets such that any two have a non-empty intersection. Assume that no other subset of
S
S
S
intersects all of the
A
i
.
A_i.
A
i
.
Prove that
k
=
2
n
−
1
.
k=2^{n-1}.
k
=
2
n
−
1
.
Putnam
set theory
Elementary