Resultados 1 al 8 de 8

Hilo: Monedas optimas

  1. #1
    Registro
    Jul 2007
    Posts
    2 598
    Nivel
    Doctor en Física
    Artículos de blog
    1
    ¡Gracias!
    1 346 (1 032 msgs.)

    Predeterminado Monedas optimas

    Hola a todos.

    Los que tenemos una cierta edad, recordaremos las pesetas. En particular las denominaciones de las monedas, que eran de una peseta, cinco pesetas (un duro), veinticinco pesetas, cincuenta pesetas, y más adelante la de 100 pesetas.

    Este sistema, era poco racional, en el sentido de que se necesitaban muchas monedas para formar una cantidad determinada. Por ejemplo, cuatro monedas para fijar cuatro pesetas, 6 monedas para tener 14 pesetas.

    Posteriormente, con el euro se puso un sistema más racional. Fijandonos solo en los céntimos, tenemos monedas de 1,2,5,10,20,50, .Con estas divisiones, es posible hacer combinaciones de cualquier cantidad con, relativamente, pocas monedas.

    A partir de esto, dejadme que os plasntee dos problemas: Uno más fácil y otro más dificil.

    El fácil: Con las denominaciones actuales (1,2,5,10,20,50), Dadas N (con N desde 1 hasta 6) monedas, de cualquier denominación (repetidas o no), cuál es la máxima cantidad M tal que podemos conseguir todas las cantidades desde 1 hasta M, usando un máximo de N monedas.

    Un ejemplo: Con N=1, M sale 2. Con N=2, M sale 7.

    El dificil: Como podemos modificar las denominaciones actuales (es decir, si por ejemplo cambiamos la moneda de 10 centimos por una de 17 centimos) , para conseguir que la cantidad M descrita anteriormente sea lo mayor posible, para cada N


    Un saludo

  2. #2
    Registro
    Mar 2015
    Ubicación
    Lujan Buenos Aires Argentina
    Posts
    3 708
    Nivel
    Universidad (Ingeniería)
    Artículos de blog
    39
    ¡Gracias!
    1 724 (1 547 msgs.)

    Predeterminado Re: Monedas optimas

    Bonito problema ,
    Contenido oculto


    Vamos por el fácil

    con denominaciones 1,2,5,10,20,50 tenemos la máxima suma para
    N maxima suma
    1 2
    2 7
    3 17
    4 37
    5 87
    6 137


    El dificil


    con N=1 monedas el máximo sería lograble es 6 con denominaciones 1,2,3,4,5,6, pero intuyo que el problema pasa por usar una única denominación y lograr lo que mas se puede en cada N

    esto se me hace que se encara por " investigación operativa, una serie de ecuaciones lineales, con una función objetivo a maximizar, aun no veo como...le seguire dando vueltas

    para N=2 intuí la serie de fibonacci, pero encontre una combinación que dio mejor

    mis intentos hasta ahora pero no desisto ... lo posteo para que sepas que demuestro interes en resolverlo, pero aun ni idea de como encontrar el maximo


    N denominaciones maxima suma no se forma
    1 1,2,3,4,5,6 6 7
    2 1,2,3,5,8,13 11 12
    2' 1,2,3,4,7,11 15 16
    2'' 1,2,3,7,11,15 18 19
    3 1,2,4,10,13,16 18 19
    4 1,5,9,13,17,21 24 25
    5 1,6,11,16,21,26 30 31
    6 1,7,13,19,25,31 36 37


    Saludos \mathbb {R}^3

  3. #3
    Registro
    Jul 2007
    Posts
    2 598
    Nivel
    Doctor en Física
    Artículos de blog
    1
    ¡Gracias!
    1 346 (1 032 msgs.)

    Predeterminado Re: Monedas optimas

    Hola. R3, gracias por participar. Una pista para el problema difícil.
    Contenido oculto

    Yo lo enfoco de forma iterativa.

    - Si tenemos una moneda, de una denominación, es obvio que esa moneda debe ser de 1.

    - Si tenemos dos monedas, de dos denominaciones, la primera debe ser 1 por lo anterior.

    Con solo la moneda de 1, puedo conseguir hasta M=2 (1, 1+1), con lo que la siguiente denominación debe ser, como máximo 3. Esto me permite, con 2 monedas, tener hasta M=4 (1, 1+1, 3, 3+1).

    Sin embargo, también podría hacer que la segunda moneda fuera 2, y también llegaría hasta M=4 (1, 2, 1+2, 2+2).

    - Si tenemos tres monedas, parto de los casos anteriores, a partir de ellos llego a que la siguiente moneda, como máximo, debe ser 5. Con ello, veo los dos casos anteriores, y me quedo con el que llegue a un M más alto.

    A ver si tu solución, para 6 monedas, o para un numero arbitrario de ellas, te sale como a mí. Es una serie muy curiosa.


  4. El siguiente usuario da las gracias a carroza por este mensaje tan útil:

    Richard R Richard (01/11/2018)

  5. #4
    Registro
    Mar 2015
    Ubicación
    Lujan Buenos Aires Argentina
    Posts
    3 708
    Nivel
    Universidad (Ingeniería)
    Artículos de blog
    39
    ¡Gracias!
    1 724 (1 547 msgs.)

    Predeterminado Re: Monedas optimas

    Hola carroza
    Contenido oculto


    mi solución para el problema difícil es que la denominación debe ser 1,2,5,13,34,89

    con ello el máximo alcanzable es


    N Denominaciones Máxima suma
    1 1,2,5,13,34,89 2
    2 1,2,5,13,34,89 7
    3 1,2,5,13,34,89 20
    4 1,2,5,13,34,89 54
    5 1,2,5,13,34,89 143
    6 1,2,5,13,34,89 232


    La regla para las máximas sumas para cada N con su denominación D_i

    MS_N=\left[\dst\sum\limits_{i=1}^{N+1}D_i\right]-1

    y la regla para las denominaciones

    D_{N+1}=D_N+\dst\sum\limits_{i=1}^{N}D_i


    una tabla con las siguientes denominaciones y las maximas sumas si se permiten mas denominaciones

    N Denom Max Suma
    1 1 2
    2 2 7
    3 5 20
    4 13 54
    5 34 143
    6 89 376(*)
    7 233 986
    8 610 2583
    9 1597 6764
    10 4181 17710
    11 10946 46367
    12 28657 121392
    13 75025 317810
    14 196418 832039
    15 514229 2178308
    16 1346269 5702886
    17 3524578 14930351
    18 9227465 39088168


    * ese valor se alcanza si se puede contar con la siguiente denominación de monedas N=7 y solo usar 6
    Última edición por Richard R Richard; 01/11/2018 a las 01:57:56.
    Saludos \mathbb {R}^3

  6. El siguiente usuario da las gracias a Richard R Richard por este mensaje tan útil:

    Maq77 (01/11/2018)

  7. #5
    Registro
    Jul 2007
    Posts
    2 598
    Nivel
    Doctor en Física
    Artículos de blog
    1
    ¡Gracias!
    1 346 (1 032 msgs.)

    Predeterminado Re: Monedas optimas

    Perfecto r3.

    A qué te suena la secuencia de valores de las monedas?

  8. #6
    Registro
    Mar 2015
    Ubicación
    Lujan Buenos Aires Argentina
    Posts
    3 708
    Nivel
    Universidad (Ingeniería)
    Artículos de blog
    39
    ¡Gracias!
    1 724 (1 547 msgs.)

    Predeterminado Re: Monedas optimas

    Se me hacia difícil reconocerla por la falta del 8, pero es

    Contenido oculto

    Es una serie de fibonacci, para todos los n impares es decir si F_{(N)} es la serie de Fibonacci=1,1,2,3,5,8,13,21,34,55,89,etc

    la solucion es F_{(2n-1)} \,\to\,n\in [1,6]

    Saludos
    Saludos \mathbb {R}^3

  9. #7
    Registro
    Jul 2007
    Posts
    2 598
    Nivel
    Doctor en Física
    Artículos de blog
    1
    ¡Gracias!
    1 346 (1 032 msgs.)

    Predeterminado Re: Monedas optimas

    Perfecto. Y, a qué te suena la serie de los valores de las máximas sumas obtenidas?

    Un saludo

  10. #8
    Registro
    Mar 2015
    Ubicación
    Lujan Buenos Aires Argentina
    Posts
    3 708
    Nivel
    Universidad (Ingeniería)
    Artículos de blog
    39
    ¡Gracias!
    1 724 (1 547 msgs.)

    Predeterminado Re: Monedas optimas

    Contenido oculto
    Las denominaciones responden a una serie de fibonacci, para todos los n impares F_{(2n-1)} \,\to\,n\in [1,6]


    Y la de las sumas es F_{(2n)}-1 \,\to\,n\in [1,6]
    Vale la pena aclarar que los valores de la serie se alcanzan si se dispone siempre de una de una moneda con la denominación correspondiente al orden n+1.
    Eso hace que alcancemos 233 y no 376 para n=6
    Última edición por Richard R Richard; 02/11/2018 a las 11:12:28.
    Saludos \mathbb {R}^3

Información del hilo

Usuarios viendo este hilo

Ahora hay 1 usuarios viendo este hilo. (0 miembros y 1 visitantes)

Hilos similares

  1. Caja con monedas
    Por jogares en foro Problemas de ingenio
    Respuestas: 18
    Último mensaje: 06/11/2015, 08:38:25
  2. Secundaria sencillito, frecuencia relativa: lanzar 2 monedas
    Por javier m en foro Probabilidad y estadística
    Respuestas: 7
    Último mensaje: 03/09/2010, 18:13:54
  3. Secundaria Al lanzar 2 monedas, que posibilidad hay que en una de ellas salga cara?
    Por javier m en foro Probabilidad y estadística
    Respuestas: 2
    Último mensaje: 30/05/2010, 00:56:41

Permisos de publicación

  • No puedes crear hilos
  • No puedes responder
  • No puedes adjuntar archivos
  • No puedes editar tus mensajes
  •