Problemas de coloreo

    1) En el depósito de una ferretería se deben almacenar 10 sustancias distintas, entre las cuales, hay algunas que no pueden ser almacenadas en el mismo compartimiento del depósito. Las 10 sustancias se distinguen con los números del 1 al 10 y en el cuadro se expresan las sustancias que NO pueden estar juntas en un mismo compartimiento.

	1	2	3	4	5	6	7	8	9	10
1		X	X	X
2	X						X		X
3	X							X		X
4	X				X	X
5				X				X	X
6				X			X			X
7		X				X		X
8			X		X		X		X	X
9		X			X			X
10			X			X		X

a)  Determinar el mínimo número de compartimientos que se necesitan para almacenar de forma segura estas diez sustancias.

b)  ¿Podría eliminar alguna sustancia de forma tal que se utilicen menos compartimientos que en el caso anterior?

2) Un grupo de egresados de la Licenciatura en Turismo de la UNR ha iniciado un emprendimiento de paseos turísticos en la ciudad de Rosario y sus alrededores, ofreciendo recorridos personalizados de acuerdo al gusto e interés del cliente. No cuentan con una flota de minibuses propios, sino que se los alquilan a una compañía de renta, de acuerdo a la necesidad. Por el trato que negociaron con la compañía, el alquiler de cada vehículo no es por hora sino por una jornada completa de 6 a 23 hs.

Para el próximo sábado tiene 8 paseos previstos, con estos horarios:

Paseo 1: 8 a 11 hs                    Paseo 2: 9 a 14 hs         Paseo 3: 10 a 12 hs

Paseo 4: 13 a 17 hs      Paseo 5: 13 a 18 hs        Paseo 6: 16 a 20 hs

Paseo 7: 19 a 21 hs    Paseo 8: 19 a 22 hs.

Cada uno de dichos paseos concertados será para pequeños grupos, por lo que bastará la capacidad de un minibús para realizarlo. Así, dos paseos que no tengan sus horarios solapados pueden realizarse con un mismo minibús. ¿Cuál es el mínimo número de minibuses que precisan alquilar ese día? De una distribución posible de los paseos con los minibuses alquilados.