Cardinalidad del conjunto de sumas vs conjunto de diferencias

Question

Deje $A$ ser un conjunto de números reales. Demostrar que el conjunto de los números reales que podría ser expresado como la suma de los dos no necesariamente distintos elementos de $A$ es al menos tantos elementos como el conjunto de los números reales no negativos que podría ser expresado como la diferencia de dos no necesariamente distintos elementos de $A$.

Traté de inducción en el tamaño de $A$, y teniendo en cuenta las intersecciones (donde no se consigue nada original, ya que hay una superposición), pero no parece funcionar. También yo era capaz de tener en cuenta que se podría afinar "los números reales positivos" porque sólo podría desplazar los números de arriba.

Answer 1

Deje $S$ el conjunto de las sumas $D$ el conjunto de diferencias. Supongamos primero que $A=\{x_1,\ldots,x_n\}$ es finito. El principal problema es que no hay una representación canónica de los elementos de estos conjuntos, por lo que la rectificación de esta construimos una función de $f$$P:=\{1,\ldots,n\}^2$, de la siguiente manera:

• Definimos $f$ el fin de: $(1,1),(1,2),\ldots,(1,n),(2,1),\ldots,(2,n),\ldots,(n,1),\ldots,(n,n)$.
• $f(j,k)=1$ si $x_j+x_k\neq x_\ell+x_m$ para todos los pares de $(\ell,m)$. De lo contrario, $f(j,k)=0$.

Deje $F_0=\{(j,k)\in P\,:\,f(j,k)=0\}$, lo $|S|=|P\setminus F_0|=|P|-|F_0|$. Observe que para cada $(j,k)\in F_0$, no existe un único mínimo (con respecto a la orden de arriba) par $(\ell,m)\in F_1$ tal que $x_j+x_k=x_\ell+x_m$, por lo que, en particular,$x_j-x_m=x_\ell-x_k$. Deje $R$ ser el conjunto de pares $(j,m)$ $j,k,\ell,m$ anterior. Para cada par $(j,m)\in R$ existe un par $(\ell,k)\in P\setminus R$ tal que $x_j-x_m=x_k-x_\ell$ (con un orden similar argumento). Es decir, para $(\ell,k)\in R$, $x_\ell-x_k$ ya se ha contado en $|D|$ por otro par; no puede ser más overcounting todavía en $P\setminus R$. Por lo tanto hemos demostrado que $$ |D|\le|P|-|R|=|P|-|F_0|=|S|. $$ El caso infinito es realmente simple: hay evidencia de que las inyecciones $A\hookrightarrow S\hookrightarrow A\times A$$D\hookrightarrow A\times A$, pero desde $A$ es infinita hay también una inyección de $A\times A\hookrightarrow A$. Armando estos encontramos a $D\hookrightarrow A\times A\hookrightarrow A\hookrightarrow S$.

Answer 2

Aquí es un boceto de una prueba por inducción para el caso finito; tengo la sospecha de un detallado y completo (y probablemente más elegante) las pruebas se pueden encontrar en un libro de soluciones para la olimpiada tipo de problemas.

La declaración tiene por $|A|=1$, ya que tanto el conjunto de sumas y el conjunto de no-diferencias negativas de tener de 1 elemento.

Supongamos que la declaración se aplica a todos los $A$ de cardinalidad finita, hasta e incluyendo la $n-1$ donde $n \ge 2$. Considere la posibilidad de un arbitrario finito $A$ $n$ elementos, que se denota como de costumbre por $|A|=n$. Queremos demostrar que hay al menos tantos pares sumas como no negativa de a pares diferencias, o (en la notación para ser introducido en el siguiente párrafo) que $|S(A)|\ge |D(A)|$.

Deje $a$ ser el máximo elemento de el conjunto finito $A$. Por comodidad vamos a $Aa$ denota el conjunto $A\setminus\{a\}$ de todos los elementos de a $A$ excluyendo $a$, y deje $S(X)=\left\{x+y\mid x,y\in X\right\}$ denota el conjunto de las sumas de los elementos de $X$, $Sf(X,x)= \left\{x+y\mid y\in X\right\}$ denota el conjunto de las sumas en que un elemento en cada suma es fijo, $D(X)=\left\{|x-y|\mid x,y\in X\right\}$ denota el conjunto de diferencias, y $Df(X,x)=\left\{|x-y|\mid y\in X\right\}$ denota el conjunto de diferencias, donde uno de los elementos en cada diferencia es fijo. A continuación,$S(A) = S(Aa) \cup Sf(A,a)$$D(A) = D(Aa) \cup Df(A,a)$. Tenga en cuenta también que $|Df(A,a)| \le |Sf(A,a)| = n$, y que por la hipótesis inductiva $|D(Aa)| \le |S(Aa)|$.

A pesar de $a+a\in Sf(A,a)\setminus S(Aa)$, puede haber cierta superposición de hasta el $n-1$ elementos entre los $S(Aa)$$Sf(A,a)$. Vamos a demostrar que siempre que hay una superposición de valor, entonces hay al menos una correspondiente superposición de valor entre el$D(Aa)$$Df(A,a)$, en un sentido preciso.

Supongamos $|S(A)|=|S(Aa)|+|Sf(A,a)|-k$. Queremos mostrar que $|D(A)|\le|D(Aa)|+|Df(A,a)|-k$. Si $k=0$, entonces hemos terminado. De lo contrario existe un subconjunto $B\subseteq Aa$ $k\ge 1$ elementos, de tal forma que un valor de la forma $a+y$ por cada $y\in B$ puede ser obtenida como suma de elementos de $Aa$, lo $a+y=u_y+v_y$ algunos $u_y,v_y\in Aa$. Ahora $|a-u_y| = a-u_y = v_y-y = |v_y-y|$, y por lo tanto $|a-u_y|\in Df(A,a)\cap D(Aa)$. También, $|\{u_y+v_y\mid y\in B\}| = k$ por lo que el conjunto de $\{|a-u_y| \mid y\in B\} \cup \{|a-v_y|\mid y\in B\}$ contiene al menos $k$ diferentes elementos. De ello se desprende que $|D(A)| \le |D(Aa)|+|Df(A,a)|-k \le |S(A)|$.

Por tanto, el resultado de la siguiente manera para cualquier finito de conjuntos de $A$.

Extendiendo el argumento para el caso infinito requiere un enfoque diferente, como un elemento maximal pueden no estar disponibles, y la construcción de una inyección de $D(A)$ $S(A)$necesita más atención.