Reseña (Criba)

Problema:
Demuestra que 121 no divide a f(n) = n^2 + 3n +5 para ningún número natural n.


Reseña:
Título: R_121_Criba Ante la petición "Demuestra que 121 no divide a n^2 + 3n + 5 para ningún n natural" lo primero que golpea nuestra mente es la forma negativa de la proposición (no divide a). ¿Cómo se puede manejar esto? Es decir ¿cómo se puede manejar una proposición en negativo? Si se pidiera "Demuestra que 121 divide a..." como que de alguna manera se siente un problema más manejable. Pero así como está planteado el problema se nos antoja no computable, no procesable por nuestros sistemas cognitivos. Pero sí lo es. El método de fuerza bruta es desalentador: probarlo para 1, 2, 3, ... Un cuento de nunca acabar. ¿Inducción? ¡Pero si es una negación? Y nuestra mente empieza a girar en remolino. Pero ¡calma! Si está propuesto en un concurso debe ser resoluble. Es más, debe ser fácil. Primero hay que buscar indicios de por dónde se le puede entrar. Porque todo problema de concurso debe tener un punto de ataque, un punto por donde se pueda empezar a pensar sobre su solución. La primera pista está en comprender lo que se pide. Para evitar leerlo en negativo pensémoslo como que pide demostrar que algo es imposible (el que 121 divida a f(n)). Si se saben manejar congruencias los casos se reducen a 120 y es posible aplicarle fuerza bruta. Y si se organizan bien los cálculos es posible verificar los 120 casos en media hora. Pero hay otra pista: 121 = 11^2. ¿Por qué es eso un indicio? Bueno, porque 11 es primo y para verificar que es imposible que 121 divida a f(n) basta demostrar que 11 no la divide dos veces para ningún n. La proposición que se pide demostrar puede traducirse así: 11 no divide dos veces a f(n). Y aquí está ya la clave para la demostración: permite dividir en casos. (El 11 no divide a f(n), y si lo dividiera una vez no lo dividiría una segunda vez.) Es la idea feliz. El método de cribado. Otra forma de traducir el problema y que lleva a la criba es: demostrar que C = {n / 121 divide a f(n)} es un conjunto vacío. La idea de la criba es reducir sucesivamente el espacio de búsqueda. En principio deben analizarse todos los casos. Pero con la criba primero se buscan los n para los cuales 11 divide a f(n). Esto reduce el espacio de búsqueda. Después, en el conjunto B = {n/ 11 divide a f}, se verifica si 121 divide a f para algún elemento de B. Primera criba (método para saber si 11 divide a f(n) para algún n) Como f(n) = n^2 + 3n + 5 no es factorizable, se factoriza dejando un término independiente múltiplo de 11. Para ello se necesita sumar y restar una constante c de tal manera que c + 5 sea múltiplo de 11 pero que, al mismo tiempo, ciertos factores de -c, digamos -c = ab, tengan como suma el coeficiente de n en la ecuación, a + b = 3. (Son las fórmulas de Vieta, un método de factorización que se aplica de manera intuitiva y por prueba y error: con la práctica el método de facilita considerablemente.) Para el caso que nos ocupa se tiene (después de varios intentos): n^2 + 3n +5 +28 – 28. La transformación buscada, pues n^2 +3n – 28 +33 cumple los requerimientos y resulta en la factorización f(n) = (n + 7)(n – 4) + 33. Y se puede ver que f es múltiplo de 11 si y sólo si n = 4 + múltiplo de 11 (digamos n = 4 + 11k, con k un entero). Por lo tanto B = {n/ n = 4 + 11k, k entero}. Segunda criba La segunda criba actúa sólo sobre los elementos de B. Para ello se sustituye en f(n) el elemento genérico de B: f(4 + 11k) = (4 + 11k +7)(4 +11k – 4) + 33 = 11(k +1)11k +33 = 121k(k + 1) +33.} Y se puede ver que 121 nunca va a dividir a f. Problema general Demostrar que p^2 no divide a f(n) = n^2 +(a+b)n + d para ningún n natural (p un primo). Primero buscamos una constante c tal que c + d = kp y al mismo tiempo que –c = ab. La función quedaría f(n) = n^2 + (a + b)n + ab + kp = (n + a)(n +b) + kp. De aquí que p divide a f si y sólo si n = - a + rp o bien cuando n= - b + sp, con r y s enteros cualesquiera. (Si - a +b = p el problema se simplifica pues así sólo habría que probar para –a + rp.) En la segunda criba se tendría: (-a + rp + a)(-a + rp +b) + kp = rp(r + 1)p + kp = r(r + 1)p^2 + kp. Generación de un problema Sea p = 7, a = 2, b= -5, d = 4. Entonces el problema sería: demostrar que 49 no divide a n^2 - 3n +4. Sumando y restando 10 se obtiene: n^2 – 3n + 4 + 10 – 10 = n^2 – 3n – 10 + 14 = (n+ 2)(n – 5) + 14. Así que 7 divide a f(n) si y sólo si n = -2 +7k. Pero para estos números se tendría f(-2 + 7k) = 49k(k + 1) + 14. Y se puede ver que 49 no divide a f(n) para ningún n.

Sugerencia | Antecedentes | Estrategias | Solución corta