Number theory and set theory problem

Question

Let $A$ be a finite set. For $0\leq i\leq 2$, let $a_i$ be the number of subsets $B$ of $A$ such that $$|B|\equiv i \pmod{3}.$$ Prove that $$|a_i - a_j| \leq 1,$$ for all $0\leq i,j\leq 2$.

Firstly I assumed that $|A|=n$. Then $a_0 = {^nC_0} + {^nC_3} + {^nC_6} +\cdots$ and $a_1 = {^nC_1}+ {^nC_4}+{^nC_7}+\cdots$ and $a_2$ in a similar manner but I am unable to show the main part. Could anyone give a hint!!

Answer 1

Let $a_0(n),a_1(n),a_2(n)$ be given by $$ \begin{cases} a_0(n) = \binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \cdots\\[4pt] a_1(n) = \binom{n}{1} + \binom{n}{4} + \binom{n}{7} + \cdots\\[4pt] a_2(n) = \binom{n}{2} + \binom{n}{5} + \binom{n}{8} + \cdots\\ \end{cases} $$ We want to show that for all nonnegative integers $n$, we have $|a_i(n)-a_j(n)|\le 1$, for $0 \le i < j \le 2$.

Proceed by induction on $n$.

By direct evaluation, we have $$ \begin{cases} a_0(0) = 1\\[4pt] a_1(0) = 0\\[4pt] a_2(0) = 0\\ \end{cases} $$ so the claim holds for the base case, $n=0$.

Next, suppose the claim holds for some nonnegative integer $n$.

Then we get \begin{align*} a_0(n) &= \;\;\binom{n}{0}\;\;+\;\;\binom{n}{3}\;\;+\;\;\binom{n}{6}\;\;+\;\;\cdots\\[4pt] a_1(n) &= \;\;\binom{n}{1}\;\;+\;\;\binom{n}{4}\;\;+\;\;\binom{n}{7}\;\;+\;\;\cdots\\[4pt] \implies\;a_0(n) + a_1(n) &= {\small{\binom{n+1}{1}}}+{\small{\binom{n+1}{4}}}+ {\small{\binom{n+1}{7}}}+\;\;\cdots\\[4pt] \implies\;a_0(n)+a_1(n) &= a_1(n+1)\\[30pt] a_1(n) &= \;\;\binom{n}{1}\;\;+\;\;\binom{n}{4}\;\;+\;\;\binom{n}{7}\;\;+\;\;\cdots\\[4pt] a_2(n) &= \;\;\binom{n}{2}\;\;+\;\;\binom{n}{5}\;\;+\;\;\binom{n}{8}\;\;+\;\;\cdots\\[4pt] \implies\;a_1(n) + a_2(n) &= {\small{\binom{n+1}{2}}}+{\small{\binom{n+1}{5}}}+ {\small{\binom{n+1}{8}}}+\;\;\cdots\\[4pt] \implies\;a_1(n)+a_2(n) &= a_2(n+1)\\[30pt] a_2(n) &= \;\;{\phantom{\binom{n}{0}\;\;+\;\;}}\binom{n}{2}\;\;+\;\;\binom{n}{5}\;\;+\;\;\cdots\\[4pt] a_0(n) &= \;\;\binom{n}{0}\;\;+\;\;\binom{n}{3}\;\;+\;\;\binom{n}{6}\;\;+\;\;\cdots\\[4pt] \implies\;a_2(n) + a_0(n) &= {\small{\binom{n+1}{0}}}+{\small{\binom{n+1}{3}}}+ {\small{\binom{n+1}{6}}}+\;\;\cdots\\[4pt] \implies\;a_2(n)+a_0(n) &= a_0(n+1)\\[4pt] \end{align*} Thus, we have \begin{align*} a_0(n)+a_1(n) &=\; a_1(n+1) \qquad\qquad\qquad\qquad \\[4pt] a_1(n)+a_2(n) &=\; a_2(n+1)\\[4pt] a_2(n)+a_0(n) &=\; a_0(n+1)\\[4pt] \end{align*} hence, subtracting the above equations in pairs, we get \begin{align*} a_2(n+1)-a_1(n+1) &=\;a_2(n)-a_0(n) \qquad\qquad\qquad\qquad\qquad \\[4pt] a_0(n+1)-a_2(n+1) &=\;a_0(n)-a_1(n)\\[4pt] a_1(n+1)-a_0(n+1) &=\;a_1(n)-a_2(n)\\[4pt] \end{align*} Then applying the inductive hypothesis, it follows that the claim holds for the case $n+1$.

This completes the proof.

Answer 2

Okay here's a hint. Define the congruence class of a set to be its cardinality modulo 3. You can split the set of subsets of $A$ into a disjoint union of sets $B_i$ each of size 3, plus another set $E$ of size strictly less than 3. You need to choose the sets of size 3 such that each element belongs to a different congruence class. ( notice that if a set $C$ is in one of the congruence classes, then removing/adding an element to $C$ produces a set in a different congruence class)

EDIT: in case I wasn't clear, if $A=\{1,2,3,4\}$ then for example $B_1=\{ \{1\},\{1,2\},\{1,2,3\}\}$ $B_2=\{ \{2\},\{2,3\},\{2,3,4\}\}$ $B_3=\{\{3\},\{3,4\},\{1,3,4\}\}$ $B_4=\{\{4\},\{1,4\},\{1,3,2\}\}$ $B_5=\{\{2,4\},\{1,2,4\},\{1,2,4,3\}\}$

And $E$ is the empty set.

Answer 3

Hint : Let $j$ be a complex number different from $1$ such that $j^3 = 1$, $$a_0 + a_1j + a_2j^2 = (1+j)^n = (-1)^nj^{2n}$$ And we know if $P\in \mathbb Z [X]$ such that $P(j) = 0$ then $1+X+X^2 | P(X)$

If $n \equiv 0 ~[3]$. Then $(a_2-a_0)j^2 + (a_1-a_0)j - (-1)^n = 0$. So $$1 + X + X^2 | (a_2 - a_0)X^2 + (a_1 - a_0) X - (-1)^n$$ this is possible only if $|a_2 - a_0| = |a_1- a_0| = |- (-1)^n| = 1$.

If $n \equiv 1 ~[3]$. Then $(a_2-a_0- (-1)^n)j^2 + (a_1-a_0 )j = 0$. So $$1 + X + X^2 | (a_2 - a_0 - (-1)^n)X^2 + (a_1 - a_0) X$$ this is possible only if $|a_2 - a_0 - (-1)^n| = |a_1- a_0| = 0 \Rightarrow |a_1- a_0| = 0 \text{ and } |a_2 - a_0| = |(-1)^n| = 1$.

If $n \equiv 2 ~[3]$. Then $(a_2-a_0)j^2 + (a_1-a_0 - (-1)^n)j = 0$. So $$1 + X + X^2 | (a_2 - a_0)X^2 + (a_1 - a_0 - (-1)^n) X$$ this is possible only if $|a_2 - a_0| = |a_1- a_0 - (-1)^n| = 0 \Rightarrow |a_2- a_0| = 0 \text{ and } |a_1- a_0| = |(-1)^n| = 1$.

Answer 4

Here's a simple induction proof. The claim clearly holds if $|A|=0$, so suppose $|A|>0$. Pick an element $a\in A$ and let $A':=A-\{a\}$. Let $a_i$ and $a_i'$ be the number of subsets of $A$ and $A'$, respectively, of cardinality congruent to $i$ mod $3$. As every subset of $A$ is either a subset of $A'$ or the union of a subset of $A'$ with $\{a\}$ (exclusive or), we find that

$$a_0=a_0'+a_2'\qquad a_1=a_1'+a_0'\qquad a_2=a_2'+a_1'.$$ so $$a_0-a_1=a_2'-a_1'\qquad a_1-a_2=a_0'-a_2'\qquad a_2-a_0=a_1'-a_0',$$ and by induction we are done.