Los Chips no forma de rectángulo en la junta

Question

Dado que es un $n\times n$ junta con $n\geq 3$. Ponemos un chip en algunas células, por lo que no las cuatro fichas en forma de rectángulo con lados paralelos a los lados de la junta. Cuántas fichas podemos, en la mayoría de los?

Podemos colocar $2n$ fichas en las posiciones de $(i,i)$ $1\leq i\leq n$, $(i,i+1)$ para $1\leq i\leq n-1$, e $(n,1)$. Es posible mejorar?

Answer 1

$$\begin{array}{cccc}X&X&X&-\\ -&X&-&X\\ X&-&-&X\\ -&-&X&X\end{array}$$

El $X$'s son las monedas. Este es un contraejemplo a $N = 4$.

---

En general, considere la posibilidad de $S_k \subset \{1, \ldots, N\}$ consta de las columnas que son llenados en la fila $k$.

El requisito es, precisamente, $|S_k \cap S_\ell| \leq 1$ todos los $k \neq \ell$.

---

Un asintótica límite inferior de la finitos planos proyectivos:

Colecciones de subconjuntos de a $\{1,\ldots, n\}$ de manera tal que cualquier pareja se cruza en la mayoría de los uno son bastante interesantes.

Un caso especial de estos se dan por proyectiva finita planos, donde el conjunto es el conjunto de puntos y los subconjuntos son las líneas. Este es un requisito más estricto, por supuesto. Puede haber una solución limpia para el máximo, en general, en su caso.

Finitos planos proyectivos darnos $n^2+n+1$, $n^2+n+1$ líneas, y $n+1$ puntos por línea.

Esto le da un $N\times N$ matriz, con $N = n^2+n+1$, $(n+1)N \approx N\sqrt{N}$ monedas.

Así que este es un asintótica límite inferior (al menos restringida a $N$ de este formulario donde $n$ es una fuente primaria de energía).

---

Un asintótica límite superior:

Deje $s_k = |S_k|$. Entonces no podemos repetir un par,

$\sum_k {s_k \choose 2} \leq {N \choose 2}$.

Por lo tanto $\sum_k s_k(s_k-1) \leq N(N-1)$.

Vamos a maximizar $\sum_k s_k$$\sum_k s_k(s_k-1) \leq M$.

Deje $\mathbf{s}$ ser el vector $(s_1,s_2,\ldots,s_N)$. Entonces

Tenemos $\mathbf{s} \cdot (\mathbf{s} - \mathbf{1}) \leq M$ y queremos enlazado $\mathbf{s}\cdot \mathbf{1}$.

Tenemos $\mathbf{1} \cdot \mathbf{s} \leq |\mathbf{s}||\mathbf{1}| = \sqrt{N} \mathbf{s}$

Así, obtenemos $\mathbf{1} \cdot \mathbf{s} \leq \sqrt{N}\sqrt{M + \mathbf{1}\cdot \mathbf{s}}$.

Así que tenemos $A \leq \sqrt{N} \sqrt{M+A}$. El cuadrado obtenemos $A^2 \leq N (M+A)$. Así que tenemos $(A - N)A \leq NM$. Por lo tanto $A-N \leq \sqrt{NM}$. Por lo tanto $A \leq \sqrt{NM}+N$.

Por lo tanto $\sum_k s_k \leq \sqrt{N} \sqrt{N(N-1)} + N \approx N \sqrt{N}$.

---

Algunos de atracciones:

Los niños de la tarjeta de juego Irregular! dispone de 55 cartas, cada una con 8 animales (y 57 diferentes animales en total). Todas las cartas son diferentes, y cualquier par de cartas tiene exactamente un par de animales en común. Esto es $\mathbb{PF}_7$ con dos líneas que faltan (probablemente para la impresión de motivos).

También hay Spot Jr! con 31 tarjetas y 6 animales por tarjeta (y el 31 de diferentes animales en total). Esto es $\mathbb{PF}_5$.

Answer 2

Sí, es posible mejorar en $2n$.

Considere la posibilidad de $n=6$ y colocar las fichas en $$ \begin{array}{cccccc} (1,1) & & & & (1,5) & \\ (2,1) & (2,2) & & & & (2,6) \\ (3,1) & & (3,3) & & & \\ & (4,2) & (4,3) & (4,4) & & & \\ & (5,2)& & & (5,5) & \\ & & (6,3) & & & (6,6) \end{array} $$ La Simple inspección muestra que no hay cuatro de estos en forma de rectángulo; la inspección es ayudado por el hecho de que cualquier rectángulo debe incluir dos puntos en la misma fila. Os dejo como ejercicio para el lector la prueba de que esta configuración tiene más de 12 fichas.

En cuanto a la cuestión del número máximo oof fichas colocable de esta manera, yo no estaría sorprendido al enterarse de que el problema es NP duro.

Answer 3

Yo siempre se puede llegar a $3n-3$. Escribir nuestra disposición de fichas de la siguiente manera : el $n$ columnas se escriben como $S_1,\cdots,S_n$ donde $S_i \subseteq \{1,\cdots,n\}$ y la condición de que no tenemos rectángulos de fichas es equivalente a $|S_i \cap S_j| \le 1$, como en aes de respuesta ; tener un rectángulo significa que hay dos columnas en las que el rectángulo que aparece y aparece un rectángulo en estas dos columnas si y sólo si estos dos columnas ambos tienen fichas en algún par de filas, lo que explica el criterio.

Dividir en los casos de $n$ a y $n$ impar. En el caso de $n$ incluso deja $$ S_1 = \{ 1,\cdots,n/2 \}, \quad S_2 = \{n/2,\cdots,n\} $$ y en el caso de $n$ impar, tomamos $$ S_1 = \{1,\cdots,(n+1)/2\}, \quad S_2 = \{ (n+1)/2,\cdots, n \}. $$ Tenemos $S_1 \cap S_2 =\{(n+1)/2\}$ o $\{n/2\}$ dependiendo de si $n$ o impar.

Ahora vamos a recoger el resto de columnas con sólo dos elementos, asegurando así que su intersección contiene más de un elemento es equivalente a la selección diferentes. Pero una manera fácil de asegurarse de que $S_1 \cap S_k$ $S_2 \cap S_k$ tiene más de un elemento es la construcción de $S_k$ mediante la selección de un elemento en $S_1 \backslash S_2$ y un elemento en $S_2 \backslash S_1$. Esto significa que hay

• $n$ incluso, $|S_1| = n/2$, $|S_2| = n/2+1$, así que hay $(n/2-1)(n/2) = \frac{n^2}4 - \frac n2 \ge n-2$ maneras de hacer esto desde $(n/2-1)(n/2)-(n-2) = \frac{(n-3)^2 - 1}4 \ge 0$ $n \ge 4$ (esto encaja en nuestras suposiciones en $n$),
• $n$ impar, $|S_1| = |S_2| = \frac{n+1}2$, por lo que hay $\frac{(n-1)^2}4 \ge n-2$ maneras de hacer esto desde $\frac{(n-1)^2}4 -(n-2) = \frac{(n-3)^2}4 \ge 0$.

Contar el número de fichas que se dio cuenta de que en ambos casos, obtenemos $3n-3$.

Sin embargo, esto es lo triste es que lejos de ser generalmente óptimo ; incluso no es correcto para $n=6$, donde tengo este arreglo de $16 > 15 = 3 \times 6 - 3$ fichas : $$ \begin{matrix} - & - & \bullet & \bullet & - & - \\ - & \bullet & \bullet & - & \bullet & - \\ - & \bullet & - & \bullet & - & \bullet \\ \bullet & \bullet & - & - & - & - \\ \bullet & - & - & \bullet & \bullet & - \\ \bullet & - & \bullet & - & - & \bullet \\ \end{de la matriz} $$ He obtenido esta tratando de llenar las tres primeras columnas y, a continuación, "de relleno en la última de las columnas", como en el caso de que me restringido mi atención a las dos primeras columnas y consiguió $3n-3$. Esto me dio algo de espacio extra, pero la combinatoria involucrados en el "llenado en las últimas columnas de" no mirar más simple, por lo que la solución no muy buen aspecto ; sin embargo, se sugiere que la solución debe ser un poco más que lineal en $n$. La solución asintótica $n \sqrt n$ de aes no suena mal.

Espero que ayude,