MathDB

interesting cardinality

Source:

May 5, 2012

inductionfunctionnumber theory proposednumber theory

Problem Statement

For a set

S

we denote its cardinality by

|S|

. Let

e_1,e_2,\ldots,e_k

be non-negative integers. Let

A_k

(respectively

B_k

) be the set of all

k

-tuples

(f_1,f_2,\ldots,f_k)

of integers such that

0\leq f_i\leq e_i

for all

i

and

\sum_{i=1}^k f_i

is even (respectively odd). Show that

|A_k|-|B_k|=0 \textrm{ or } 1

.

Back to Problems View on AoPS