Puntos de la transformación del plano

Question

Hay n puntos situados arbitrariamente en el plano. Realicemos la siguiente transformación: cada punto "salta" al más cercano. ' A salta a B significa que el punto A las coordenadas después de la transformación son iguales a las coordenadas del punto B antes de la transformación. Si hay varios puntos ( B y C ) con la misma distancia mínima de A ( AB = AC ), puede saltar a cualquiera de ellos ( A a B o A a C ), por lo que puede elegir la opción favorable. Si algunos puntos tienen coordenadas iguales después de la transformación, se fusionan en un solo punto, lo que reduce el número de puntos restantes. Todos los saltos se producen simultáneamente (sólo hay dos estados del sistema). ¿Cuál es el número mínimo de puntos después de la transformación?

Algunos ejemplos:

1) 2 puntos A y B . Lo único que puede pasar es que A salta a B y B salta a A . Esencialmente, sólo intercambian lugares.

2) Tres puntos A , B , C en los vértices de un triángulo equilátero. Cada punto puede saltar a uno de los otros. Por ejemplo, A a B , B a C , C a A (intercambio a tres bandas) o A a B , B a A , C a A ( B y C se han fusionado, ahora sólo hay 2 puntos: B-C y A ) o etc. La segunda opción es mejor y, dado que buscamos el mínimo número de puntos restantes, para n=3 la respuesta es 2.

Estaba pensando en la solución con pequeños n . Parece obvio que siete puntos deben estar dispuestos en el centro y los vértices de un hexágono. 7 puntos por 2 es una buena proporción. Dos hexágonos con un vértice común producen (para 13 puntos) la mejor proporción (13 a 3), si 2 puntos centrales de los hexágonos adyacentes saltan al mismo lugar.

Estoy casi seguro de que hay una forma mejor de organizar los puntos en el plano, pero de momento me he quedado sin ideas. ¿Tienes alguna sugerencia?

Answer 1

Puede organizar hasta 10 puntos de esta manera:

Donde todos están en una cuadrícula hexagonal, de modo que los puntos negros se asignan a uno de los puntos púrpura y los puntos púrpura se asignan cada uno al otro.

Se pueden añadir otros tres puntos aumentando sólo uno el recuento final:

donde cada uno de los nuevos puntos va al mismo punto negro.

Estas dos formas pueden repetirse cualquier número de veces sin interferir entre sí, por lo que la respuesta al problema es:

$$\text{minimum}(n) = \begin{cases} \text{if }n > 10\land(n\text{ mod }10) \in \{1, 2, 3\}: & 2\left\lceil\frac{n}{10}\right\rceil-1\\ \text{else:} & 2\left\lceil\frac{n}{10}\right\rceil \end{cases}$$

Porque podemos tener $\left\lceil\frac{n}{10}\right\rceil$ grupos de diez, cada uno de los cuales consume diez puntos y resulta en dos, y podemos añadir hasta tres puntos adicionales a uno de esos grupos, añadiendo sólo un punto extra.

La prueba de que esta es la forma óptima se basa en el hecho de que como máximo seis puntos pueden mapearse a uno solo, y cualquier punto que se mapee a un punto "completo" sólo puede tener como máximo tres nuevos puntos mapeados a él.