Pondré dos problemas que se me hicieron sencillos, pero que con una buena construcción salen en un instante:
1) Sean n y k enteros positivos. Están dadas n circunferencias, todas se intersectan dos a dos en un par distinto de puntos. Cada punto de intersección se pinta de uno de n colores distintos tal que cada color sea utilizado almenos una vez, y exactamente k colores distintos aparecen en cada circunferencia. Encuentra todos los valores de k para toda n$\geq$2 tal que haya una construcción posible.
2) Se tiene una gráfica completa de n vértices. Un paso es escoger un ciclo de longitud 4 (si existe alguno) y se le elimina una de las aristas que la conforma. Determina el menor número de aristas que se pueden dejar en la gráfica después de varios pasos.
viernes, 13 de mayo de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
3 comentarios:
1) Aun no lo termino, pero se como constuir para k mayor a la mitad de n
2) podemos ver facilmente por indución que podemos dejar n aristas, y tenia un argumento de que no se podian menos, pero creo esta mal, voy a intentar corregirlo
No se si alguien lo siga intentando, pero pues doy los Hints:
1)Usar una inducción para mostrar que para $n\geq 3$, funciona todo k tq $3\leq k \leq n$
2)Como Daniel usar inducción, o mi método fue hacer la construcción con una tabla de nxn. Para lo que te falta Daniel, yo use un tablero para demostrar que no se podía, usando que (el número de renglones usados)<(número de aristas)
1) No ma, tmabien se puede con 3?, lo voy a intentar.
2) no entiendo como un tablero?
Publicar un comentario