Monedas optimas

[carroza]

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

[Richard R Richard]

Re: Monedas optimas

Bonito problema ,

Ocultar contenido

Mostrar solución Ocultar solución

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

[carroza]

Re: Monedas optimas

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

Ocultar contenido

Mostrar solución Ocultar solución

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.

[Richard R Richard]

Re: Monedas optimas

Hola carroza

Ocultar contenido

Mostrar solución Ocultar solución

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

[carroza]

Re: Monedas optimas

Perfecto r3.

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

[Richard R Richard]

Re: Monedas optimas

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

Ocultar contenido

Mostrar solución Ocultar solución

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

[carroza]

Re: Monedas optimas

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

Un saludo

[Richard R Richard]

Re: Monedas optimas

Ocultar contenido

Mostrar solución Ocultar solución

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