Perfora 2000 agujeros en 2000 polígonos con 1000 agujas.

Question

Tiene dos idéntica a la perfección trozos cuadrados de papel. El área de cada papel es de 1000 unidades.

Sobre cada hoja de papel, dibuja 1000 convexo, no superposición de polígonos con todos los polígonos que tenga la misma área (exactamente 1 unidad). Obviamente, los polígonos que abarcan tanto los papeles por completo y los bordes de papel también sirven como bordes de algunos polígonos). Los polígonos pueden tener diferentes formas y número de lados y el dibujo en el primer papel es completamente diferente de la de dibujo en el segundo papel.

Ahora poner el primer papel en la parte superior de la segunda y alinee los bordes del papel a la perfección. Demostrar que siempre es posible perforar un agujero en cada una de 2000 polígonos con 1000 agujas (cada aguja pasa a través de ambos documentos).

Lo he intentado?

Este problema surgió de mi hijo que le gusta torturar a su padre con difíciles problemas que traía de sus matemáticas de la escuela. Mi primer intento fue a robar a su inteligente análisis de libro mientras él estaba durmiendo y encontrar la página de la derecha en la sección de respuestas. Por desgracia, este problema no tenía solución, que básicamente significa que es demasiado simple (y yo soy demasiado estúpido o demasiado difícil.

Así que me decidí a leer algo de teoría y descubrió que había algunos bastante grandes lagunas en mi educación matemática. Este problema es definitivamente acerca de las funciones. Usted tiene un conjunto de 1000 polígonos en un lado y un conjunto de 1000 polígonos en el otro lado. Tengo que demostrar que no es un bijective función entre estos dos conjuntos. Las agujas son sólo las líneas que conectan los puntos. Sin embargo, todos mis intentos de construir una función terminó miserablemente. Supongo que tiene que ser inteligente teorema que puede ser aplicado a problemas como este, pero me gustaría tener que leer bastante grueso libro encontrarlo.

Gracias por la sugerencia.

Answer 1

La inteligente teorema que se puede aplicar a preguntas como esta es la Sala del teorema.

Construir un gráfico bipartito, con los vértices de un lado están los polígonos en la primera hoja de papel, y los vértices en el otro lado están los polígonos en la segunda hoja de papel. Dibujar un borde entre dos polígonos cuando se superponen.

Un perfecto maridaje en este gráfico es un uno-a-uno de emparejamiento de los polígonos de las dos hojas, para que cualquiera de los dos polígonos que están vinculados superponen en algún lugar. Si encontramos un perfecto maridaje, podemos perforar los agujeros: para cada par de polígonos en el perfecto maridaje, meter una aguja a través de alguna parte de su región de superposición.

Hall del teorema dice que un perfecto maridaje se garantiza que existe si, para cada conjunto de $S$ de los vértices de un lado, el conjunto de $N(S)$ de vértices adyacentes a algún vértice en $S$ satisface $|N(S)| \ge |S|$. En otras palabras, si usted toma cualquier $k$ polígonos en una hoja de papel, habrá al menos $k$ polígonos en la otra hoja de papel adjcent al menos a uno de los que has elegido.

Esto se deduce a partir de la observación de las áreas. Un individuo polígono de área $1$. Por lo que el $k$ polígonos que usted eligió en una hoja tiene área total $k$. En la otra hoja, la misma región necesita, al menos, $k$ polígonos para cubrir.

Answer 2

Es "evidente" que no podemos utilizar a menos de 1000 agujas, sólo para perforar un agujero en cada polígono en una sola hoja.

Por la encasillar principio, si utilizamos más de 1000 agujas, a continuación, algunos de los polígonos que debe tener más de un agujero en ellos.

Supongamos que la perforación 1000 agujeros en 1000 polígonos en la parte superior de la hoja de no conseguir una perfecta cobertura en la parte inferior de la hoja: no todos los 1000 polígonos recibir un agujero. Que requiere que uno o más polígonos para recibir dos agujeros. (Nuestro amigo, encasillar, de nuevo).

Es eso posible? Sí, sí que lo es. Para que eso suceda, todo lo que necesitamos es la situación en la que dos agujas (necesariamente) a través de diferentes polígonos en la parte superior de la hoja de pierce en el mismo polígono en la parte inferior de la hoja.

Sin embargo, es inevitable? No, no, no. Dos agujas de ir a través de diferentes polígonos nunca están obligados a asignar a la misma parte inferior del polígono. Para una situación inevitable, tendría que ser que algunos de los más bajos de la capa de polígono completamente cubiertas de dos (o más) de la capa superior de los polígonos. Este es descartado por la restricción de clave que todos los polígonos tienen la misma área. Por lo tanto, la situación es evitable; ningún par de agujas de tener que compartir el mismo inferior de la capa de polígono.