Conjuntos de números que no se dividen

Se me pide que encuentre el mayor número de elementos que un conjunto de números enteros de 1 a 100 puede tener, de manera que ningún elemento del conjunto es divisible por otro. Me dijeron una sugerencia: Imagina todos los números 1 a 100 en forma 2^k m donde k \ge 0 y m es impar. He hecho esto para casi todos los enteros 1 - 100, pero no puede ver un patrón viable. No quiero "la respuesta" a esta pregunta sólo quiero ayuda a la interpretación de la sugerencia o tal vez otra manera de resolverlo. Cualquier ayuda sería grande. ¡Gracias!

¿Quiere una sugerencia? Haga clic aquí.

Haga clic aquí para ver la respuesta completa.

Sugerencia 1

Trabaje sobre el siguiente problema más general: Entre el conjunto de números enteros de 1 a 2n, ¿cuál es el subconjunto más grande tal que ningún elemento divide a otro elemento? Este es un problema mejor porque:

• puede practicar en ejemplos más pequeños, como n = 1, n = 2, n = 3;
• existe un patrón muy fuerte en las respuestas, que usted debería ser capaz de entender de los casos pequeñas antes de trabajar en el caso mayor de n = 50.

Sugerencia 2

Experimentalmente, la mitad superior de los números es tal conjunto, es decir, ninguno de estos números se divide otra:

La adición de cualquier número de esta serie pierde la propiedad, ya que cualquier número adicional k es en el intervalo 1, ..., n y por tanto divide a 2k que ya está en el conjunto. ¿Puede probar las siguientes dos afirmaciones?

1. Ningún elemento de A divide a otro elemento. (Esta es fácil, ¡no trabaje demasiado!)
2. Entre cualquier n + 1 números en el intervalo 1, ..., 2n hay uno que divide a otro. (¡Este es más difícil!)

Sugerencia 3

Parte (1) es fácil. Sea a y b dos elementos de A , con a < b . ¿Puede ser b/a un número entero? No, porque ¡es mayor que 1 y menor que 2!

Aquí hay otra sugerencia para (2). El ejemplo de cómo agregar un elemento a A sugiere que en este problema hay alguna relación especial entre un número y su doble. Si tenemos un conjunto B con más que n elementos, ponemos los elementos en subconjuntos de tal manera que un número y su doble están en el mismo subconjunto de B . Es decir, para cualquier número impar m definimos el conjunto B_m cómo todos elementos de B con la forma 2^k m donde k \ge 0.

El Resto de la Respuesta

Si uno de los B_m contiene más de un elemento, se acaba, porque el elemento más pequeño divide el más grande (en el cociente de los dos elementos, el factor m cancela, y la potencia de 2 más pequeña divide la potencia más grande. Queremos demostrar que existe un B_m con más que un elemento. Y esto es fácil, porque hay n tales B_m (un conjunto para cada 1, 3, ..., 2n - 1), mientras que hay por lo menos n + 1 elementos de B . El principio del palomar nos dice que algún B_m tiene más que un elemento.

El Principio del Palomar

Se utilizó una idea simple pero muy importante llamado principio del palomar o principio de Dirichlet. Peter Gustav Lejeune Dirichlet utilizó el principio en los problemas de la teoría de números. Se puede expresar de varias formas, tales como:

• Si n + 1 elementos se colocan en n cajas, entonces alguna caja contiene al menos dos elementos.
• Si n elementos se colocan en n cajas, de modo que ninguna caja contiene más de un elemento, entonces cada caja contiene exactamente un elemento.

Y hay versiones infinitas:

• Si un infinidad de elementos se colocan en un número finito de cajas, alguna caja contiene una infinidad de elementos.
• Si una cantidad no numerable de elementos se colocan en una cantidad numerable de cajas, alguna caja contiene una cantidad no numerable de elementos.

El principio del palomar es útil en la teoría de números y problemas de combinatoria. Aquí hay un par de problemas para que usted practique el principio:

• Si p es un número primo y a es un número entero no divisible por p , entonces hay un número entero x tal que ax que es congruente con 1 módulo p . Es decir a tiene un inverso multiplicativo mod p . (Sugerencia: considerar todos los posibles valores de ax , es decir 0, a, 2a, ..., (p-1)a ).
• Aquí hay otro problema sobre conjuntos de números que no se dividen. Para un entero positivo n , considerar el conjunto de (n + 1)^2 enteros de la forma 2^a 3^b donde 0 \le a, b \le n . ¿Cuál es el subconjunto más grande de este conjunto con la propiedad de que ningún elemento del subconjunto divide a otro elemento?

Referencias

• (en inglés) Puede ver la pregunta original de Geoff aquí.
• Martin Aigner y Günter M. Ziegler, EL LIBRO de las Demostraciones , Nivola Libros y Ediciones, Tres Cantos (Madrid), 2005. Capítulo 22, "El principio del palomar y el doble recuento" (pp. 139-149) da ejemplos intrincados del principio del palomar, incluso la pregunta de Geoff.
• Wikipedia tiene un artículo sobre el principio del palomar.