Deje $p$ ser un número primo impar. Cuántas $p$-elemento de subconjuntos de a $\{1,2,3,4, \ldots, 2p\}$ han sumas divisible por $p$?

Question

Desde allí se $2p$ elementos en el conjunto, hay exactamente $p$ distintos residuos (incluyendo $0$) cuando se divide por $p$. Se puede escribir como :

$1$ $p+1 \equiv 1 \pmod{p}$

$2$ $p+2 \equiv 2 \pmod{p}$

$3$ $p+3 \equiv 3 \pmod{p}$

$.$

$.$

$p-1$ $2p-1 \equiv p - 1 \pmod{p}$

$p$ $2p \equiv 0 \pmod{p}$

Me di cuenta de que podemos hacer $p$-elemento de considerar cada uno de los subconjuntos de los mismos resto conjunto

por ejemplo: los Subconjuntos pueden ser = ($1,2,3,...p$), ($p+1,p+2,3,5,..2p$).

Por tanto, el número de maneras en que la elección de $p$-elemento de subconjuntos es $2^p$. Y creo que hay algunos más. Espero que alguien podría ayudar?

Answer 1

Esta es la OMI 1995 P6.

Yo voy a darles 2 soluciones, una utilizando sólo el estándar de la teoría de números y la otra a través de la generación de funciones.

Solución 1: Claramente $\{1, 2, \ldots , p\}$ $\{p+1, p+2, \ldots , 2p\}$ 2 $p$-elemento de subconjuntos con la suma de los elementos divisible por $p$.

Considerar que todas las demás $p$-elemento de subconjuntos de a $\{1, 2, \ldots , 2p\}$. Hay $\dbinom{2p}{p}-2$ de ellos. Para un subconjunto con $k$ elementos en $\{1, 2, \ldots , p\}$ $p-k$ elementos en $\{p+1, p+2, \ldots , 2p\}$ donde $1 \leq k \leq p-1$, podemos tomar cualquier $1 \leq i \leq p-1$, añada $i$ a cada una de las $k$ elementos en $\{1, 2, \ldots , p\}$, luego tomar la resultante $k$ números de $\pmod{p}$ a mantenerlos en $\{1, 2, \ldots, p\}$. Esto nos da $(p-1)$ $p$- elemento subconjuntos, por lo que tenemos $p$ $p$-elemento de subconjuntos con la suma de los elementos que proporcionan distintos resto $\pmod{p}$.

Ahora está claro que el $\dbinom{2p}{p}-2$ subconjuntos se puede dividir en grupos de a $p$ subconjuntos, donde cada grupo tiene exactamente un subconjunto con la suma de los elementos divisible por $p$. Esto le da a $\dfrac{\dbinom{2p}{p}-2}{p}$.

Por último, la combinación da el número total como $2+\dfrac{\dbinom{2p}{p}-2}{p}$.

Solución 2: vamos a proceder mediante la generación de funciones. Considere la posibilidad de la generación de la función $f(x, y)=\prod\limits_{m=1}^{2p}{(1+x^my)}$. En su expansión, el coeficiente de $x^ay^b$ es el número de $b$-elemento de subconjuntos con la suma de elementos igual a $a$.

Supongamos que la suma de todos los coeficientes de los términos en el que el poder de $x$ y el poder de la $y$ son ambos divisibles por $p$. Esto le dará el número de $kp$ elemento subconjuntos con la suma de los elementos divisible por $p$. Para obtener el número de $p$-elemento de subconjuntos con suma divisible por $p$, tendríamos que restar el número de $0$-elemento de subconjuntos de e $2p$-elemento del subconjunto con suma divisible por $p$,$2$.

Para obtener la necesaria suma, tenemos un promedio sobre todos los $p$th raíces de la unidad, por tanto $x, y$ (y restar $2$ para obtener la respuesta final):

\begin{align} &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\sum_{j=0}^{p-1}{f(e^{\frac{2i\pi j}{p}}, e^{\frac{2i\pi k}{p})}}} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\sum_{j=0}^{p-1}{\prod_{m=1}^{2p}{(1+(e^{\frac{2i\pi j}{p}})^m(e^{\frac{2i\pi k}{p}}))}}} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\left((1+e^{\frac{2i\pi k}{p}})^{2p}+\sum_{j=1}^{p-1}{\prod_{m=1}^{2p}{(1+(e^{\frac{2i\pi j}{p}})^m(e^{\frac{2i\pi k}{p}}))}}\right)} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\left((1+e^{\frac{2i\pi k}{p}})^{2p}+(p-1)\prod_{m=1}^{2p}{(1+e^{\frac{2i\pi m}{p}})}\right)} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\left((1+e^{\frac{2i\pi k}{p}})^{2p}\right)}+\frac{1}{p}\left((p-1)\prod_{m=1}^{2p}{(1+e^{\frac{2i\pi m}{p}})}\right) \\ = &-2+\frac{1}{p}\left(2+\binom{2p}{p}\right)+\frac{1}{p}\left((p-1)[(-1)^p((-1)^p-1)]^2\right) \\ = & \frac{\dbinom{2p}{p}+2p-2}{p} \end{align}

Answer 2

Recuerdo de un elegante complejo número de la prueba de una Olimpiada de libro (al parecer, esta solución fue dada por un búlgaro concursante que ganó un premio a la creatividad).

Deje $\omega$ $p$- ésima raíz de la unidad. Tenga en cuenta la suma: $$F(\omega) = \sum_{1 \leq i_1 < i_2 ... < i_p \leq 2p} \omega^{i_1}\omega^{i_2}...\omega^{i_p}.$$

Se observa que el $\omega, \omega^{2}, ... , \omega^{2p}$ son las raíces de $(x^p - 1)^2 = x^{2p} - 2x^p + 1$. Por la relación entre la escuela primaria simétrica funciones de las raíces y los coeficientes, obtenemos $F(\omega) = 2$.

Pero podemos escribir $\omega^{i_1}\omega^{i_2}...\omega^{i_p} = \omega^{i_1+i_2+...+i_p}$ y leer los poderes de $\omega$ modulo $p$. Por lo tanto, otra manera de escribir la suma es $$F(\omega) = \sum_{0 \leq k \leq p-1}a_k \omega ^k.$$

Por lo tanto, la equiparación de las dos formas diferentes de escribir la suma, se obtiene: $$(a_o - 2) + a_1 \omega + a_2 \omega^2 ... + a_{p-1} \omega^{p-1} = 0.$$

Pero esto significa $$a_0 - 2 = a_1 = a_2 = ... = a_{p-1}.$$ Clearly $\sum_k a_k$ counts the total number of terms in the summation $F(\omega)$ which is $\binom{2}{p}$.

Por lo tanto, $$\binom{2p}{p} - 2 = (a_0 - 2) + a_1 + a_2 + ...+ a_{p-1} = p(a_0 - 2).$$

Así llegamos $$a_0 = \frac{\binom{2p}{p} - 2}{p} + 2.$$

Tenga en cuenta que esto resuelve el problema, ya que $a_0$ cuenta el número de términos en la suma con la propiedad $i_1 + i_2 + ... + i_p = 0$ modulo $p$.