Problema sobre números naturales
El enunciado del problema de Gaussianos de hoy es el siguiente:
Sea
un número natural. Si denotamos como
a la parte entera del número real
(es decir, el mayor número entero menor o igual que
x < n^2[/latex] tal que [latex] \lfloor n^2/x+1 \rfloor[/latex] es divisible por [latex]n[/latex]. Indicar también el valor de [latex]x[/latex].
El problema ha servido de base para la siguiente relación de ejercicios, para el curso de Informática de 1º del Grado en Matemáticas, en la que se conjetura la respuesta con Haskell y se comprueba con QuickCheck.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import Test.QuickCheck -- -------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- soluciones :: Integer -> [Integer] -- tal que (soluciones n) es la lista de los números naturales x < n^2 -- tales que la parte entera de n^2/x+1 es divisible por n. Por ejemplo, -- soluciones 3 == [4] -- -------------------------------------------------------------------- soluciones :: Integer -> [Integer] soluciones n = [x | x <- [1..n^2-1], mod (floor ((fromIntegral n)^2/(fromIntegral x)+1)) n == 0] -- -------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- solucionesEntre :: Integer -> Integer -> [(Integer,[Integer])] -- tal que (soluciones n m) es la lista de los pares de los números x -- entre n y m y la lista de las soluciones de x. Por ejemplo, -- solucionesEntre 2 5 == [(2,[3]),(3,[4]),(4,[5]),(5,[6])] -- -------------------------------------------------------------------- solucionesEntre :: Integer -> Integer -> [(Integer,[Integer])] solucionesEntre n m = [(x,soluciones x) | x <- [n..m]] -- -------------------------------------------------------------------- -- Ejercicio 3. Calcular (solucionesEntre 10 20) y conjeturar el valor -- de (soluciones n). -- -------------------------------------------------------------------- -- El cálculo es -- Main> solucionesEntre 10 20 -- [(10,[11]),(11,[12]),(12,[13]),(13,[14]),(14,[15]),(15,[16]), -- (16,[17]),(17,[18]),(18,[19]),(19,[20]),(20,[21])] -- A la vista del cálculo anterior, (soluciones n) es [n+1]. -- -------------------------------------------------------------------- -- Ejercicio 4. Comprobar con QuickCheck la conjetura anterior. -- -------------------------------------------------------------------- -- La propiedad es prop_soluciones :: Integer -> Property prop_soluciones n = n > 1 ==> soluciones n == [n+1] -- La comprobación es -- Main> quickCheck prop_soluciones -- OK, passed 100 tests. |
El problema también sirve como ejercicio de demostración con Isabelle en la asignatura de Razonamiento automático.