MathDB

B6

Part of 1974 Putnam

Problems(1)

Putnam 1974 B6

Source: Putnam 1974

5/28/2022
For a set with nn elements, how many subsets are there whose cardinality is respectively ≡0\equiv 0 (mod 33), ≡1\equiv 1 (mod 33), ≡2 \equiv 2 (mod 33)? In other words, calculate si,n=∑k≡i  (mod  3)(nk)s_{i,n}= \sum_{k\equiv i \;(\text{mod} \;3)} \binom{n}{k} for i=0,1,2i=0,1,2. Your result should be strong enough to permit direct evaluation of the numbers si,ns_{i,n} and to show clearly the relationship of s0,n,s1,ns_{0,n}, s_{1,n} and s2,ns_{2,n} to each other for all positive integers nn. In particular, show the relationships among these three sums for n=1000n = 1000.
PutnamSetsmoduloSubsets