**IAIC** Colección Genérica de Problemas: Representación # Lista de Problemas 1. **Problema de las 2 Jarras: ** Se tienen dos jarras de agua, una de $4$ litros y otra de $3$ litros sin escala de medición. Se desea obtener $2$ litros de agua en la jarra de $4$ litros. Las operaciones válidas son: llenar completamente cada una de las jarras, vaciar completamente una de las jarras, pasar agua de una jarra a otra (hasta que la primera se vacía o la segunda se llena). 2. **Misioneros y Caníbales:** Hay $3$ misioneros y $3$ caníbales a la orilla de un río. Tienen una canoa con capacidad para dos personas como máximo. Se desea que los seis crucen el río, pero hay que considerar que no debe haber más caníbales que misioneros en ningún sitio porque entonces los caníbales se comerían a los misioneros. Además, la canoa siempre debe ser conducida por alguien (no puede cruzar el río sola). 3. **El Granjero:** Un granjero va al mercado y compra un lobo, una oveja y una col. Para volver a su casa tiene que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras. Si el lobo se queda solo con la oveja, se la come, si la oveja se queda sola con la col, se la come. El reto del granjero es cruzar el río con todas sus compras. ¿Cómo puede hacerlo? 4. **Problema del coloreado de Mapas:** Fijado un grafo, $G$, con un etiquetado dado y una función $vecinos?(x,y)$ que indica si los nodos $x$ e $y$ son vecinos en $G$ (es decir, si están conectados por una arista del grafo), determina (y en caso positivo, proporciona) si existe un coloreado válido de $G$ haciendo uso de $K$ colores. (Un coloreado es una asignación de colores a nodos, y es válido si nodos vecinos están coloreados con colores distintos). 5. **Problema de las $3$ Jarras:** Se tienen $3$ jarras de $12$, $8$ y $3$ litros de capacidad y un grifo. Las operaciones que se pueden realizar con ellas son: llenar cada una de las jarras de agua, volcar el contenido de una en cualquier otra (hasta que una se vacía o la otra se llena), o bien vaciar su contenido en el suelo. El objetivo es conseguir exactamente $1$ litro en alguna de las jarras. 6. **Todos los dígitos del Rey**: Dado el conjunto de dígitos $0123456789$, inserta los símbolos de los operadores aritméticos ($\times + - /,$) y paréntesis entre ellos para que la expresión resultante se evalúe como 100. Por ejemplo: $$0+1+2+3+4+5+6+7+(8\times 9) =100$$ ¿Puedes encontrar alguna otra solución? 7. Un **cuadrado mágico** consiste en una distribución de números en filas y columnas, formando un cuadrado, de forma que los números de cada fila, columna y diagonal suman lo mismo. Aunque es posible recrear diferentes tipos de cuadrados mágicos, tradicionalmente se forman con los números naturales desde el $1$ hasta $n^2$, donde $n$ es el lado del cuadrado. Representa el problema de generación automática de cuadrados mágicos de tamaño $n$ como un problema de espacio de estados. ¿Cuál sería su factor de ramificación y profundidad? 8. Tenemos $10$ cartas numeradas del $1$ al $10$. Sepáralas en $2$ montones de forma que la suma de las cartas del primer montón esté _lo más cerca posible_ de $36$ y el producto de las cartas del segundo montón esté lo más cerca posible de $360$. 9. El problema del **$8$-puzzle:** es un puzle de deslizamiento que consiste en un conjunto de $8$ piezas en un marco de tamaño $3\times 3$, por lo que queda un hueco libre. El objetivo del puzle consiste en encontrar la sucesión de movimientos (moviendo piezas al hueco libre) que llevan la distribución inicial a una distribución ordenada prefijada. Se pueden pensar variantes con $n\times n$ huecos. por ejemplo, el 15-puzzle. 10. **Torres de Hanoi:** Se tienen $N$ discos de distinto tamaño apilados sobre una base $A$ de manera que cada disco se encuentra sobre uno de mayor radio. Existen otras dos bases vacías $B$ y $C$. Haciendo uso únicamente de las 3 bases, el objetivo es llevar todos los discos de la base $A$ hasta la base $C$. solo se puede mover un disco a la vez, y cada disco puede descansar solamente en las bases o sobre otro disco de tamaño superior, pero no en el suelo. El más habitual es $N=3$. 11. **Problema de las N reinas:** Sitúar $N$ reinas en un tablero de ajedrez de tamaño $N\times N$ sin que se amenacen entre ellas. Una reina amenaza a otra si ambas están en la misma fila, columna o diagonal. El caso más común es el de $N=8$, el trablero de ajedrez estándar. 13. Dados cuatro números naturales $n$, $m$, $r$ y $T$, encontrar una secuencia mínima de operaciones aritméticas básicas (suma, resta, multiplicación y división) que usando $n$ y $m$ únicamente y partiendo de $0$, obtenga como resultado $T$, con la restricción adicional de que ni $n$ ni $m$ se pueden usar más de $r$ veces. Por ejemplo, si $n = 2$, $m = 3$, $r = 3$ y $T = 28$, una posible solución (no necesariamente mínima) es $((((((0 + 3) × 3) × 2) − 3) × 2) − 2)$, ya que el resultado es $28$ y ni $2$ ni $3$ se han usado más de tres veces cada uno. 14. **Cruce del puente:** Un grupo de $5$ personas quiere cruzar un viejo y estrecho puente. Es una noche cerrada y se necesita llevar una linterna para cruzar, pero el grupo solo dispone de una linterna, a la que le quedan $5$ minutos de batería.Cada persona tarda en cruzar $10$, $30$, $60$, $80$ y $120$ segundos, respectivamente. El puente solo resiste un máximo de $2$ personas cruzando a la vez, y cuando cruzan dos personas juntas caminan a la velocidad del más lento. No se puede lanzar la linterna de un extremo a otro del puente, así que cada vez que crucen dos personas, alguien tiene que volver a cruzar hacia atrás con la linterna a buscar a los compañeros que falten, y repetir este proceso hasta que hayan cruzado todos. ¿Cuál sería una solución válida? 15. **Problema de las bolsas:** Se pretende encontrar una manera de distribuir un conjunto de objetos, $O=\{o_1,\dots,o_n\}$, en bolsas usando el menor número posible de ellas. Cada objeto tiene un peso asociado, $Peso(o_i)=p_i$, y las bolsas tienen un límite de peso máximo soportado, $B$. 16. **Suma nula**: Dado un conjunto de enteros $I=\{i_1,\dots,i_n\}$, el problema es encontrar un subconjunto $S\subseteq I$ que sume $0$. 17. **El juego de las Ranas:** Tenemos $N$ ranas negras y $N$ verdes situadas encima de $2N+1$ nenúfares tal y como muestra la animación (en el caso particular de $N=3$). Comienza cada grupo de ranas en un extremo distinto de la fila de nenúfares. El objetivo consiste en intercambiar la posición de las ranas negras y verdes. Para ello, los movimientos permitidos son los siguientes: a) Una rana puede moverse a un nenúfar adyacente vacío, con coste 1. b) Una rana puede desplazarse a un nenúfar vacío saltando por encima de una rana como máximo, con un coste igual a 2. 18. **Juego de las Cifras (Cifras y Letras):** Dados $6$ números, y un objetivo $O$, encontrar la combinación aritmética entre ellos que se aproxima lo más posible a $O$. 19. Trabajaremos con números de 3 cifras (de $100$ a $999$). Inicialmente, tenemos dos números prefijados, que denotaremos por $S$ (Start) y $G$ (Goal), y un conjunto de números que denotaremos por $P$ (de Prohibidos). En cada turno, podemos transformar un número en otro añadiendo/sustrayendo 1 a uno de sus dígitos (por ejemplo, pasando de $678$ a $679$, o de $234$ a $134$). El coste de cada movimiento es 1. Adicionalmente, tenemos estas restricciones: (a) No se permite añadir $1$ a $9$, ni sustraer $1$ a $0$. (b) No se permite convertir un número en un elemento de $P$ (están prohibidos). (c) No se puede cambiar un mismo dígito 2 veces seguidas. Además de dar la representación general, resuelve el caso particular $S = 567$, $G = 777$ y $P = \{666, 667\}$. 20. Un grupo de $N$ personas de diferentes países se sienta en una mesa circular con $N$ sillas. Cada persona sabe hablar dos idiomas (no necesariamente los mismos para todos). Se trata de encontrar una disposición para sentarse de manera que cada persona pueda comunicarse con sus dos vecinos en la mesa. 21. **El Problema del Viajante:** Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad origen? 22. Un ayuntamiento tiene que adjudicar 10 proyectos de obra mediante concurso público. Se han presentado al concurso 5 empresas, dando presupuestos para cada uno de los diez proyectos. La adjudicación debe realizarse de manera que a cada empresa solo se le concedan dos proyectos. Encuentra la adjudicación de menor precio. 23. Un ganadero tiene un rebaño de ovejas. Cada oveja tiene un peso y se vende por un precio prefijado. El ganadero dispone de un camión que es capaz de cargar un peso máximo. Su problema es seleccionar una colección de ovejas para llevarlas al mercado de ganado en el camión, de manera que se maximice el precio total de las ovejas transportadas, sin superar el peso total soportado por el camión. 24. Usa algún método de optimización para conseguir un buen [autómata celular](http://www.cs.us.es/~fsancho/?e=66) 1D que resuelva de la mejor forma posible (cometerá errores) el problema de la mayoría. (Ayuda: usa la representación binaria de las reglas del autómata como conjunto de genes del individuo). 25. **Problema de asignación de tareas:** Hay un número de agentes ($\{a_i: 1\leq i\leq n\}$) y un número de tareas a realizar ($\{t_j: 1\leq j \leq m\}$). Cualquier agente puede ser asignado para desarrollar cualquier tarea, cuya ejecución supone un coste ($c_{ij}$) que puede variar dependiendo del agente, $a_i$, y la tarea, $t_j$, asignada. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total de la asignación sea minimizado, aunque un mismo agente podría realizar más de una tarea, pero ha de tenerse en cuenta que la realización de la tarea $t_j$ por el agente $a_i$ conlleva el uso de una serie de recursos ($r_{ij}$) del agente, y estos están acotados por una cantidad fija, $b_i$, para cada agente. Encuentra una asignación de tareas factible y de coste mínimo. 26. Tenemos una lista que representa los pesos de una población (todos los pesos están entre 0 y 100). Queremos encontrar 3 números (0 < a1 < a2 < a3 < 100) que sirvan para dividir el conjunto anterior en 4 secciones: $[0,a1), [a1,a2), [a2,a3),[a3,100)$, de forma que las sumas de los pesos que hay en cada sección sean _lo más parecidas posibles_. ¿Qué cambios harías para encontrar una división similar en $K$ secciones? 27. Disponemos de un CD de $N$ minutos de duración y queremos grabar el mayor tiempo posible de nuestra colección de $M$ canciones. Queremos saber qué pistas debemos grabar. Las duraciones en minutos de las canciones se dan en una lista $(d_1,\dots,d_{M})$. Modifica la solución anterior para que, además, obtengamos un CD con el estilo más uniforme posible. El estilo de una canción viene dado por un código numérico. Dos estilos son más parecidos si sus códigos son más cercanos. El estilo de las canciones de nuestra colección viene dado por una lista: $(e_1,\dots,e_{M})$. 28. **Problema de Optimización de Tareas:** Tenemos $N$ tareas, $\{T_1,\dots,T_N\}$, que se encargan de procesar datos. Podemos hacer uso de un procesador que NO tiene capacidad paralela.Cada tarea, $T_i$, tarda un tiempo $t_i$ en ejecutarse, y hasta que no termina una tarea, no puede lanzarse otra. Cada tarea solo se puede ejecutar 1 vez. Disponemos de un tiempo total, $T$, para poder usar el procesador. Además, la ejecución de cada tarea, $T_i$, consume $D_i$ datos. Algunas tareas solo se pueden ejecutar si algunas otras se han ejecutado antes. Para saber cuáles, disponemos de una tabla que indica si una tarea necesita que otra tarea se haya ejecutado antes. Por ejemplo, la siguiente tabla indica que $T_1$ necesita que $T_2$ se haya ejecutado antes, $T_2$ necesita que $T_4$ se haya ejecutado antes, y $T_3$ necesita que $T_1$ se haya ejecutado antes: | | $T_1$ | $T_2$ | $T_3$ | $T_4$ | |---------|---------|---------|---------|---------| | $T_1$ | $0$ | $1$ | $0$ | $0$ | | $T_2$ | $0$ | $0$ | $0$ | $1$ | | $T_3$ | $1$ | $0$ | $0$ | $0$ | | $T_4$ | $0$ | $0$ | $0$ | $0$ | Objetivo: Obtén una secuencia de ejecuciones que consuma la máxima cantidad de datos en el tiempo total permitido. 29. **Sudoku:** Este problema se publicó en Nueva York en el año 1979 bajo el nombre de *Number Place* y se hizo popular en Japón con el nombre de sudoku (*Sudji wa dokushin ni kagiru*: *los números deben aparecer una vez*). En el problema del sudoku, hay que rellenar las casillas de un tablero de $9 \times 9$ con números del $1$ al $9$, de forma que no se repita ningún número en la misma fila, columna, o subcuadro de 3 × 3 que componen el sudoku. Es habitual que se den algunas casillas ya rellenas. 30. **Problema de agrupamiento I**: Agrupa $N$ números en $k$ grupos disjuntos minimizando la suma de las diferencias entre los grupos. 31. **Problema de agrupamiento II**: Reparte los $N^2$ primeros números naturales en una matriz cuadrada $N\times,N$ de tal manera que las sumas tanto por filas como por columnas coincidan. 32. **Problema de emplazamiento de bloques rectangulares**: Dado un conjunto de $n$ bloques rectangulares de distintas anchuras y alturas, se trata de encontrar un emplazamiento (asignación de los centros de los bloques rectangulares a puntos de un espacio cartesiano bidimensional) de tal forma que no haya solapamientos entre los bloques rectangulares, y se minimice la función de coste $f = A + \lambda C$, donde $A$ es el área del rectángulo que engloba todos los bloques rectangulares, $\lambda$ es una constante positiva y $C$ un término de conectividad, $C =\sum_{i=1}^{n-1}\sum_{j=i+1}^n w_{ij} d_{ij}$, siendo $d_{ij}$ la distancia entre los centros de los bloques rectangulares y $w_{ij}$ el coste relacionado al unir el bloque rectangular $i$-ésimo con el bloque rectangular $j$-ésimo. 33. **Particionamientos de un grafo. Problema max-cut. Problema min-cut**. Dado un grafo $G = (V,E)$ sin ciclos, donde cada arista lleva asociado un peso entero positivo, se trata de encontrar una partición de $V$ en dos conjuntos disjuntos, $V_0$ y $V_1$ de tal manera que la suma de los pesos de las aristas que tienen un extremo en $V_0$ y el otro extremo en $V_1$, sea máximo (**problema max-cut**) o mínimo (**problema min-cut**). 34. **Problema del conjunto de vértices independientes**. Dado un grafo $G = (V,E)$, se trata de encontrar el denominado conjunto maximal de vértices independientes, es decir el conjunto $VIM \subseteq V$ de mayor cardinalidad para el cual ninguna de sus aristas se encuentre en $E$. 35. **Problema del Salto del Caballo**. Teniendo un tablero de $N\times N$ casillas y un caballo de ajedrez colocado en una posición inicial cualquiera, consegir que el caballo pase por todas las casillas del tablero una, y sola una vez. 36. **Problema del Dominó I**. Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente. 37. **Problema del Dominó II**. Toma el tablero de ajedrez y tapa con dos monedas los dos cuadros de dos esquinas opuestas. Ahora trata de cubrir todos los demás cuadros con 31 fichas de dominó, cada ficha ocupando dos cuadros contiguos del tablero. Intenta el mismo problema con distintos tamaños de tablero. 38. **El Problema de los matrimonios estables**: Una agencia matrimonial ofrece a sus clientes parejas _estables_. Para conseguirlo, cada cliente debe establecer sus preferencias respecto al resto por medio de una lista con sus favoritos por orden de preferencia, incluyendo todos aquellos en los que puede estar interesado y dejando fuera aquellos que no le interesan en absoluto. A partir de estas listas se deben confeccionar parejas estables. Se entiende por _estable_ el que nadie tenga la tentación de divorciarse porque puede encontrar una pareja mejor que la actual: Si A está emparejado con B y C con D, pero a A le gusta más D que B, y D prefiere A por delante de C, entonces los emparejamientos anteriores no son estables. 39. **¿De quién es esta cebra?** Son cinco casas adosadas, de diferentes colores, habitadas por cinco hombres de diferentes nacionalidades. Cada uno posee un animal diferente, bebe una bebida diferente y fuman una marca de tabaco distinta. Sabiendo la siguiente información, ¿podrías decir quién bebe agua?, ¿de quién es la cebra? 1. El noruego vive en la primera casa. 2. La casa de al lado del noruego es azul. 3. El de la tercera casa bebe leche. 4. El inglés vive en la casa roja. 5. El de la casa verde bebe café. 6. El de la casa amarilla fuma Ducados. 7. La casa blanca está después de la verde. 8. El español tiene un perro. 9. El ucraniano bebe té. 10. El japonés fuma Habanos. 11. El que fuma Fortuna tiene un gato. 12. El que fuma Celtas bebe vino. 13. El vecino del que fuma Chester tiene un canario. 14. El vecino del que fuma Ducados tiene un caballo. 40. **Comprando zapatos**: Enriqueta, al volver del centro comercial, describe felizmente a su amiga Aurora los cuatro pares de zapatos que se ha comprado. A Aurora le encantan todos (las alpargatas de color crudo, los planos fucsia, las bambas moradas y unas sandalias de cuero preciosas), pero Enriqueta no puede recordar en qué tienda compró cada uno (*La granja del pie*, *Tacones a Mogollón*, *El palacio del zapato* o *Muchachas*). ¿Puedes echarles una mano y establecer el orden en el que Enriqueta compró cada par de zapatos, y dónde compró cada uno? Dispones de la siguiente información: 1. Enriqueta sabe que los planos fucsia los compró en *Tacones a Mogollón*. 2. La tienda que visitó inmediatamente después de comprar sus bambas moradas no era *Muchachas*. 3. En *La granja del pie* fue su segunda compra. 4. Dos paradas después de dejar el *Palacio del zapato*, Enriqueta compró sus sandalias de cuero. 41. **La orquesta de Boulika**: Esta orquesta comprende 180 ejecutantes, ¿cuántos no tocan ninguno de estos instrumentos? 1. 6 no tocan más que el violoncello. 2. 24 tocan violocello y violín, pero no viola. 3. 12 tocan violoncello y viola, pero no violín. 4. 6 tocan violín y viola, pero no violoncello. 5. 63 músicos tocan el violín, 54 el violoncelo y 36 la viola. 42. **La perspicacia del inspector Lafrite**: Lafrite está encargado de la investigación sobre un robo de cuadros en una galería de arte. Pidió a Relbou y Gremai, dos de sus asistentes, que le ayudaran en el asunto. Laminvestigación terminó con el arresto de cuatro personas: Jules Rateau, Desiré Lafrange, Michel Boileau y Felicie Ossy. Los interrogatorios los realizan los dos asistentes que vienen a dar su informe, a raíz del cual Lafrite dice: *Si considero que lo que me dicen es cierto, puedo afirmar la culpabilidad de una de las cuatro personas*. ¿Puedes ayudar a los inspectores a encontrar a esa persona?. El informe es: 1. Relbou: *Jules Rateau es inocente, pero estoy seguro de que por lo menos uno de los otros es culpable*. 2. Gremai: *Si Desiré Lafrange es culpable, no hay más que un cómplice, que está entre los demás*. 3. Relbou: *Y si Michel Boileau es culpable, pienso que tiene dos cómplices entre los otros*. 43. Puedes probar otros problemas de la colección: [http://www.csplib.org/Problems/](http://www.csplib.org/Problems/)