MathDB

Putnam 1968 A3

Source: Putnam 1968

February 19, 2022

PutnamcombinatoricsSets

Problem Statement

Let

S

be a finite set and

P

the set of all subsets of

S

. Show that one can label the elements of

P

as

A_i

such that (1)

A_1 =\emptyset

. (2) For each

n\geq1

we either have

A_{n-1}\subset A_{n}

and

|A_{n} \setminus A_{n-1}|=1

or

A_{n}\subset A_{n-1}

and

|A_{n-1} \setminus A_{n}|=1.

Back to Problems View on AoPS