Un problema interesante usando el principio Pigeonhole

Question

Un problema interesante usando el principio Pigeonhole

Matemáticas
combinatoria
principio del casillero

Maddy

Vi este problema: Let $A \subset \{1,2,3,\cdots,2n\}$ . También, $|A|=n+1$ . Demuestra que existe $a,b \in A$ con $a \neq b$ y $a$ y $b$ es coprimo. Probé este muy fácilmente usando el principio del casillero en la partición en $\{1,2\},\{3,4\},\dots,\{2n-1,2n\}$ .

Mi pregunta es ¿Cómo puedo probar o refutar que:

Dejar $A \subset \{1,2,3,\cdots,2n\}$ . También, $|A|=n+1$ . Demuestra que existe $a,b \in A$ con $a \neq b$ y $a|b$ .

No puedo hacer una partición adecuada. ¿Es esto cierto?

tonyk

Pista: hay

n

$n$ casilleros, pero no todos son del mismo tamaño. Por ejemplo, si

n = 5

$n=5$ , los casilleros contienen {1,2,4,8}, {3,6}, {5,10}, {7} y {9}.

Maddy

Oh gracias. Lo tengo.

Respuestas (1)

Un problema interesante usando el principio Pigeonhole

Pista: hay $n$ casilleros, pero no todos son del mismo tamaño. Por ejemplo, si $n=5$ , los casilleros contienen {1,2,4,8}, {3,6}, {5,10}, {7} y {9}.

Abhra Abir Kundu · Answer 1

Cualquier número del conjunto $A$ es de la forma $2^{k}l$ dónde $k\ge 0,0\le l\le (2n-1)$ y $l$ es impar.

Número de números impares $l\le (2n-1)$ es $n$ .

Ahora bien, si seleccionamos $(n+1)$ números del conjunto $A$ entonces debe haber dos números (entre los números seleccionados) con el mismo $l$ .

Es decir, debemos conseguir $a,b$ con $a=2^{k_1}l$ y $b=2^{k_2}l$ no fue $a\ne b$ entonces $k_1\ne k_2$ .Ahora si $k_1>k_2$ entonces $b|a$ demás $a|b$ .

Esto completa la demostración.

Un problema interesante usando el principio Pigeonhole

Maddy

tonyk

Maddy

Respuestas (1)

Abhra Abir Kundu

Dados 5 enteros, muestra que puedes encontrar dos cuya suma o diferencia sea divisible por 6.

Existencia de un subconjunto tal que el producto de sus elementos es un cuadrado perfecto

Mover fichas en un tablero de ajedrez

Dibuja 7 líneas en el plano de manera arbitraria. Demuestre que para cualquier configuración de este tipo, 2 de esas 7 líneas forman un ángulo menor que 26◦

Prueba del principio del casillero por contradicción

Selección de enteros con principio de casillero

Cómo implementar el principio del casillero generalizado

Demuestre que para cualquier conjunto de 201 enteros positivos menores que 300, debe haber dos cuyo cociente sea una potencia de tres (sin resto)

Demuestre utilizando el principio del casillero que hay al menos 555 de las 414141 piezas de ajedrez en el tablero de 10 × 1010 × 1010 × 10 que no están en la misma fila.

Mostrando que hay un nodo en el gráfico con una y solo una arista