Deducción de la divisibilidad basada en el principio de casillero

Question

Estoy tratando de resolver este problema a continuación de Norman Bigg's Matemáticas discretas libro de texto, pero no puedo conciliar su solución con mi trabajo.

Sea $X$ sea un subconjunto de $\{1, 2, \ldots 2n\}$ et $Y$ el conjunto de los números Impares $\{1, 3, \ldots, 2n-1\}$ . Definir una función $f: X \to Y$ b \begin{equation} f(x) = \text{the greatest member of $Y$ that exactly divides $x$}. \end{equation} Demuestre que si $|X| > n + 1$ el n $f$ no es una inyección, y deducir en este caso que $X$ contiene números distintos $x_1$ et $x_2$ tal que $x_1$ es múltiplo de $x_2$ .

Esto es lo que tengo hasta ahora.

Definir una función $X \to Y$ por la regla dada. Claramente, para cualquier $n$ , $|Y|=n$ Así que $|X| > |Y|$ et $f$ no puede ser inyectiva por el Principio del Casillero, lo que significa que hay dos elementos en $X$ , $x_1$ et $x_2$ tal que $f(x_1) = f(x_2) = y$ . Si $x_1 = x_2$ para cualquier $x_1$ et $x_2$ , $f$ sería inyectiva, por lo que debemos ser capaces de encontrar $x_1$ et $x_2$ tal que $x_1 \neq x_2$ . Desde $y$ divide ambos $x_1$ et $x_2$ debemos tener \begin{equation} x_1 = ay \ \text{and} \ x_2 = by, \end{equation} para $a, b, \in \mathbb{N}$ . Pero $x_1$ et $x_2$ son pares, por la definición de $X$ debe darse el caso de que $a$ et $b$ son pares, ya que $y$ no lo son. Por lo tanto, \begin{equation} x_1 = 2cy \ \text{and} \ x_2 = 2dy, \end{equation} para $c, d \in \mathbb{N}$ .

Sin sacrificar la generalidad, tomemos $x_1 > x_2$ . Por lo tanto, $a > b$ . Basta con demostrar que $b | a$ .

---

Este es el punto en el que soy incapaz de completar el argumento. El manual de soluciones enmarca el argumento de forma bastante diferente, argumentando que podemos escribir $x_1 = 2^{m_1} y$ et $x_2 = 2^{m_2} y$ para naturales $m_1, m_2$ . No entiendo por qué podemos escribir $x_1$ et $x_2$ con poderes de $2$ en lugar de múltiplos. La única suposición que no he utilizado es que $y$ es impar: sustituyendo en alguna forma de $2j - 1$ para $y$ no parece que sirva de mucho.

Cualquier ayuda al respecto será muy apreciada.

Answer 1

Lo más importante es que $a$ et $b$ no sólo tienen que ser pares, tienen que ser potencias de dos. ¿Por qué? Porque $f(x)$ se define como mayor impar divisor de $x$ . Al extraer factores de $2$ puedes escribir $a=2^kc$ para algunos impar $c$ lo que significa $x_1=2^kcy$ . Pero entonces $cy$ es un divisor impar de $x_1$ el hecho de que $y$ ya era el mayor divisor impar implica que debemos tener $c=1$ .

Por lo tanto, podemos escribir $x_1=2^ky$ et $x_2=2^hy$ . Y necesariamente, uno de ellos debe ser múltiplo del otro. (Tómese el que tenga un exponente mayor; o, si son iguales, cualquiera de los dos sirve).