Tengo que indicar de antemano que aunque tengo una idea para resolver el problema, aun no he comprovado el buen funcionamiento de ésta. Así que éste problema, más que ser un concurso, es un inicio de debate para solucionarlo entre todo aquel que quiera participar.
Enunciado del problema:
Ruslan tiene K amigos. Y todos ellos cumplen años mañana. Ayer Ruslan compró N álbums de fotos y los quiere repartir entre sus amigos. Por supuesto que no puede dar menos de un álbum de fotos a qualquiera de sus amigos (puesto que supondria no dar ningun regalo a alguno de los amigos). Se pide calcular cuantas maneras posibles hay de hacerlo.
Observaciones: Todos los álbums de fotos son diferentes. Dos distribuciones son consideradas la misma si solo difieren por el orden de los álbums regalados a una persona o las personas que reciben los regalos.
Ejemplo:
Sea K = 2 y N = 3.
A los álbums de fotos los llamaremos A, B y C. Las posibles maneras de distribuir los álbums son:
Amigo 1: A; Amigo 2: B, C;
Amigo 1: B; Amigo 2: A, C;
Amigo 1: C; Amigo 2: A, B;
Las distribuciones
Amigo 1: A; Amigo 2: B, C; y
Amigo 1: A; Amigo 2: C, B; son consideradas la misma, igual que las distribuciones
Amigo 1: A; Amigo 2: B, C; y
Amigo 1: C, B; Amigo 2: A;
Encontrareis el problema en la web: http://acm.sgu.ru/problem.php?contest=0&problem=441
11 comentarios:
Se me ocurre lo siguiente, Sara:
Primero realizas la diferencia N-K. Con esto ya has entregado a cada amigo su primer álbum. Ahora tienes el mismo problema pero con la condición de entregar álbumes a tu gusto: puedes entregar cero álbumes a algunos amigos.
Luego, como sólo te importa la cantidad que cada uno recibirá (según el enunciado) este problema equivale al siguiente que es muy conocido:
Encontrar cuántas disposiciones existen de K-1 palitos y N-K bolitas en una fila. Los K-1 palitos separan las asignaciones de los K amigos puestos por orden alfabético, por ejemplo.
El número que se obtiene es:
(N-1)!/((N-K)!(K-1)!), donde el valor N-1 viene de sumar (N-K)+(K-1) y el símbolo "!" refiere al factorial.
Por supuesto, cuando en la disposición aparecen dos "palitos" juntos es que has entregado cero álbumes a ese amigo después de darle el primero.
Un saludo cordial desde Buenos Aires.
Perdón, Sara. Creo que me olvidé en mi respuesta de la última condición: la que decía que dos distribuciones eran consideradas iguales si cierto conjunto de álbumes lo recibía un amigo u otro y... ahora que lo pienso: ¡que los álbumes eran distinguibles!(pero que no importaba el orden en que un determinado amigo los recibiera).
Realmente fue una ingenuidad de mi parte creer que pudieras tener alguna duda con un enunciado como el que yo imaginé leer.
Seguiré pensando.
Saludos cordiales.
Como bien dices, Roberto, éstas dos condiciones hacen que el problema se complique notablemente.
Hasta ahora no he dado con ninguna fórmula matemática cerrada que dé buenos resultados, pero he dado con una recurrencia, aunque no se si sirve... aquí la comento:
Para un K y N determinados, si K = N entonces solamente hay una manera de distribuir los albumes (un album para cada amigo).
Si K = 1, hay igulamente una sola manera de distribuirlos (todos los albumes al mismo amigo).
Para cualquier otro K (donde se cumpla 1 < K < N), las formas de distribuir los albumes son K*i + j.
Donde i es el total de formas de distribuir N-1 albumes a K amigos y j es el total de formas de distribuir N-1 albumes a K-1 amigos.
Ésta fórmula se da mediante el siguiente razonamiento:
Supongamos que conozco el número de maneras de dar N-1 albumes a cualquier número de amigos menor o igual que K.
Ahora, con un álbum más, quiero saber las fórmas de dar N álbums a K amigos.
Éste nuevo álbum que doy lo puedo dar a un amigo junto a otros álbumes (por cada manera de dar N-1 álbumes a K amigos, K maneras de dar N álbumes a K amigos) o puedo darlo solo (entonces los otros N-1 álbumes se tienen que distribuir entre K-1 amigos). Como no hay más maneras de colocar éste nuevo álbum, si declaramos una funcion f:NxN -> N tal que f(N, K) = maneras de dar N albumes a K amigos segun el enunciado, tenemos que:
f(N, K) = K*f(N-1, K) + f(N-1, K-1).
De momento éste ha sido mi razonamiento para solucionar el problema... lamentablemente parece que es erroneo, puesto que el juez online de la página web de donde lo saqué me dice que falla en segun que casos. Además, tendría que buscarse una manera más eficaz de calcular el resultado, puesto que el número de álbumes que se dan puede llegar a 1000000000 (aunque el número de amigos es como máximo 10) y un ordenador tarda lo suyo en hacer tantos cálculos.
A ver si entre todos encontramos la solución.
Un saludo.
Sara, te consulto si tú ya tienes la respuesta. Ocurre que tengo algunas ideas para avanzar en la resolución y creo que pueden servir, pero va a llevar cierto tiempo más pasarlas en limpio.
Espero tus noticias.
Un saludo cordial.
Yo aun no tengo la respuesta, he probado algunos caminos para llegar a la resolución de éste problema, pero hasta ahora no me convence ninguno...
Espero impaciente tus propuestas, Roberto. Seguro que son muy interesantes.
Saludos, Sara
Sara, tengo que pasar un poco en limpio y entender bien una conversación que tuve con una profesora de aquí que sabe mucho del tema. Pero en Buenos Aires ya es muy tarde y voy a tratar de hacer esto entre mañana viernes y el sábado.
Saludos cordiales.
Todavía no tengo la solución, Sara.
Pero sigo pensando.
Un saludo cordial desde Buenos Aires.
Sara, te consulto: ¿finalmente hallaste la solución a este problema?
Un saludo cordial desde Buenos Aires.
Hola Roberto. Al final conseguí resolver el problema. La solución es la que describí en un comentario, lo que pasa es que los números eran demasiado grandes y sólo hacía falta encontrar un ciclo para hallar rápidamente las soluciones.
Saludos cordiales.
Sara, ¿o sea que se resolvía mediante una recursión que para números grandes requería instrumentarla computacionalmente?
Si es así, creo que era imposible para mí.
Saludos cordiales.
Publicar un comentario