$n$ negro y $n$ puntos blancos son dibujados en un plano, por lo que no hay tres de ellos ponen en una línea. Cómo probar que podemos conectar cada punto blanco hasta cierto punto negro por segmento recto de modo que no hay dos segmentos que se intersectan? Cada punto negro debe ser conectada a un punto blanco.
Respuestas
¿Demasiados anuncios?
Considerar los vértices del casco convexo de la serie. Si contiene ambos puntos blancos y negros, también contiene dos consecutivos de puntos blancos y negros que podemos conectar y, a continuación, proceder por inducción sobre el resto del conjunto.
Supongo que todos los vértices son de color negro. Por rotación, podemos asumir que el $x$-coordenadas de los puntos son todos diferentes. Ahora más a la izquierda del punto es de color negro y así está más a la derecha del punto. Si tomamos los puntos en orden de izquierda a derecha, y deje $w_k$ el número de puntos blancos entre los primeros a $k$ $b_k$ el número de puntos negros entre los primeros a $k$ de los puntos, entonces $w_1 = 0$, $b_1 = 1$, $b_{n-1} = n-1$ y $w_{n-1} = n$. Así, la diferencia $b_k - w_{k}$$1$$-1$, y debe ser $0$ en el medio. Por lo tanto existe una separación de la línea, y se puede proceder por inducción.
Calvin Lin
Puntos
33086
Utilizar el principio extremal.
Considerar todos los $n!$ de las maneras en que podemos conectar los puntos blancos para los puntos negros. Debido a que este es finito, existe un camino que tiene un mínimo de longitud total. Me dicen que este conjunto cumple la condición. (Nota: Suponiendo que el problema enunciado es verdadero, Este conjunto es un candidato natural para satisfacer las condiciones.)
Prueba: Supongamos que no, entonces hay algún par de segmentos de líneas que se intersectan en un punto de $P$. Deje que los correspondientes puntos se $W_N, W_M$ $B_N, B_M$ donde $W_NB_N$ están conectados y $W_MB_M$ están conectados. Por la desigualdad de triángulo,
$$ W_NB_N + W_MB_M \\ = (W_NP + PB_N) + (W_M P + P B_M) \\ = W_NP + PB_M + W_M P + PB_N \\> W_N B_M + W_M B_N$$
La desigualdad es estricta, ya no hay tres puntos se encuentran en una línea. Esto contradice la suposición de que los segmentos de línea que tenía un mínimo de longitud total.
