La teoría de números y la teoría de conjuntos problema

Question

Deje $A$ ser un conjunto finito. Para $0\leq i\leq 2$, vamos a $a_i$ el número de subconjuntos de a $B$ $A$ tal que $$|B|\equiv i \pmod{3}.$$ Demostrar que $$|a_i - a_j| \leq 1,$$ for all $0\leq i,j\leq 2$.

En primer lugar, supuse que $|A|=n$. A continuación, $a_0 = {^nC_0} + {^nC_3} + {^nC_6} +\cdots$ $a_1 = {^nC_1}+ {^nC_4}+{^nC_7}+\cdots$ $a_2$ de manera similar, pero soy incapaz de mostrar la parte principal. Alguien podría dar una sugerencia!!

Answer 1

He aquí una simple inducción de la prueba. La demanda sostiene claramente si $|A|=0$, así que supongo $|A|>0$. Escoger un elemento $a\in A$ y deje $A':=A-\{a\}$. Deje $a_i$ $a_i'$ el número de subconjuntos de a$A$$A'$, respectivamente, de la cardinalidad congruente a $i$ mod $3$. Como cada subconjunto de $A$ es un subconjunto de a $A'$ o de la unión de un subconjunto de a $A'$ $\{a\}$ (o exclusivo), nos encontramos con que

$$a_0=a_0'+a_2'\qquad a_1=a_1'+a_0'\qquad a_2=a_2'+a_1'.$$ así $$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',$$ y por inducción se realiza.

Answer 2

Deje $a_0(n),a_1(n),a_2(n)$ ser dada por $$ \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{casos} $$ Queremos demostrar que para todos los números enteros no negativos $n$,$|a_i(n)-a_j(n)|\le 1$$0 \le i < j \le 2$.

Proceder por inducción en $n$.

Por evaluación directa, tenemos $$ \begin{cases} a_0(0) = 1\\[4pt] a_1(0) = 0\\[4pt] a_2(0) = 0\\ \end{casos} $$ por lo que la demanda se sostiene para el caso base, $n=0$.

Siguiente, supongamos que la demanda se mantiene para algunos entero no negativo $n$.

A continuación, obtenemos \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*} Por lo tanto, hemos \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*} por lo tanto, restando las ecuaciones anteriores en pares, obtenemos \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*} Entonces la aplicación de la hipótesis inductiva, se deduce que la demanda se sostiene para el caso de $n+1$.

Esto completa la prueba.

Answer 3

Sugerencia : Deje $j$ ser un número complejo distinto de $1$ tal que $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)$

Si $n \equiv 0 ~[3]$. A continuación,$(a_2-a_0)j^2 + (a_1-a_0)j - (-1)^n = 0$. Así $$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$.

Si $n \equiv 1 ~[3]$. A continuación,$(a_2-a_0- (-1)^n)j^2 + (a_1-a_0 )j = 0$. Así $$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{ y } |a_2 - a_0| = |(-1)^n| = 1$.

Si $n \equiv 2 ~[3]$. A continuación,$(a_2-a_0)j^2 + (a_1-a_0 - (-1)^n)j = 0$. Así $$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{ y } |a_1 - a_0| = |(-1)^n| = 1$.

Answer 4

Bueno aquí está una sugerencia. Definir la congruencia de la clase de un conjunto para ser su cardinalidad modulo 3. Se puede dividir el conjunto de subconjuntos de a $A$ en un discontinuo de la unión de los conjuntos de $B_i$ cada uno de tamaño 3, además de un set $E$ de tamaño estrictamente menor que 3. Es necesario elegir los conjuntos de tamaño 3, tales que cada elemento pertenece a una diferente de la congruencia de la clase. ( observe que si un conjunto $C$ es en una de las clases de congruencia, a continuación, quitar/añadir un elemento a $C$ produce un conjunto en diferentes congruencia de la clase)

EDIT: en caso de que no estaba claro, si $A=\{1,2,3,4\}$, por ejemplo $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\}\}$

Y $E$ es el conjunto vacío.