Uno de los cuadrados por persona

Question

Hay n personas.

Cada persona dibuja k interiores disjuntos plazas.

Quiero dar a cada persona una sola plaza fuera de su elegido, k, de modo que el n plazas doy son interiores disjuntos.

Cuál es el mínimo de k (como una función de n) para que yo pueda hacer esto?

NOTAS:

• Para n=1, obviamente k=1.
• Para n=2, obviamente k debe ser mayor de 2, ya que con 2 plazas por persona, es fácil pensar en situaciones donde las plazas de la persona 1 cruzan ambas plazas o persona 2. Parece que k=3 es suficiente, pero yo no podía probar esta formalmente.
• Si no nos limitamos a las plazas, pero permitir general rectángulos, entonces, incluso para n=2, k no será lo suficientemente grande, como es posible que cada rectángulo de jugador 1 se cruza con cada otro rectángulo de jugador 2. Así, el sqauare limitación es importante.

EDIT: El problema tiene dos versiones: en una versión, las plazas son todos los ejes alineados. En la segunda versión, las plazas pueden ser rotados. Soluciones para cualquiera de estas versiones son bienvenidos.

EDIT: Aquí es posiblemente útil de la demanda, relevantes para el alineado al eje versión:

Reivindicación 1: Si dos alineado al eje plazas, a y B, se cruzan, entonces una de las 3 opciones siguientes:se

• Al menos 2 de las esquinas de Una están cubiertos por B, y B es tan grande o más grande que Una;
• Una esquina de Una está cubierto por B, y una esquina de B está cubierto por Una,
• Al menos 2 de las esquinas de B están cubiertos por Una, y es tan grande o más grande que la de B.

Por lo tanto, si se cruza con B, luego, a partir de las 8 esquinas de a y B, en la mayoría de las 6 esquinas quedan al descubierto.

Answer 1

Aquí está mi contra-ejemplo para el caso de $n=2$$k=3$. Siempre, naturalmente, que las plazas no necesitan ser del mismo tamaño. Usted tendrá que confiar en mí que todas las formas son cuadrados. Sin embargo, podemos ver que cada cuadrado se superpone a todos los 3 de los cuadrados de los otros colores.

Answer 2

He encontrado una cota superior para el alineado al eje de la versión. Se basa en la siguiente afirmación:

Reivindicación 2: una plaza puede intersectar en la mayoría de los 4 interiores disjuntos plazas que son tan grandes o más grandes que A.

• Prueba: Si se cruza con B y B es tan grande o más grande que Una, al menos una esquina de Una está cubierto por B (Ver Reivindicación 1, al final de la pregunta). Desde Una tiene 4 esquinas, no puede haber más de 4 plazas que son interiores disjuntos.

Ahora podemos dar a cada persona un cuadrado de su elección, utilizando el siguiente algoritmo:

1. Encontrar el más pequeño de la plaza de la $nk$ disponibilidad de plazas. Si hay más de uno - elija uno de forma arbitraria.
2. Dar el cuadrado más pequeño a su dueño, enviar el dueño de la casa, y eliminar todas las plazas de dicho propietario.
3. Eliminar todos los cuadrados que son intersectados por el cuadrado más pequeño. Por la Reivindicación 2, hay en la mayoría de los 4 cuadrados por persona. Por lo tanto, cada uno de los n-1 personas tiene al menos k-4 plazas. Volver al paso 1.

Si $k = 4n-3$, entonces el algoritmo, finalmente, terminar con 1 persona y 1 plaza.

Esto es sólo la mitad de una solución. Podemos hacer mejor que $4k-3$ en el eje alineado a la versión?

Answer 3

Esta respuesta: Plaza de colorear demuestra que, en el eje alineado a la versión, con $n=2$ de la gente, $k=3$ plazas son suficientes. Este es un apretado obligado.

Esta respuesta: http://cs.stackexchange.com/questions/12275/team-construction-in-tri-partite-graph demuestra que, con $n=3$ de la gente, $k=15$ cuadrados son siempre suficientes, pero esto obviamente no es un apretado vinculado (en una respuesta anterior me mostró que $k=9$ plazas son suficientes en este caso). Es posible que $k=8$ plazas son también bastante, pero esto depende de la solución de un SAT problema, y en cualquier caso, no es la que probablemente se encuentre firme.