Inesperado Pruebas Usando Funciones De Generación

Question

Recientemente me encontré con esta hermosa prueba por Erdős que utiliza la generación de funciones de una manera única:

Deje $S = \{a_1, \cdots, a_n \}$ ser un conjunto finito de enteros positivos tal que no hay dos subconjuntos de a $S$ tienen la misma suma. Demostrar que $$\sum_{i=1}^n \frac{1}{a_i} < 2.$$

Pregunta: ¿hay más ejemplos de sorprendente o inesperado pruebas usando funciones de generación de que esta comunidad es consciente de?

(Por favor, abstenerse de publicar respuestas que son ampliamente conocidos, tales como el cambio de decisiones, la forma cerrada de Fibonacci, etc.)

La prueba del teorema anterior:

Prueba: Supongamos $0< x < 1$. Tenemos $$\prod_{i=1}^n (1 + x^{a_i}) < \sum_{i = 0}^{\infty} x^i = \frac{1}{1-x}.$$ Mus, $$\begin{align*} \sum_{i=1}^n \log(1+x^{a_i}) &< - \log(1-x) \\ \sum_{i=1}^n \int_0^1 \frac{\log(1+x^{a_i})}{x} \ dx &< - \int_0^1 \frac{\log(1-x)}x \ dx . \end{align*}$$ Poner a $x^{a_i} = y$, obtenemos $$\begin{align*} \sum_{i=1}^{n} \frac{1}{a_i} \int_0^1 \frac{\log(1+y)}{y} \ dy < - \int_0^1 \frac{\log(1-x)}{x} \ dx \end{align*}$$ es decir, $$\sum_{i=1}^n \frac{1}{a_i} \left( \frac{\pi^2}{12} \right) < \frac{\pi^2}6.$$ Por lo tanto, $\sum_{i=1}^n \frac{1}{a_i} < 2$ y el teorema queda demostrado.

Answer 1

Sicherman dados son la única pareja de 6 caras de los dados que no son normales dados, oso enteros positivos, y tienen la misma distribución de probabilidad de la suma como normal dados.

Las caras de los dados son numeradas 1, 2, 2, 3, 3, 4 y 1, 3, 4, 5, 6, 8.

(Fuente: artículo de la Wikipedia en Sicherman dados)

Podemos probar este hecho mediante la generación de funciones.

Vamos a la no-estándar dados $A$ $B$ caras $(a_1,a_2,a_3,a_4,a_5,a_6)$$(b_1,b_2,b_3,b_4,b_5,b_6)$.

Deje $a(x) = x^{a_1}+x^{a_2}+x^{a_3}+x^{a_4}+x^{a_5}+x^{a_6}$ $b(x) = x^{b_1}+x^{b_2}+x^{b_3}+x^{b_4}+x^{b_5}+x^{b_6}$ ser la generación de funciones para el número hecho rodar de los dados $A$ y dados $B$ respectivamente.

Cuando el producto $$a(x)b(x) = (x^{a_1}+x^{a_2}+x^{a_3}+x^{a_4}+x^{a_5}+x^{a_6})(x^{b_1}+x^{b_2}+x^{b_3}+x^{b_4}+x^{b_5}+x^{b_6})$$ is expanded as a polynomial, the $x^n$ coefficient is the number of ways these non-standard dice can have a sum of $$ n. Si la suma de la no-estándar dado tiene la misma distribución que dos dados, a continuación, el anterior producto debe ser igual al producto de las funciones de generación de dos dados, es decir, \begin{align} a(x)b(x) &= (x+x^2+x^3+x^4+x^5+x^6)^2 \\ &= [x(1+x+x^2+x^3+x^4+x^5)]^2 \\ &= [x(1+x^3)(1+x+x^2)]^2 \\ &= [x(1+x)(1-x+x^2)(1+x+x^2)]^2. \end{align}

Sólo tenemos que averiguar cómo se distribuyen los factores entre los polinomios $a(x)$$b(x)$.

Desde cada uno de los dados debe tener sólo un número entero positivo caras, $x$ divide tanto a a$a(x)$$b(x)$. Por lo tanto, $a(x)$ $b(x)$ debe obtener cada uno de los dos $x$ factores.

Desde dados $A$ $B$ han $6$ caras, $a(1) = b(1) = 6$. Observe que $(1+x)\left.\right|_{x = 1} = 2$, $(1-x+x^2)\left.\right|_{x = 1} = 1$, y $(1+x+x^2)\left.\right|_{x = 1} = 3$. Claramente, $a(x)$ $b(x)$ debe obtener cada uno de los dos $1+x$ factores y uno de los dos $1+x+x^2$ factores.

Esto deja sólo el dos $1-x+x^2$ factores. Si distribuimos uno para cada una de las $a(x)$$b(x)$, entonces habremos $a(x) = b(x)$, y vamos a terminar con el estándar de dados. Por lo tanto, hemos de dar a $1-x+x^2$ factores de la misma dados de generación de función (WLOG $b(x)$).

Esto nos da \begin{align} a(x) &= x(1+x)(1+x+x^2) \\ &= x+2x^2+2x^3+x^4 \\ \left.\right. \\ b(x) &= x(1+x)(1+x+x^2)(1-x+x^2)^2 \\ &= x+x^3+x^4+x^5+x^6+x^8 \end{align}

Por lo tanto, la única pareja de 6 caras de los dados que no son normales dados, oso enteros positivos, y tienen la misma distribución de probabilidad de la suma como normal dados tienen caras numeradas $(1,2,2,3,3,4)$$(1,3,4,5,6,8)$.

Answer 2

Recuerdo que este problema de Stein & Shakarchi del Análisis Complejo.

Deje $\mathbb{N}$ denota el conjunto de los enteros positivos. Un subconjunto $S\subset \mathbb{N}$ se dice que está en progresión aritmética si $$ S=\{a, a+d, a+2d, a+3d, \ldots\} $$ donde $a, d\in \mathbb{N}$. Aquí $d$ se llama el paso de $S$.

Mostrar que $\mathbb{N}$ no puede ser dividido en un número finito de subconjuntos que están en progresión aritmética con los distintos pasos (excepto para el caso trivial $a=d=1$).

Sugerencia: Escriba $\sum_{n\in\mathbb{N}} z^n$ como una suma de términos del tipo de $\frac{z^a}{1-z^d}$.

En la sugerencia de este problema, los términos de $\frac{z^a}{1-z^d}$ representa el ordinario de generación de función para la función característica de la progresión aritmética $S=\{a, a+d, a+2d, \ldots\}$.

Otro buen ejemplo es este problema, y la respuesta por @barto

Answer 3

Aquí está otro (pero tal vez no tan interesante de un problema) que bien combinan la generación de series de análisis complejos para resolver un problema que se encuentra en el contexto de los reales. Si mal no recuerdo este es un ejemplo o problema en J. Bak (muy bonito) análisis complejo libro. No sé si esto cuenta como inesperado a pesar de que (si no me avisas y voy a quitar), pero he utilizado para sorprenderles que métodos como estos podrían ser utilizados para problemas que, ingenuamente, parece lejos de que el problema en sí.

Considerar las (infinitas) sistema de ecuaciones $$\sum_{k=0}^n {n\choose k}a_{n-k}b_k = a_nb_0 + {n\choose 1}a_{n-1}b_1 + \ldots + {n\choose n-1} a_1 b_{n-1} + a_0b_n = 2^n~~~\text{for}~~~n\in\mathbb{N}$$ con $a_0 = b_0 = a_1 = b_1 = 1$. Encuentre todas las soluciones con $a_n,b_n\geq 0$.

El teorema del binomio muestra que $a_n=b_n=1$ es una solución, y si nosotros no permitir que los números negativos, a continuación, hay una infinidad de soluciones. A pesar de que estamos introduciendo dos variables libres ($a_n,b_n$) en cada paso $(n)$ resulta que $a_n=b_n=1$ es la única solución en la que todos los $a_n,b_n$ son positivos.

Prueba: Supongamos $\{a_n,b_n\}_{n=1}^\infty$ resuelve el sistema anterior y de introducir la exponencial en la generación de funciones de $A(z) = \sum_{n=0}^\infty \frac{a_nz^n}{n!}$$B(z) = \sum_{n=0}^\infty \frac{b_nz^n}{n!}$. El producto de Cauchy de las dos series de satisfacer $$A(z)B(z) = \sum_{n=0}^\infty \left(\frac{1}{n!}\sum_{k=0}^n {n\choose k}a_k b_{n-k}\right)z^n = \sum_{n=0}^\infty \frac{2^nz^n}{n!} = e^{2z}$$ Since $a_n,b_n\geq 0$ we have $a_n,b_n\leq 2^n$ so $$ and $B$ are entire functions. As $AB = e^{2z}$ they are also of finite order and zero-free so we must have $A(z) = e^{az + b}$ and $B(z) = e^{cz + d}$ with $a+c = 2$ and $b+d = 0$. Taking into account the initial conditions we get $b=d=0$ and $a=c=1$ so $A(z) = B(z) = e^{z} = 1 + z + \frac{z^2}{2!} + \ldots$ and it follows that $a_n = b_n \equiv 1$ es la única solución.

Si nos relajamos $a_1=b_1=1$, entonces el mismo tipo de derivación como anterior muestra que todas las soluciones positivas son en la forma $a_n = c^n$ $b_n = (2-c)^n$ algunos $c \in [0,2]$.

Answer 4

En la misma línea que el ejemplo de @JimmyK4542, aunque diferentes.

Es posible que la suma de los resultados de los dos "fallos" dados con los habituales números de $\{1,2, \cdots 6\}$ sobre uno de sus lados tiene una distribución uniforme en $\{2, \cdots 12\}$ ? La respuesta es negativa.

Prueba: se debe tener, con evidente notaciones

$$\tag{1}(p_1x+p_2x^2+\cdots p_6x^6)(p'_1x+p'_2x^2+\cdots p'_6x^6)=\frac{1}{11}(x^2+x^3+\cdots x^{12})$$

Factoring $x^2$, $(1)$ es equivalente a:

$$\tag{2}(p_1+p_2x+\cdots p_6x^5)(p'_1+p'_2x+\cdots p'_6x^5)=\frac{1}{11}(1+x+\cdots x^{10})$$

Pero esto es imposible porque

• en el lado izquierdo de $(2)$, tenemos el producto de dos impares grado de los polinomios, cada uno con al menos una raíz real, mientras que

• las raíces del polinomio en el lado derecho, que puede ser escrito bajo la forma $\frac{1-x^{11}}{1-x}$, son las $e^{2i\pi k/11}$, k=1..10$, con ninguna raíz real entre ellos. Contradicción.

Comentario: en lugar de "defectuoso dados", es probablemente mejor para dar un contexto de dos "ruletas" con la desigualdad de los sectores representados en la gráfica de abajo:

Answer 5

Aquí es otro cuidada aplicación que apareció en el examen Putnam.

Deje $S_0$ ser un conjunto finito de enteros positivos. Definimos los conjuntos finitos $S_1, S_2, \cdots$ de los enteros positivos de la siguiente manera: el entero $a$ $S_{n+1}$ si y sólo si exactamente uno de $a−1$ o $a$ es en $S_n.$ Demuestran que existen una infinidad de números enteros $N$ que $S_N = S_0 \cup \{N +a : a \in S_0\}.$.

Prueba de Dibujo: Definir $$f_0(x) = \sum_{a_i \in S_0} x^{a_i}.$$ Note that $$f_{k+1}(x) \equiv (1+x)\cdot f_k(x) \pmod 2$$ is the corresponding polynomial to $S_k$. Then we use the fact that $$(1+x)^{2^n} \equiv 1 + x^{2^n} \pmod 2$$ y el resultado de la siguiente manera.