1991 AMC 12 Problem 30

Question

For any set

S,

let

|S|

denote the number of elements in

S,

and let

n(S)

be the number of subsets of

S,

including the empty set and the set

S

itself. If

A,

B,

and

C

are sets for which

\begin{gathered} n(A)+n(B)+n(C)\\ {}=n(A\cup B\cup C),\\ |A|=|B|=100, \end{gathered}

then what is the minimum possible value of

|A\cap B\cap C|?

96

97

98

99

100

Use

n(S)=2^{|S|}

and determine

|C|

and

|A\cup B\cup C|

Within the union, count how many elements each of

A,

B,

and

C

can omit

Let

c=|C|

and

u=|A\cup B\cup C|.

Since

n(S)=2^{|S|},

the equation becomes

2^{101}+2^c=2^u.

The two summands must be equal, so

c=101

and

u=102.

Within the union,

A,

B,

and

C

omit

2,

2,

and

1

elements. Thus at most five distinct elements are absent from the triple intersection, giving

|A\cap B\cap C|\ge97.

Equality is attained by making those omissions distinct.

Thus the correct answer is B.

Problem 30 in other years