Estoy atascado en un problema relacionado con galerías de arte. Es problema de $12$ en el capítulo sobre las galerías de arte en Cómo proteger una Galería de Arte y Otros Matemáticos Discretos Aventuras por T. S. Michael (yo revisamos un poco la pregunta, sobre todo a la introducción de anotaciones $k$$n$):
Post $k=10$ guardias en una particular galería de arte con $n=17$ paredes de modo que el conjunto de la galería está protegido, pero el despido de cualquier guardia sale de alguna parte de la galería sin protección.
La dificultad está claro que la galería de arte en el problema es una incógnita que debe ser determinado. He probado muchos ejemplos de galerías con $17$ paredes, pero hasta el momento, sólo puedo encontrar un ejemplo para el problema más sencillo con $k=8$ (una estrella en forma de galería).
Alguna idea?
De fondo si usted no sabe acerca de galerías de arte, pero quiero tratar de resolver el problema:
- Una galería de arte con $n$ paredes está representado por un nonconvex polígono con $n$ bordes.
- Un guardia está representada por un punto. El protector puede ser colocado en cualquier lugar en la galería, a lo largo de una pared o en un vértice.
- Los guardias no se puede mover, pero se puede ver todo a su alrededor (a la vez!). Que Un punto de $p$ en el interior de la galería es visto por un guardia de $g$ si $[p,q)$ está contenida en el interior de la galería.
- Una galería está protegido si en cualquier punto de su interior es visto por al menos uno de los de la guardia.
