Par de números usando el principio del agujero de paloma

Question

n N, A {1, . . . , 2n}, |A| = n + 1. Mostrar que:

a) En A hay un par de números cuya suma es igual a 2n + 1.

b) En A hay un par de números primos relativos.

c) En A hay un par de números, tal que uno es múltiplo del otro.

Para la primera parte, comencé haciendo pares de números cuya suma es igual a 2n + 1, que es literalmente el primer número y el último en el conjunto A, {2n + 1, 2n - 1 + 2, 2n - 2 + 3 ...} No estoy seguro de cómo demostrar que existe este par, cuando claramente lo hace.

No estoy seguro de cómo abordar la parte b) y c), cualquier pista sería muy apreciada.

Answer 1

Para la primera parte, comenzaste bien. Necesitas hacer pares que sumen $2n+1$. Excepto $(1,2n)$, podemos tener $(2,2n-1)$ y más. En general $(1+d,2n-d)$, donde $d=1,2,...,n$. Entonces, hay $n$ pares. Teniendo $n$ pares, tomar $n+1$ números obligaría a tomar dos números de un mismo par.

Para la segunda parte, nota que cualquier par $(a,a+1)$ son mutuamente primos. Entonces haz pares de números consecutivos.

Para la última parte, necesitas hacer conjuntos como los siguientes. En $\{1,2,...,2n\}$, hay exactamente $n$ números impares. Considera $n$ conjuntos vacíos y pon uno de los $n$ números impares en cada uno de ellos. Luego, si $\{x\}$ es uno de los conjuntos, completa el conjunto de la siguiente manera.

$\{x\times 2^{k}|k\in\mathbb{N}\cup\{0\} , x\times 2^{k}\leq2n\}$

Se puede demostrar que, de esta manera de construir los conjuntos, no ocurrirían repeticiones de números. Además, cubriría todos los números.

Answer 2

$$ \begin{array}{rcl} 2n & \longleftrightarrow & 1 \\ 2n-1 & \longleftrightarrow & 2 \\ 2n-2 & \longleftrightarrow & 3 \\ 2n-3 & \longleftrightarrow & 4 \\ & \vdots \end{array} $$

Si tu conjunto $A$ contiene a lo sumo un número de cada uno de estos $n$ pares, entonces tienes $|A|\le n.$

Answer 3

Vamos a poner los datos dados como $$ \left\{ {\begin{array}{*{20}c} {U = \left\{ {1,\; \ldots ,\;2n} \right\}} & {\left| U \right| = 2n} \\ {A \subseteq U} & {\left| A \right| = n + 1} \\ {B = U\backslash A} & {\left| B \right| = n - 1} \\ \end{array} } \right.\quad $$ Ahora, consideramos los pares ordenados, por ejemplo $(a,b)\;|\,a \leqslant b$, de elementos de $U$ que satisfacen una propiedad dada.
Si (al menos) uno de los elementos del par pertenece a $B$, entonces el par completo no puede pertenecer a $A.
Entonces, si $B$ puede acomodar al menos un elemento distinto por cada par, entonces todos los pares son "destruidos", es decir, ninguno pertenecerá a $A.
No perdemos generalidad si realizamos esta comprobación en el primer elemento (distinto) de cada par, ya que siempre podemos intercambiar los elementos.
Dado que la cardinalidad de $B$ es $n-1$, eso significa que si dentro de los pares ordenados con la propiedad dada, el conteo de aquellos que tienen un primer elemento distinto es menor que $n$, entonces podría darse el caso de que $B$ contenga todos esos elementos, dejando ningún par para $A.
Por el contrario, si son $n$ o más, al menos un par permanecerá fuera y terminará en $A$.

Ahora, teniendo en cuenta también las otras respuestas, para las propiedades propuestas tenemos

• a) los pares ordenados que suman $2n+1$ son $(1,\,2n)\; \cdots \;(n,n+1)$, para un total de $n$ con todos los primeros elementos distintos $\quad \Rightarrow \quad \text{demostrado}$
• b) los pares ordenados con elementos coprimos son al menos los dados por $(n \, ,n+1)$, para un total de $n \leqslant 2n-1$, con todos los primeros elementos distintos $\quad \Rightarrow \quad \text{demostrado}$
• c) los pares ordenados con un elemento múltiplo del otro son al menos los dados por $(1 \, ,n+1)$, para un total de $n \leqslant 2n-1$, con todos los segundos elementos distintos, y cambiando el orden $\quad \Rightarrow \quad \text{demostrado}$