Página 1 de 1

Regional 2017 N3 P1

Publicado: Mié 06 Sep, 2017 6:18 pm
por Matías V5
Un número entero positivo de [math] dígitos se llama diverso si sus [math] dígitos son distintos. Hallar la cantidad de números diversos que son divisibles por [math].

Re: Regional 2017 N3 P1

Publicado: Mié 06 Sep, 2017 6:48 pm
por Juampi.espejo1
Spoiler: mostrar
a mí me dió 285120

Re: Regional 2017 N3 P1

Publicado: Mié 06 Sep, 2017 9:19 pm
por sebach
Juampi.espejo1 escribió:
Spoiler: mostrar
a mí me dió 285120
Está bien ese número, si podés y querés contá cómo lo pensaste

Re: Regional 2017 N3 P1

Publicado: Jue 07 Sep, 2017 2:40 pm
por sgomezpaz
Spoiler: mostrar
$99=9*11$
Como todos los números diversos son múltiplos de 9 (la suma de sus dígitos siempre será 45), solo queda encontrar los diversos que son múltiplos de 11.
Sabemos que para que un numero sea divisible por 11 la suma de sus dígitos pares debe ser congruente con la suma de sus dígitos impares mod 11.
Llamaremos m a la suma de los dígitos impares y p a la suma de los dígitos pares.
Sabemos por un lado que $m+p=45$ y por otro que $m=p+11k$, con k entero.
Como m y p son naturales y de paridad opuesta, las únicas soluciones que encontramos son $m=p+11$ y $p=m+11$, con lo cual $m=17$ y $p=28$ o $m=28$ y $p=17$.
En cualquiera de los casos tenemos que encontrar los conjuntos que cumplan con las condiciones: A sume 17 y su contraparte B sume 28, con todos los dígitos distintos entre sí.
Tenemos, indistintos de la posición de los dígitos, 11 posibles conjuntos A y B:

$A_1=\{0,1,2,5,9\}$ $B_1=\{3,4,6,7,8\}$
$A_2=\{0,1,2,6,8\}$ $B_2=\{3,4,5,7,9\}$
$A_3=\{0,1,3,4,9\}$ $B_3=\{2,5,6,7,8\}$
$A_4=\{0,1,3,5,8\}$ $B_4=\{2,4,6,7,9\}$
$A_5=\{0,1,3,6,7\}$ $B_5=\{2,4,5,8,9\}$
$A_6=\{0,1,4,5,7\}$ $B_6=\{2,3,6,8,9\}$
$A_7=\{0,2,3,4,8\}$ $B_7=\{1,5,6,7,9\}$
$A_8=\{0,2,3,5,7\}$ $B_8=\{1,4,6,8,9\}$
$A_9=\{0,2,4,5,6\}$ $B_9=\{1,3,7,8,9\}$
$A_{10}=\{1,2,3,4,7\}$ $B_{10}=\{0,5,6,8,9\}$
$A_{11}=\{1,2,3,5,6\}$ $B_{11}=\{0,4,7,8,9\}$

Ahora tenemos que calcular la cantidad de números distintos que se pueden formar con estos conjuntos, ya sea con los conjuntos A en lugares impares y B en pares o viceversa.
Sabemos que $5! * 11$ nos da las distintas posiciones que pueden tomar los dígitos de los conjuntos en diferentes lugares.
Multiplicando estas por las distintas maneras de ordenar las contrapartes B de los conjuntos A ($5!$), tenemos
$2*5!^2*11$ posibilidades (recordar que podemos ubicar a los conjuntos A en lugares impares y B en pares y viceversa).

Solo queda restar los diversos que arrancan con 0 (y por lo tanto no pueden ser expresados como números de 10 cifras).
Como todos los pares de conjuntos A y B tienen alguno un cero y ambos son usados en lugares impares la mitad de las veces, tenemos $11*4!*5!$ números que empiezan con 0.

Finalmente:
Cant. diversos divisibles por 99 $= 11*5!(2*5!-4!) = 285120$

Re: Regional 2017 N3 P1

Publicado: Vie 08 Sep, 2017 12:15 am
por sebach
Comentario un poquito relacionado (que podría haber metido en muchos lugares, pero este problema me gustó como excusa):

Existe una herramienta hermosa y súper importante, no para una instancia Regional pero sí para muchas cosas más que nada de "la vida" que es la programación. Para los que no están interiorizados, es básicamente darle a la computadora una serie de pasos a seguir en un idioma que entienda la computadora para que agarre y haga las cuentas que queremos pero mucho más rápido.

Por ejemplo, para este problema, podíamos decirle a la computadora "che, fijate los números de [math] cifras (desde el [math] hasta el [math]), cuántos son divisibles por [math] y tienen todas las cifras distintas y decime la respuesta".
Obviamente en una instancia de la Olimpíada de Matemática no se puede porque no tendría mucho sentido poner "son 'tantos' " y listo, había que explicar cómo pensarlo y cómo contarlos justamente sin ver uno a uno. Pero qué se yo, con esta herramienta por ejemplo podrían volver a sus casas y que la compu les compruebe en quizás unos minutos (son muchos números a chequear) si su respuesta estuvo bien o no.

Hay muchas competencias de programación, Olimpíadas presenciales y también problemas para resolver online, con problemas muy relacionados a la matemática, como por ejemplo este podría ser uno. Quizás salen solo haciendo cosas de matemática, o quizás pensando hay que descartar algunas cosas para que la compu no haga cuentas de más (por ejemplo, acá se podía ver que siempre que tuviera todas las cifras distintas, ya era múltiplo de 9, y se ahorraban de que la compu chequeara esa condición).

Hay mucho para leer en internet (como todo), y si a alguien le interesó/interesa pueden comunicarse conmigo (por ejemplo) y les puedo dar una mano.

Re: Regional 2017 N3 P1

Publicado: Vie 24 Nov, 2017 6:20 pm
por Guty
sebach escribió: Vie 08 Sep, 2017 12:15 am
Existe una herramienta hermosa y súper importante, no para una instancia Regional pero sí para muchas cosas más que nada de "la vida" que es la programación. Para los que no están interiorizados, es básicamente darle a la computadora una serie de pasos a seguir en un idioma que entienda la computadora para que agarre y haga las cuentas que queremos pero mucho más rápido.

Hay muchas competencias de programación, Olimpíadas presenciales y también problemas para resolver online, con problemas muy relacionados a la matemática, como por ejemplo este podría ser uno. Quizás salen solo haciendo cosas de matemática, o quizás pensando hay que descartar algunas cosas para que la compu no haga cuentas de más (por ejemplo, acá se podía ver que siempre que tuviera todas las cifras distintas, ya era múltiplo de 9, y se ahorraban de que la compu chequeara esa condición).
Para aquellos interesados en la programación, ahora hay un Foro de OIA (Olimpíada Informática Argentina) :

Post en OMA Foros sobre el Foro de la OIA

Re: Regional 2017 N3 P1

Publicado: Sab 01 Jul, 2023 4:41 pm
por Gianni De Rico
Detesté este problema cuando me tocó rendirlo y lo sigo detestando ahora, pero en algún momento tenía que subir una solución jaja
Spoiler: mostrar
Primero limpiamos todas las pavadas que dice el problema para quedarnos con lo que de verdad nos está pidiendo.

Como un número diverso tiene $10$ dígitos distintos, los mismos son (en algún orden) $0,1,2,3,4,5,6,7,8,9$. Un número es múltiplo de $99$ si y sólo si es múltiplo de $11$ y de $9$. Como la suma de los dígitos de un número diverso es $0+1+2+3+4+5+6+7+8+9=45=9\cdot 5$, tenemos que todos los números diversos son múltiplos de $9$, así que únicamente hay que buscar los que son múltiplos de $11$.
Un número es múltiplo de $11$ si y sólo si la suma de sus dígitos en posiciones pares menos la suma de sus dígitos en posiciones impares es múltiplo de $11$. Como un número diverso tiene $10$ dígitos, hay $5$ en posiciones pares y $5$ en posiciones impares, y como dichos dígitos son todos distintos, la resta que tenemos es al menos $(0+1+2+3+4)-(5+6+7+8+9)=-25$ y a lo sumo $(9+8+7+6+5)-(4+3+2+1+0)=25$. Los únicos múltiplos de $11$ entres $-25$ y $25$ son $-22$, $-11$, $0$, $11$ y $22$, pero como la suma de todos los dígitos es impar, cualquier suma y resta de los dígitos va a ser impar (acá estamos usando que $-1\equiv 1\pmod 2$, pero puede verse también notando que siempre vamos a tener una cantidad impar de impares, así que el resultado nos va a dar impar). Entonces la resta que tenemos puede valer únicamente $11$ o $-11$. En otras palabras, tenemos una resta de la forma $(a+b+c+d+e)-(f+g+h+i+j)=11$ o $(A+B+C+D+E)-(F+G+H+I+J)=-11$, pero multiplicando la segunda opción por $-1$ nos da una resta de la forma $(F+G+H+I+J)-(A+B+C+D+E)=11$, es decir, de la misma forma que la anterior. Entonces solamente tenemos que resolver la ecuación $(a+b+c+d+e)-(f+g+h+i+j)=11$, donde $a,b,c,d,e,f,g,h,i,j$ son los $10$ dígitos. Esta ecuación es $a+b+c+d+e=f+g+h+i+j+11$, y sumando $a+b+c+d+e$ a ambos lados nos queda $2(a+b+c+d+e)=(a+b+c+d+e+f+g+h+i+j)+11$, pero $a+b+c+d+e+f+g+h+i+j=45$ porque es la suma de los $10$ dígitos. Entonces $2(a+b+c+d+e)=45+11=56$, así que $a+b+c+d+e=28$.

En resumen, lo que nos pide el problema es buscar todas las formas de sumar $28$ usando $5$ dígitos distintos, prácticamente nada que ver con lo que nos dice el enunciado original. Acá terminó la parte divertida (sí, limpiar todas las pavadas es lo único divertido que hay acá). Ahora nos toca ser ordenados para buscar las soluciones.

Miremos el mayor dígito de los $5$. Si es $7$ o menos, la suma da como mucho $7+6+5+4+3=25$, así que el mayor dígito tiene que ser $8$ o $9$.
  • Si el mayor dígito es $8$, tenemos que sumar $20$ usando $4$ dígitos distintos y menores que $8$.
    Miremos el mayor dígito de los $4$. Si es $6$ o menos, la suma da como mucho $6+5+4+3=18$, así que el mayor dígito tiene que ser $7$, por lo que tenemos que sumar $13$ con $3$ dígitos distintos y menores que $7$.
    Miremos el mayor dígito de los $3$. Si es $5$ o menos, la suma da como mucho $5+4+3=12$, así que el mayor dígito tiene que ser $6$, por lo que tenemos que sumar $7$ con $2$ dígitos distintos y menores que $6$. Las únicas opciones son $4+3$ y $5+2$.
  • Si el mayor dígito es $9$, tenemos que sumar $19$ usando $4$ dígitos distintos y menores que $9$.
    Miremos el mayor dígito de los $4$. Si es $6$ o menos, la suma da como mucho $6+5+4+3=18$, así que el mayor dígito tiene que ser $7$ u $8$.
    • Si el mayor dígito es $7$, tenemos que sumar $12$ usando $3$ dígitos distintos y menores que $7$.
      Miremos el mayor dígito de los $3$. Si es $4$ o menos, la suma da como mucho $4+3+2=9$, así que el mayor dígito tiene que ser $5$ o $6$.
      • Si el mayor dígito es $5$, tenemos que sumar $7$ usando $2$ dígitos distintos y menores que $5$. La única opción es $4+3$.
      • Si el mayor dígito es $6$, tenemos que sumar $6$ usando $2$ dígitos distintos y menores que $6$. Las únicas opciones son $4+2$ y $5+1$.
    • Si el mayor dígito es $8$, tenemos que sumar $11$ usando $3$ dígitos distintos y menores que $8$.
      Miremos el mayor dígito de los $3$. Si es $4$ o menos, la suma es como mucho $4+3+2=9$, así que el mayor dígito tiene que ser $5$, $6$ o $7$.
      • Si el mayor dígito es $5$, tenemos que sumar $6$ usando $2$ dígitos distintos y menores que $5$. La única opción es $4+2$.
      • Si el mayor dígito es $6$, tenemos que sumar $5$ usando $2$ dígitos distintos y menores que $6$. Las únicas opciones son $3+2$, $4+1$ y $5+0$.
      • Si el mayor dígito es $7$, tenemos que sumar $4$ usando $2$ dígitos distintos y menores que $7$. Las únicas opciones son $3+1$ y $4+0$.
En conclusión, las únicas formas de sumar $28$ con $5$ dígitos distintos son
  1. $8+7+6+4+3$.
  2. $8+7+6+5+2$.
  3. $9+7+5+4+3$.
  4. $9+7+6+4+2$.
  5. $9+7+6+5+1$.
  6. $9+8+5+4+2$.
  7. $9+8+6+3+2$.
  8. $9+8+6+4+1$.
  9. $9+8+6+5+0$.
  10. $9+8+7+3+1$.
  11. $9+8+7+4+0$.
Ahora hay que contar cuántos números diversos podemos armar con cada una. Para eso notamos que, en cada una de ellas, si los dígitos que van en posiciones pares tienen al $0$ (como es el caso de $9+8+6+5+0$ y $9+8+7+4+0$), entonces podemos ordenarlos de $5!$ formas distintas y también podemos ordenar a los dígitos en posiciones impares de $5!$ formas distintas, lo que nos da un total de $5!^2$ formas distintas; mientras que si los dígitos en posiciones impares tienen al $0$, entonces podemos ordenarlos de $5!-4!$ formas distintas (descontamos las $4!$ posibilidades en las que el número empieza con $0$) y podemos ordenar a los dígitos en posiciones impares de $5!$ formas distintas, lo que nos da un total de $5!\cdot (5!-4!)$ formas distintas. Esto era para el caso en el que la resta daba $11$, si la resta da $-11$ tenemos que cambiar los números de las posiciones pares con los de las posiciones impares, de modo que los que antes nos daban $5!^2$ posibilidades ahora nos dan $5!\cdot (5!-4!)$ y los que antes nos daban $5!\cdot (5!-4!)$ ahora nos dan $5!^2$. En total, cada una de las $11$ soluciones nos da ${5!}^2+5!\cdot (5!-4!)=5!\cdot (2\cdot 5!-4!)$, por lo que la cantidad de números diversos que son múltiplos de $99$ resulta$$11\cdot 5!\cdot (2\cdot 5!-4!),$$y estamos.

Re: Regional 2017 N3 P1

Publicado: Vie 09 Feb, 2024 11:38 pm
por drynshock
Spoiler: mostrar
Notemos que nuestros números son permutaciones de $1234567890$ ya que solo hay 10 dígitos y nuestro numero tiene todos los dígitos distintos.
También sabemos que $0+1+2+3+4+5+6+7+8+9 = 45$ por lo tanto el numero es divisible entre $9$. Entonces solamente nos interesa si el numero es divisible por 11. Recordemos que el criterio de divisibilidad del 11 es: la suma de los dígitos en una posición par, menos la suma de los dígitos en una posición impar debe ser múltiplo de 11. Para obtener el máximo y mínimo nos queda que: $(9+8+7+6+5) - (4+3+2+1+0) = 25$ y lo mismo pero al revés nos da el mínimo de $-25$. Como la diferencia esta nos tiene que dar múltiplo de 11, los posibles valores son $-22, -11, 0, 11, 22$. Llamemos $S_p$ a la suma de los números que están en posición pare y $S_i$ a la suma de los impares. Con esto podemos plantear un par de sistemas de ecuaciones para ver cuanto nos tiene que dar la suma de cada uno.

$S_p + S_i = 45$
$S_p - S_i = 0$

$S_p + S_i = 45$
$S_p - S_i = 22$

$S_p + S_i = 45$
$S_p - S_i = 11$

No vamos a considerar los múltiplos impares por ahora ya que seria alternar $S_p - S_i$.

Caso $S_p - S_i = 0
$2S_p = 45$
$S_p \notin \mathbb Z$
Por lo que no hay solución.

Caso $S_p - S_i = 22
$2S_p = 67$
$S_p \notin \mathbb Z$
Por lo que no hay solución.

Caso $S_p - S_i = 11
$2S_p = 56$
$S_p = 28 \land S_i = 17$

Sabiendo que $S_i = 17$ podemos concluir lo siguiente, al haber 5 números que están en posición impar, para que la suma sea también impar debemos tener:
Caso 1) iiiii (5 Números impares)
Caso 2) PPPPi (4 pares, 1 impar)
Caso 3) PPiii (2 pares, 3 impares)
El caso uno lo podemos descartar ya que $S_i = 1+3+5+7+9 = 25$

Veamos el caso 2:
Si tenemos 8624 i la suma excede los 17, por lo tanto el numero 0 debe aparecer si o si.
Probando con los pocos casos que quedan tenemos que los números que cumplen son:
86201
84203
84205
Notemos que estos son los números en posición impar, pongamos al lado los números en posición par.
86201 |34579
84203 |15679
84205 |13679
Supongamos que queremos calcular las permutaciones del primer caso, 86201 tiene $5!$ permutaciones y 34579 también tiene $5!$. Sin embargo recordemos que si intercambiamos todas las posiciones impares con las pares también vamos a obtener un numero múltiplo de 11. Entonces también debemos considerar el caso 34579 | 86201. Las permutaciones de 34579 son $5!$ sin embargo las de $86201$ son $4.4!$ ya que el 0 no puede ir en el primer lugar. Si sumamos todos los casos posibles para este mismo numero nos queda que $5!.5! + 5!.4.4! = 25920$. Concluimos entonces que cada numero tiene 25920 permutaciones totales, ahora si buscamos cuantos números distintos tenemos podemos calcular las permutaciones totales.
Para el caso 2 sabemos que hay 3 números.

Caso 3) Procedo a enunciarlos, sin embargo no conozco una forma fácil de calcular todos mas que a mano.
95120 |
93140 |
75320 |
75140 |
73160 |
73142 |
53180 |
53162 |
En total el caso 2 tiene 8 números.

Veamos que si sumamos el caso 2 con el 3 nos quedan 11 números distintos, si multiplicamos 11 con la cantidad de permutaciones ya estamos.
$11.25920 = 285120$

Nota: Notemos que en el caso 3 hay dos números que inicialmente no tienen el 0, sin embargo como después tenemos que invertir pares e impares nos queda la misma cantidad de permutaciones.