Que cubre diez puntos en una mesa con 10 monedas de igual tamaño: explicación de la prueba

Question

Nota: Esta pregunta ha sido publicado en StackOverflow. He movido de aquí, porque:

1. Tengo curiosidad por saber la respuesta
2. El OP no ha mostrado ningún interés en mover a sí mismo

---

En las Comunicaciones de la ACM, de agosto de 2008 "Perplejo" de la columna, Peter Winkler le hizo la siguiente pregunta:

En la mesa delante de nosotros son 10 puntos, y en nuestro bolsillo son 10 monedas de $1. Demostrar las monedas pueden ser colocados en el tabla (sin superposición de dos) en un manera que todos los puntos están cubiertos. Figura 2 muestra válida de la colocación de las monedas para este conjunto particular de puntos; son transparentes, por lo que podemos ver. Las tres monedas en el fondo no son es necesario.

En el siguiente problema, que presentó su prueba:

Teníamos que mostrar que cualquier 10 puntos en un la tabla puede ser cubierto por no superposición de monedas de $1, en un problema ideado por Naoki Inaba y envió a mí por su amigo, Hirokazu Iwasawa, tanto rompecabezas de expertos en Japón.

La clave es tener en cuenta que el embalaje de los discos dispuestos en un patrón de panal de abeja de la cubierta más del 90% del avión. Pero, ¿cómo sabemos que hacer? Un disco de radio uno encaja dentro de un hexágono regular compone de los seis triángulos equiláteros de la altitud. Desde cada triángulo tiene área sqrt(3)/3, el hexágono sí tiene área 2*sqrt(3); desde el hexágonos azulejo el avión en un panal de abejas patrón, los discos, cada uno con área de π, cubierta π /(2*sqrt(3)) ~ .9069 de la plano de la superficie.

De ello se sigue que si los discos son colocadas al azar en el avión, el probabilidad de que cualquier punto en particular está cubierto .9069. Por lo tanto, si nos aleatoriamente lugar un montón de monedas de $1 (prestado) en la tabla en un hexagonal el patrón, en promedio, 9.069 de nuestros 10 los puntos serán cubiertos, es decir, al menos parte del tiempo, todos los 10 será cubierto. (Necesitamos en la mayoría de sólo 10 monedas para dar la espalda al resto.)

¿Qué significa que los discos de la cubierta 90.69% del plano infinito? La manera más fácil de responder es decir, tal vez, que el porcentaje de cualquier gran plaza cubierta por los discos los enfoques de este valor como la plaza se expande. ¿Qué es "aleatorio" acerca de la la colocación de los discos? Una manera de creo que es para arreglar cualquier embalaje y ningún disco dentro de ella, a continuación, elegir un punto uniformemente al azar de la panal hexagonal que contiene el disco y mover el disco de manera que su centro está en el punto elegido.

Yo no lo entiendo. No la naturaleza probabilística de esta prueba simplemente significa que, en la mayoría de las configuraciones, todo 10 puntos pueden ser cubiertos. No podemos todavía vienen con una configuración en el que participaron 10 (o menos) puntos, donde uno de los puntos no pueden ser cubiertos?

Answer 1

Bueno! La anterior prueba demuestra que cualquier configuración de 10 puntos pueden ser cubiertos. Lo que tenemos aquí es un ejemplo del método de probabilidades, que usa la probabilidad, pero da una cierta (no probabilística) conclusión (un ejemplo de probabilista de las pruebas de no-probabilístico teoremas). Esta prueba también se utiliza de forma implícita la linealidad de espera, un hecho que parece contra-intuitivo, en algunos casos, hasta que te acostumbras a él.

Para aclarar la prueba: dado cualquier configuración de 10 puntos, revisión de la configuración, y considere la posibilidad de colocar a un panal de abejas patrón de discos al azar. Ahora, ¿cuál es el número esperado $X$ de los puntos cubiertos? Deje $X_i$ 1 punto si $i$, e $0$ lo contrario. Sabemos que $E[X] = E[X_1] + \dots + E[X_{10}]$, y también que $E[X_i] = \Pr(X_i = 1) \approx 0.9069$ como se explicó anteriormente, para todos los $i$. Por lo $E[X] = 9.069$. (Tenga en cuenta que hemos obtenido este resultado usando la linealidad de la expectativa, a pesar de que sería difícil argumentar acerca de los eventos de cubrir los puntos de ser independientes).

Ahora, ya que el promedio de las colocaciones de los discos (para la configuración fija de puntos!) es 9.069, no todas las ubicaciones pueden cubrir ≤9 puntos - al menos una colocación debe cubrir todos los 10 puntos.

Answer 2

El punto clave es que la 90.69% de probabilidad con respecto a "los discos de [ser] colocadas al azar en el avión", no los puntos se colocan al azar en el plano. Es decir, el conjunto de puntos en el plano es fijo, pero el panal de la disposición de los discos se coloca sobre ella en un desplazamiento aleatorio. Dado que la probabilidad de que dicha colocación cubre un punto dado es 0.9069, un azar de la colocación del panal se cubren, en promedio, 9.069 puntos (esto se deduce de la linealidad de la expectativa; I puede ampliar sobre esto si te gusta). Ahora la única forma aleatoria colocaciones puede cubrir 9.069 puntos en promedio es si algunas de estas colocaciones cubierta de 10 puntos -- si todas las colocaciones cubiertas 9 puntos o menos, el número promedio de puntos a cubrir en la mayoría de los 9. Por lo tanto, existe una colocación de panal de acuerdo que cubre 10 puntos (aunque esta prueba no le dice lo que es, o cómo encontrarlo).

Answer 3

Si usted lee con cuidado, esta prueba es para un arbitraria de la colocación de puntos. Así que, dado cualquier punto arreglo, si acabamos de colocar las monedas al azar (en el panal de acuerdo), entonces, en promedio, vamos a cubrir un poco más de 9 puntos. Pero ya que no podemos cubrir "parte" de un punto (en este problema), entonces eso significa que no existe un azar de la colocación de las monedas que cubre todos los 10 puntos. Así que no importa la configuración de puntos, sabemos que siempre hay una forma de cubrir los puntos con un máximo de 10 monedas :)