Problema resuelto de CyM

• Versión para imprimir con 2 problemas
  • Para Word (.doc)
  • Para Acrobat (.pdf)
• Otro problema resuelto
• Más problemas resueltos
• Discutí tus soluciones en el Consultorio CyM : Nivel 1 | Nivel 2 | Nivel 3

Enunciado

Problema 1, Primera Ronda CyM 1999, Nivel 1:
¿Cuántos números enteros positivos menores que 1020 tienen como únicos factores primos al 2, 3 ó 7? (Por ejemplo: 2, 8, 21, 63, 84, ...)
(Nota: los números enteros positivos son 1, 2, 3, 4, ...)

Primero tratamos de entender a fondo el problema. Llamemos n a un número que cumpla con lo que pide el enunciado. Entonces, como es "entero positivo", debe ser n >= 1. También el enunciado dice que n < 1020.

La condición que falta es que n tiene como únicos factores primos al 2, al 3 y/o al 7. Pruebo con los ejemplos del enunciado:
8 = 2·2·2 = 23
21 = 3·7
63 = 3·3·7 = 32·7

Y también con otros números:
17 = ... = 17 (es primo, no sirve)
35 = 5·7 (tiene el 5, no sirve)
6 = 2·3 (¡este sí!)

(A continuación describimos una solución posible. No es la más eficiente, pero funciona, y quizás sea lo primero que se nos ocurre.)

En papel

El enunciado pide contar cuántos enteros n cumplen n >= 1, n < 1020, y n = 2^a·3^b·7^c.

Como el 1 no sirve, lo descartamos.

Lo que vamos a hacer es un programa que prueba todos los números enteros desde 2 hasta 1019, y los cuente cuando el número sólo tiene como factores primos al 2, 3 ó 7.

Primero hacemos una copia del valor del Numero en la variable Queda.

Vamos a eliminar todos los 2 de la factorización de Queda. Si tiene de factor al 2 al dividirlo por 2 da resto 0, calculamos el resto con la función "mod". Si es así la dividimos por 2. Repitiendo este proceso muchas veces estamos seguros de eliminar a todos los 2. Como los números son menores a 1020 alcanza con repetir este procedimiento 1020 veces.

(Se puede achicar mucho este número, pero no hace falta, porque el programa es rápido. Para cada número el programa tiene que hacer unas 1020 cuentas tres veces (para 2, 3 y 7). Como hay 1018 numero tiene que hacer sólo unas 1020*3*1018 <= 3000000 operaciones.)

Luego hacemos lo mismo con 3 y con 7.

Si al final Queda vale 1, significa que no aparecen otros primos en la factorización de n y entonces es de la forma 2^a·3^b·7^c y lo contamos. Si no, quiere decir que todavía quedan otros factores primos, y no lo contamos.

El programa en QB

Dim Cantidad as Long
Dim Numero as Long
Dim Queda as Long
Dim Aux as Long
Cantidad = 0
For Numero = 2 To 1019
    Queda = Numero
    For Aux = 1 To 1020
        If Queda mod 2 = 0 Then
            Queda = Queda / 2
        End If
    Next Aux
    For Aux = 1 To 1020
        If Queda mod 3 = 0 Then
            Queda = Queda / 3
        End If
    Next Aux
    For Aux = 1 To 1020
        If Queda mod 7 = 0 Then
            Queda = Queda / 7
        End If
    Next Aux
    If Queda = 1 Then
        Cantidad = Cantidad + 1
    End If
Next Numero
Print "El resultado es:", Cantidad 

En la pantalla

El resultado es: 74

En papel nuevamente
(Es importante escribirlo en papel.)

El programa muestra directamente el resultado: hay 74 enteros positivos menores que 1020 cuyos únicos factores primos son 2, 3 ó 7.

Comentarios al margen

A veces es conveniente ir mostrando los números que va encontrando, para estar seguros de haber hecho bien las cosas.

Hay varias formas distintas de resolver y de escribir un programa que realice esta tarea. Por ejemplo se puede hacer que cuando se da cuenta que no es múltiplo de 2, no siga probando inútilmente.

Otra posibilidad, en lugar de probar número por número si sirve o no, es simplemente generarlos (con cuidado). Para esto usamos que n = 2^a · 3^b · 7^c, y mediante ciclos anidados vamos dando valores a a, b y c, verificando que el producto (n) sea menor que 1020. Notar que a, b y c no pueden ser muy grandes. Con este método anda más rápido.

Recuerden escribir la respuesta del problema en papel (con letra prolija).

• Versión para imprimir con 2 problemas
  • Para Word (.doc)
  • Para Acrobat (.pdf)
• Otro problema resuelto
• Más problemas resueltos
• Discutí tus soluciones en el Consultorio CyM : Nivel 1 | Nivel 2 | Nivel 3

primera visita Principal CyM ¿Qué es CyM? Problemas resueltos: Problema 1 | Problema 2 Material para imprimir Enunciados anteriores Cómo participar Quiénes somos Cómo contactarnos

Conexiones Calendario 2007 Material de entrenamiento Niveles Lenguajes Reglamento 2006 Campeones Más Detalles 2006

Torneo de CyM Página Principal	Olimpíada Matemática Argentina    www.oma.org.ar | info@oma.org.ar
mensajes webmaster@oma.org.ar