He estado trabajando en ejercicios en un libro de combinatoria y he llegado a un problema con el que tengo dificultades. El problema dice:
"Se nos da rectas en el plano, en posición general, es decir, st no hay dos de ellas paralelas y no hay tres de ellas que pasen por el mismo punto. Calcule el número de regiones en que estas líneas dividen el plano".
En las pistas dice que hay distintos puntos de intersección para las líneas. Luego hablan de elegir una línea. que no es paralela a ninguna recta que pase por dos de estos puntos. Hay, pues, dos clases de regiones: las que poseen un punto más alto con respecto a - que es necesariamente uno de los puntos de intersección de los líneas dadas-- y las que no poseen un punto más alto. Dicen que un paso de la solución es mostrar que existe una biyección entre las regiones de primera especie y el conjunto formado por las puntos. El segundo paso es mostrar que hay exactamente regiones del segundo tipo, de modo que el número total de regiones es igual a .
¿Puede alguien mostrarme cómo construir la biyección a la que se hace referencia en la pista y cómo determinar que hay regiones del segundo tipo?
Pista. Cada punto de intersección es el punto más profundo de exactamente una parte. Las partes sin puntos más profundos no están limitadas por debajo y cortan una línea horizontal (que introducimos) en piezas. En el contexto de las Olimpiadas, la gente suele referirse a esta propiedad como "Principio Extremo".
Antón Grudkin
Brian M Scott