torta cuadrada con pasas de uva

Question

Alice hornea un cuadrado de bizcocho, con $n$ uvas pasas (= puntos).

Bob cortes $p$ trozos cuadrados. Son alineado al eje, interiores disjuntos, y cada pieza debe contener al menos $2$ pasas.

Tenga en cuenta que una pasa de uva puede ser compartido por dos piezas (si es que en su límite), o incluso cuatro piezas (si es que en su esquina).

Bob intenta maximizar el número de piezas que $p$, y Alice intenta minimizar $p$ por un sofisticado de la colocación de las pasas.

Para un determinado $$ n (número de pasas de uva), ¿cómo debe Alice lugar la pasas como para minimizar $p$, y cuál es el mínimo?

Estos son algunos de los casos:

• Para n=0, 1, obviamente, p=0.
• Para n=2, 3, 4, Alice puede hacer que el p=1, colocando la pasas en las esquinas de la torta, ya que la única pieza cuadrada que puede contener 2 pasas de uva es la torta entera.
• Para n=5, el mínimo de p es de 2: hay al menos una cuarta parte de la torta que contiene 2 pasas de uva. Bob puede cortar una pieza que contiene estos 2 pasas de uva en su límite, y es totalmente contenida dentro de esa parte de la torta. Ahora hay suficiente espacio para otra plaza, que contiene uno de estos pasas y otro de pasas de uva.

Cuál es el mínimo de $p$ para un determinado $n$?

-

Algunas ideas:

• Dadas dos pasas de uva, la longitud mínima de un cuadrado que contiene a ambas es el tablero de ajedrez de la distancia entre ellos.
• Por lo tanto, parece que Alice, la mejor estrategia es maximizar el tablero de ajedrez distancias, y así que la fuerza de Bob el uso de grandes plazas. Esto tiene sentido, pero no puedo demostrarlo.
• Si n es un número cuadrado ($n = k^2$), entonces Alice puede colocar las pasas en un k por k cuadrícula, de tal manera que el más pequeño tablero de ajedrez de la distancia entre las pasas de uva es de $1/(k-1)$. En este caso, Bob puede reducir en más de $(k-1)^2$ plazas. Pero es esto realmente Alice es la mejor estrategia?
• Bob siempre se puede hacer mejor con piezas de pasas sólo en sus límites (Él nunca tiene que cortar una pieza que tiene una pasa de uva en el interior). PRUEBA: Para cualquiera de los dos pasas de uva, hay un cuadrado que contiene tanto de ellos en el límite. Si la pieza contiene dos pasas de uva en el interior, o uno en el interior y uno en el límite, Bob puede reducir esa pieza para conseguir una plaza que tiene estos dos pasas de uva en el límite. Esta plaza será totalmente contenida en el original de la plaza, y por lo tanto no afectará a las otras piezas.

Answer 1

Edición (31 de Mayo de 2013): La prueba de la cota superior de a continuación es un error (ver comentarios), el límite inferior debe todavía se mantienen.

Deje que $p(n)$ de ser la óptima valor de $p$ si ambos jugadores juegan de manera óptima. Voy a demostrar que $p(n)\leq (n+2)/3$ y se esbozo una prueba de $p(n)\geq C$ n de una absoluta constante $C>0$.

Alice puede alcanzar $p(n)\leq (n+2)/3$. La prueba es por inducción sobre $n$. Identificar el pastel con $[0,1]^2$ en el plano Cartesiano. Lugar de tres pasas en $(0,1)$, $(1,0)$, y $(1,1)$. A continuación, tomar una colocación óptima de $n-3$ pasas, un factor de escala de $1/3 de dólares para hacer una colocación en $[0,1/3]^2$. El resultado es un conjunto de $n$ pasas. Ahora, si $p\geq 2$, entonces en la mayoría de los una de las tres de la esquina pasas pertenecen a una plaza. Obtenemos así que $p(n)<2$ o $p(n)\leq 1+p(n-3)$. En cualquier caso, la inducción paso es completa.

A continuación se explica Bob estrategia. Suponga que en lugar de $[0,1]^2$ cuadrado de todo el juego ocurre en el plano infinito de $\mathbb{R}^2$. Así, las plazas están autorizados a extender más allá de la torta de la frontera. Antes de cortar los cuadrados, que es una operación irreversible, Bob debe mentalmente elegir qué plazas para cortar, como sigue. Él comienza sin plazas. Para cada pasas $r$ hay un único cuadrado más pequeño $S(r)$ que se centra en $r$ y contiene, al menos, otro de pasas de uva. (Es de suponer que $n\geq 2$ para $S(r)$ a estar bien definidos). En cada paso de Bob hace lo siguiente:

1) Si el cuadrado $S(r)$ no se cruza con ninguna de las plazas en su lista mental, entonces Bob agregar $S(r)$ a la lista.

2) Si el cuadrado $S(r)$ reúne algunos de los actuales plazas, entonces $S(r)$ se añade sólo si es menor que el de las plazas que se cruza. En ese caso, la plaza se cruza se quitan de la lista.

El proceso termina porque si ordenamos los cuadrados de tamaños, a continuación, la secuencia resultante se convierte en lexicográficamente más pequeña en cada paso.

Ahora bien, si el punto $r'$ no está en la lista resultante de plazas porque $S(r'))$ cruza algunos de los más pequeños (o igual) $S(r)$, entonces decimos que el punto $r'$ echa la culpa a el punto $r$. Yo reclamo un punto de $r$ se puede culpar a la mayoría de los $8$ otros puntos. Lamentablemente, no veo una limpieza a prueba, aunque es bastante obvio desde el diseño de las imágenes. Suponiendo que la demanda, se sigue que $n$ es en la mayoría de los $9$ veces el número de plazas (cada cuadrado contiene el centro, y en la mayoría de los otros ocho puntos de la culpa).

En el anterior he asumido que el juego es jugado en $\mathbb{R}^2$. Yo no creo que debería ser una de las principales dificultades, pero de nuevo no se ve de una manera limpia para lidiar con ella.

Answer 2

Yo creo que he encontrado un límite superior:

$$P(n) \leq techo({n \over 2}) - 1$$

PRUEBA (después de la discusión con Boris Bukh): supongamos que el número de pasas es $n=2k+2$ ($k \geq 1$), y supongamos que el pastel es el cuadrado $[1,3^k]x[1,3^k]$.

Alice puede colocar las pasas en las siguientes posiciones:

$(1,1) (1,3) (1,9) ... (1,3^k)$

$(3,1) (9,1) ... (3^k,1) (3^k,3^k)$

¿Cuál es el mejor Bob puede hacer?

• En primer lugar, considerar la parte superior derecha de pasas $(3^k,3^k)$. El tablero de ajedrez de la distancia entre este y pasas cualquier otro de pasas de uva es de $3^k-1$, que es la longitud de la torta entera. Por lo tanto, la única pieza que puede utilizar que pasa está todo el pastel. Por lo tanto, Bob tuvo mejor descartar esta pasas y no lo utilizan.
• Ahora, el resto de las pasas de uva son: Uno inferior izquierda de pasas $(1,1)$; k lado izquierdo pasas de dólares(1,3^i)$, y de k parte inferior del lado pasas $(3^j,1)$. Cualquier pieza que utiliza una parte inferior del lado de pasas y un lado izquierdo de pasas necesariamente contiene la esquina inferior izquierda de dólares(1,1)$, por lo tanto, Bob puede tener a lo sumo un tal pieza. Todas las piezas deben utilizar cualquiera de las dos parte inferior del lado pasas, o dos del lado izquierdo pasas.
• Supongamos que Bob cortes de la izquierda de la pieza que contiene dos adyacentes pasas de dólares(1,3^i)$ y $(1,3*3^i)$, con $1 \leq i \leq k-1$. El lado de longitud de esta pieza es de al menos $2*3^i$. Por lo tanto, contiene el punto $(2*3^i,2*3^i)$. Lo mismo vale para cualquier parte inferior del lado de la pieza que contiene los dos adyacentes pasas $(3^i,1)$ y $(3*3^i,1)$. Por lo tanto, Bob sólo puede tener uno de los dos trozos, y por lo tanto él puede tener a lo sumo k-1 piezas que contienen parte inferior del lado izquierdo o del lado de las piezas (por $1 \leq i \leq k-1$).
• En total, Bob puede tener en la mayoría de los k piezas cuadradas, demostrando el límite superior $p \leq techo(n/2)-1$.

ADEMÁS (2013-06-12): Supongamos que Bob está permitido para cortar, no sólo de plazas, pero también R-equilibrado rectángulos, que se define como rectángulos cuya relación anchura/altura de entre R y 1/R, $R \geq 1$ (tenga en cuenta que un cuadrado es 1-equilibrado).

Alice puede usar la anterior construcción, con dos pequeñas modificaciones:

• En lugar de 3, el uso de un factor de dólares(2+R)$ .
• Soltar la parte superior derecha de pasas de uva (ahora el número total de pasas de uva es de $2k+1$).

Bob todavía puede tener en la mayoría de los k piezas cuadradas, y el límite superior es de $p \leq suelo(n/2)$.

Por lo tanto, permitiendo r-equilibrado rectángulos en lugar de cuadrados, para cualquier finito de r, no mejora de Bob situación muy mucho - le permite obtener cero o una pieza adicional.

Answer 3

Demasiado largo para un comentario, así que estoy publicando aquí.

puedo decir que la estrategia que creo que es la mejor para Alice para colocar las pasas de uva:

en primer lugar, poner 4 pasas de uva en las cuatro esquinas, y llame a cualquiera de los dos diaginal pasas a y B;

a continuación,poner 2 pasas de uva C y D en el interior de la plaza, o en el límite,cada pasas a o B pueden formar un cuadrado con una de las dos pasas de uva que está más cerca a él,y tomar el segmento CD como la diagonal, se puede formar un rectángulo dentro de la plaza;

a continuación, poner otros dos pasas de uva E y F en el interior del rectángulo o en el límite, cada pasas de C y D se puede formar un cuadrado con E o F, y tomar EF como la diagonal, se puede formar un pequeño rectángulo en el interior del rectángulo,continuar en este camino, hasta que Alice se utiliza todos los n pasas.

Answer 4

Yo creo que he encontrado un límite inferior.

Aquí es un algoritmo recursivo Bob puede usar:

Si $n \leq 1$, entonces ninguna de sus piezas son posibles; Si $2 \leq n \leq 4$, entonces una sola pieza es posible; y si $5 \leq n \leq 8$, entonces al menos 2 piezas son posibles.

Si $a 8 $ \leq$ n, Divida el pastel (sin cortarlo) a 4 idéntica plaza trimestres. Contar el número de pasas de uva en cada trimestre. Proceder de acuerdo al número de trimestres con al menos 2 pasas de uva (debe haber al menos uno de esos trimestre):

• Caso 1: No es exactamente 1 trimestre con al menos 2 pasas de uva. En este caso, los otros 3 cuartos contienen en la mayoría de los 3 pasas de uva. Reducir el ex trimestre hasta que el resto contiene exactamente 4 pasas de uva. El resto pueden ser cubiertos por 3 (posiblemente se superponen) cuadrados, y contiene 4 pasas de uva, por lo que al menos uno de los 3 cubrir plazas contiene 2 pasas de uva, y Bob puede cortar una sola pieza fuera de él. El shrinked trimestre contiene al menos $n-3$ pasas. Cortar en forma recursiva.
• Los casos 2, 3, 4: Hay 2, 3 o 4 trimestres con al menos 2 pasas de uva. Corte cada uno de ellos de forma recursiva, e ignorar el resto de los cuartos.

Deje que $P(n)$ ser el número de piezas de Bob puede conseguir con este algoritmo:

• $n \leq 1$: $P(n)=0$.
• $2 \leq n \leq 4$: $P(n) \geq 1$.
• $5 \leq n \leq 8$: $P(n) \geq 2$.
• $8 \leq n$: $P(n)$ es al menos el mínimo de los siguientes casos:
  • Caso 1: $1 + P(n-3)$
  • Caso 2: $min_{i,j}P(i) + P(j)$ tal que $i+j+2 = n$, y $i,j \geq 2$.
  • Caso 3: $min_{i,j,k}P(i) + P(j) + P(k)$ tal que $i+j+k+1 = n$, y $i,j,k \geq 2$.
  • Caso 4: $min_{i,j,k,l}P(i) + P(j) + P(k) + P(l)$ tal que $i+j+k+l = n$, y $i,j,k,l \geq 2$.

Estas relaciones de recurrencia sugerencia de que $P(n)$ es lineal. Para encontrar un límite inferior en $P(n)$, vamos a asumir que hay algunos $a$ y $b$ tales que:

$$P(n) \geq {(n+b) \más de un}$$

y demostrarlo mediante la inducción. Durante la inducción de la prueba, vamos a encontrar lo que $a$ y $b$ debe estar en orden para que la prueba sea correcta.

En primer lugar, la relación debe ser cierto para todos los $2 \leq n \leq 8$. Por lo tanto:

• Por $2 \leq n \leq 4$, debe ser cierto que: $1 \geq (n+b)/$. Por lo tanto: $a \geq b+4$.
• Por $5 \leq n \leq 8$, debe ser cierto que: $2 \geq n/a + b$. Por lo tanto: $2a \geq b+8$.

• Por $8 \leq$ n, tenemos que revisar todos los 4 casos:

  • Caso 1: $1 + P(n-3) \geq 1 + (n+b-3)/a = (n+b+a-3)/a \geq (n+b)/$. Para que esto se sostenga, debemos tener: $a \geq 3$.
  • Caso 2: $P(i) + P(j) \geq (i+j+2b)/a = (n-2+2b)/a \geq (n+b)/$. Para que esto se sostenga, debemos tener: $b \geq 2$.
  • Caso 3: $P(i) + P(j) + P(k) \geq (i+j+k+3b)/a = (n-1+3b)/a \geq (n+b)/$. Para que esto se sostenga, debemos tener $2b \geq 1$ (este trivialmente se sigue de la anterior requisito).
  • Caso 4: $P(i) + P(j) + P(k) + P(l) \geq (n+4b)/a > (n+b)/$. Para que esto se sostenga, debemos tener $3b \geq 0$ (este trivialmente se sigue de la anterior requisito).

La asignación de $a=6$ y $b=2$ cumple todos los requisitos. Así tenemos el siguiente límite inferior:

$$ P(n) \geq {(n+2) \más de 6} \ \ \ \ \ [n \geq 2]$$

Todavía hay una gran brecha entre el límite inferior de aproximadamente $n/6$, para el límite superior de aproximadamente $n/2$.

Ejercicios para los lectores:

• Demostrar una mejor cota inferior, de aproximadamente $n/a 4$, para el caso de que Bob es permitido para cortar, no sólo plazas, pero también 2-equilibrado rectángulos (es decir, rectángulos cuya relación anchura/altura de entre 1/2 y 2). Tenga en cuenta que en este caso, el límite superior es de aproximadamente $n/2$.
• Supongamos que Bob encuentra una manera de cortar 3 cuadrados en un pastel con 7 uvas pasas (esto es a la par con el límite superior). Basado en esta suposición, demostrar una mejor cota inferior, de aproximadamente $n/a 4$, $n \geq 5$. Sugerencia: usted tiene que dividir algunos de los casos a la sub-casos, donde algunos de los rectángulos contienen al menos 2 a menos de 5 uvas pasas.