Encuentra el menor

Os traigo hoy el problema de esta semana. El enunciado es el siguiente:

Un número natural de diez dígitos o menos es autobiográfico si, comenzando por la izquierda, su primera cifra indica el número de ceros que tiene el número, su segunda cifra el número de unos, y así sucesivamente. Por ejemplo, el número 3211000 es autobiográfico.

El problema consiste en encontrar el menor número autobiográfico, y, evidentemente, explicar el razonamiento lógico empleado para ello.

Problema sencillo para esta semana. A por él.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

25 Comentarios

  1. Yo diría que el 1210, y he llegado por eliminación, ya que el número de cifras del número te limitan los dígitos posibles que pueden aparecer (por ejemplo, si es de dos cifras sólo pueden aparecer ceros y unos), así que con una cifra sólo puede ser el 0, que no es autobiográfico, con dos cifras sólo pueden ser el 10 y el 11 y ninguno es autobiográfico, con tres cifras, si empieza por 1 tiene que tener un cero, así que sólo puede ser 101, 102, 110 o 120, que tampoco es ninguno y si empieza por dos, sólo puede ser 200 que tampoco es. Así que de 4 cifras, si empiezas poniendo un 1 en la primera no podría haber otro 1 en la segunda (implicaría que sólo hay un uno cuando ya hay 2) así que tiene q ser un 2 y ya el número sale solo…

    Publica una respuesta
  2. Entiendo que el primer número autobiográfico es el 1.

    El 1 se puede expresar como 01 [cero uno], diciendo que, en primer lugar tiene cero ceros, y en segundo lugar tiene un uno.

    Un saludo a todos

    Publica una respuesta
  3. Sea m el número de dígitos, nótese que que si el dígito n aparece en el número autobiográfico entonces n\leq{m+1}, ya que el primero dígito del número indica cuántas veces aparece el número cero, el segundo indica cuántas veces el número uno, y, así, el (n+1)-ésimo dígito indica cuántas veces aparece n, por lo que debe haber al menos n+1 dígitos. (*)

    Además, el primer dígito debe ser distinto de cero para que el número realmente sea de m dígitos, (por ejemplo: el número 01, es realmente de un dígito, no de dos) (**)

    Esto mismo, implica a su vez que debe aparecer en el valor autobiográfico al menos una vez el 0 para que el primer dígito sea positivo. (***)

    La busqueda del mínimo número autobiográfico se hará a partir de conocer el número de dígitos que tiene. Esto, a su vez, se encontrará suponiendo que hay un número autobiográfico con m dígitos a partir del 1, e incrementando en una unidad si no se logra encontrar un número autobiográfico con el número de dígitos supuesto. En cada número de dígito a suponer se construirá un número autobiográfico, de tal manera que se construya como el mínimo. De esta manera, el primer número autobiográfico construido será el mínimo, que es lo que se desea encontrar.

    Si m=1, por (*) debe ser 0, pero esto indicaría que no hay cero, lo cual es una contradicción.

    Si m=2, por (*), sólo aparecen 1’s ó 0’s; por (***), debe haber al menos un cero; y, por (**), el primer valor sería 1. Esto indica que debe ser el 10, pero el 10 no es un número autobiográfico, el cual es una contradicción.

    Si m=3, por (*) sólo pueden aparecer 1, 2 ó 3, por (***) aparece el cero y por (**) el primer valor no es cero. Llamemos al primer valor a_{0}\not= 0, entonces el dígito en el lugar a_{0}+1 es distinto de cero, pues indica que se encuentra al menos una vez el dígito correspondiente en el supuest número autobiográfico. Como 0 aparece una sóla vez, el primer valor es 1 y, por tanto, hay un número distinto de cero en el segundo lugar, entonces el tercero lo ocupa el cero, lo que a su vez indica que no aparece el dos. Con lo que sólo se puede construir el 110, el cual tampoco es autobiográfico, que es una contradicción.

    Si m=4, por (***) aparece el cero; y, por (**), el primer dígito es distinto de cero. Si el primer dígito es 1, entonces el segundo dígito no puede ser 0, ya que aparece al menos una vez el uno, a saber en el dígito del millar; más tampoco puede ser 1, ya que indicaría que aparece una vez el 1, pero con este nuevo 1, ya aparecerían al menos dos veces el 1; si fuese 2, entonces el tercer dígito, que indica la cantidad de veces en que apareció 2, debe ser positivo, si fuese 1, entonces el último dígito debe ser el cero. Con lo cual se construye 1210.

    Finalmente, se verifica que, efectivamente, este es un número autobiográfico, lo cual es cierto, ya que aparece una vez el 0, indicado en el primer dígito; aparecen 2 veces el 1, indicado en el segundo dígito; aparece una vez el 2, indicado en el tercer dígito; y no aparece el 3, indicado en el cuarto dígito.

    Por lo tanto, el mínimo número autobiográfico es: 1210.

    Publica una respuesta
  4. El menor ya hemos dado con él, pero… ¿Y el mayor?

    A mí me sale 6210001000

    Publica una respuesta
  5. La suma de los dígitos debe coincidir con el número de dígitos (claro) y ésto permite buscarlos fácilmente (ej. con Haskell aquí) los números son:

    1210
    2020
    21200
    3211000
    42101000
    521001000
    6210001000
    72100001000
    821000001000
    9210000001000

    hasta 17 dígitos no hay ninguno, para n>17 se ve que, como no puede haber más de 9 ceros, tendría que haber particiones de 9 dígitos tipo 1, 2, … lo cual forzaría claramente a haber más de tipo 2, 3, … lo cual no es posible.

    Publica una respuesta
  6. Algo anecdótico respecto a este problema que propone ^DiAmOnD^ es que apareció hace 2 o 3 semanas en una olimpíada realizada aquí, en Argentina.

    El problema iba destinado a chicos de entre 8º y 9º año de escolaridad, y pedía que se determinaran los tres menores números “autobiográficos” (en el problema se los denominaba “números claros”, pero cumplían con las mismas características).

    Publica una respuesta
  7. Si alguien tiene ganas de encarar el siguiente problema, se me planteo en unas olimpiadas regionales (previas a las nacionales), y dice lo siguiente:

    Sea M el numero de 2011 digitos, todos 8. Sea N el numero de 2011 digitos, todos ellos 5. Sea A = 9·M·N. Calcular la suma de los digitos de A.

    Publica una respuesta
  8. Respecto al problema que propone Pedro T. me atrevería a decir que el resultado es:

    2010*4+3+2010*5+6=2011*9=18099

    Publica una respuesta
  9. 0011 o sea el 11 me extraña que nadie lo haya dicho asi que si se me escapa algo decidmelo por favor.

    Publica una respuesta
  10. Damiancete, ¿como llegas al resultado? (Que es correcto).
    Me interesa como lo resolviste, mas que el resultado.

    Publica una respuesta
  11. Pedro T., coge una calculadora y ve probando: 9x88x55, 9x888x555, 9x8888x5555,…
    Si n es el número de dígitos, queda 4(n-1)+3+5(n-1)+6, que haciendo cuentas es lo mismo que 9n. No lo demostré, pero me imagino que estará bien…

    Publica una respuesta
  12. Jaja pero tu calculadora tiene una buena cantidad de digitos! Esta bien. Habria que demostrarlo de alguna manera (ej. por induccion, no se si se puede).

    Te muestro una forma
    \Gamma = 9\times55\dots555\times88\dots888
    \Gamma = 9\times40(11\dots111)^{2}

    Cualquier numero de la forma, con n unos, N = 11\dots111 lo podemos expresar como \frac{10^{n}-1}{9}

    Despues como esta elevado al cuadrado y tiene 2011 unos
    \Gamma =  40 \frac{(10^{4022}-2 10^{2011}+1)}{9}
    \Gamma =  40 \frac{(10^{4022}-1 - 2\times 10^{2011}+2)}{9}
    \Gamma=  40(\frac{10^{4022}-1}{9} - 2\frac{10^{2011}-1)}{9})

    Claramente las dos potencias de diez que estan escritas son de la forma N = 111\dots111 y N_{1} = 222\dots222 con 4022 y 2011 cifras respectivamente. Despues se sigue con algunas sumas y restas, que por ejemplo, en el primer caso tenemos que

    N-N_{0} = 111\dots110888\dots8889 , con 2010 unos, y 2010 ochos.

    Al multiplicar por cuatro tenemos

    9\times4= 36

    Eso da el primer seis, te llevas el 3 y depues te queda 32+3=35, y te llevas el tres hasta que te topas con el 0. Despues es multiplicar los unos por 4 por lo que te queda, como dijiste:

    \Gamma= 444\dots4443555\dots5556 con 2010 cuatros, 2010 cincos y un seis y un tres.

    Asi

    \Sigma(\Gamma)= 2010\times5 + 2010\times4 + 3 + 6 = 2011\times9 = 18099

    Saludos.

    Publica una respuesta
  13. Gracias Pedro T. por tu demostración. Intenté buscar la forma de hacerlo por inducción pero no la encuentro.

    Por “fuerza bruta”:

    9*888…8*555…5=9*888…8*5*111…1=9*444…4*10*111…1=(39)99…96*111…1*10

    donde todos los números tienen 2011 cifras (el 3999…96 tiene 2012). Descarto el 10 ya que no influye en la suma de las cifras.

    Por tanto, haciendo la multiplicación a mano, obtenemos 2011 filas y 4022 columnas, siendo 39999…..96 todas las filas. Cada columna es de la forma:

    Columna 4022: 6
    Columna 4021: 9+6
    Columna 4020: 9+9+6
    Columna 4019: 9+9+9+6
    ……………………………..
    Columna 2012: 9*2010+6
    Columna 2011: 3+9*2010
    Columna 2010: 3+9*2009
    Columna 2009: 3+9*2008
    …………………………….
    Columna 3: 3+9+9
    Columna 2: 3+9
    Columna 1: 3

    Entonces:

    Columna 4022: 6
    Columna 4021: 9+6=15, dejo el 5 y me llevo 1.
    Columna 4020: 1+9+9+6=10+9+6=25, dejo el 5 y me llevo 2.
    Columna 4019: 2+9+9+9+6=20+9+6=35, dejo el 5 y me llevo 3.
    ……………………………
    Columna 2012: 2009+9*2010+6=2009+9*2009+9+6=20105, dejo el 5 y me llevo 2010.

    Hasta aquí agrupo de la forma 10*(4022-(columna+1))+9+6=10*(4022-columna)+5

    Columna 2011: 2010+9*2010+3=20103, dejo el 3 y me llevo 2010.

    A partir de aquí agrupo de la forma 10*(columna-1)+1+3

    Columna 2010: 2010+3+9*2009=2009+1+9*2009+3=20094, dejo el 4 y me llevo 2009.
    Columna 2009: 2009+3+9*2008=2008+1+9*2008+3=20084, dejo el 4 y me llevo 2008.
    …………………………..
    Columna 3: 3+3+9*2=2+1+3+9*2=24, dejo el 4 y me llevo 2.
    Columna 2: 2+3+9=14, dejo el 4 y me llevo 1.
    Columna 1: 1+3=4.

    Por tanto, las cifras son: 2010 cuatros, un tres, 2010 cincos y un seis.

    Después de hacer esto me doy cuenta de que lo puedo generalizar para n cifras:

    Columna 2n: 6
    Columna 2n-1: 9+6
    ………………….
    Columna n+1: 10*(2n-(n+1))+5

    Hasta aquí agrupo de la forma 10*(2n-columna)+5

    Columna n: 10*(n-1)+3

    A partir de aquí agrupo de la forma 10*(columna-1)+1+3

    Columna n-1: 10*((n-1)-1)+1+3
    …………………………………….
    Columna 2: 10+1+3
    Columna 1: 1+3

    Claro está, las cifras son (n-1) cuatros, un tres, (n-1) cincos y un seis.

    Mucho más bonita la tuya, por supuesto 🙂

    Publica una respuesta
  14. Quisiera saber de donde has conseguido este problema?? la duda surge de que el mismo fue tomado en la instancia regional (de nivel 1, es decir para chicos de 12-13 años) de las Olimpiadas Matematicas Argentinas hace 3 o 4 semanas… con la unica diferencia de que pedia hallar los primeros 3 y se los llamaba numeros “claros”.

    Publica una respuesta
  15. El numero mas grande autobiografico es el 6210001000. como la dijeron la suma de sus digitos debe ser igual al numero de digitos en este caso es 10, un numero autobiografico por definicion es un numero natural de 10 digitos o menos asi que el mas grande debe tener 10 dijitos, si empezamos a construirlo:

    9000000000 <——- tiene 9 ceros pero no indicamos que existe un 9 en el numero
    9000000001 <——- Ya lo indicamos pero ahora existe un 1 en el numero y solo ocho 0
    8100000001 <——- Ahora tenemos dos 1 ya no hay 9, tenemos un 8 y solo siete 0
    7200000010 <——- Ahora hay un 2 y solo un 1 mantendremos el 2 y cambiamos un 0
    7210000100 <——- Pero ahora solo hay seis 0.
    6210000100 <——- Ahora ya no hay 7 y hay un 6 asi que cambiamos de lugar el 1
    6210001000 <——- Ahora ya tenemos el numero autobiografico mas grande.

    en cuanto al menor estoy deacuerdo con Osukaru y Alvaro Cardeña

    Publica una respuesta
  16. Como curiosidad, es una distribución de números del 0 al 9 y bastante regural por lo que parece, dado que 4022 * 4.5 = 18099.

    Sglubbb

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Os traigo hoy el problema de esta semana. El enunciado es el siguiente: Un…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *