Dibuja un cuadrado de 5x5. En 16 de 25 cuadrados dibuja diagonales de tal manera que no se toquen los extremos diagonales. ¿Cómo puedo hacer esto?
Esta pregunta ya tiene respuestas:
- ¿Cómo resolver una cuadrícula 5x5 con 16 diagonales? (5 respuestas )
Respuestas
¿Demasiados anuncios?
Publicación de una copia en CW de la imagen (vinculada a) dada como una solución a la pregunta duplicada . Por si acaso el enlace se pudre: - /
mrseaman
Puntos
161
He aquí un argumento de por qué $16$ es óptimo. Deje $r_i$ el número de diagonales trazadas en la $i$-ésima fila de cuadrados. (Así que en la supuesta solución óptima $r_1 = r_3 = r_5 = 4$$r_2 = r_4 = 2$.) A continuación,$0 \le r_i \le 5$, y debido a que cada diagonal en la fila $i$ elimina $1$ de la $6$ superior de los vértices de la diagonal en la fila $i + 1$,$r_{i+1} \le 6 - r_i$. Deje $d_{i+1} = 6 - r_i - r_{i+1}$ ser el error de esta desigualdad, de manera que $d_{i+1} \ge 0$$r_{i+1} = 6 - r_i - d_{i+1}$. (Por lo que el $d_i$ todos los $0$ en la reivindicada en la solución óptima.) El número total de diagonales es entonces:
$$ r_1 + r_2 + r_3 + r_4 + r_5= r_1 + 12 - d_3 - d_5 \le 17 $$
y sólo podemos tener igualdad de si $r_1 = 5$$d_3 = d_5 = 0$. Sin embargo, si $r_1 = 5$ y $r_2 = 1$, $r_3$ no puede ser $5$ debido a la diagonal en la fila $2$ no puede tener su baja en el límite de la matriz de cuadrados. Por lo $d_3 > 0$ y la solución óptima tiene de hecho en la mayoría de las $16$ diagonales como se reivindica.
Tebbe
Puntos
271
John Hughes
Puntos
27780
He aquí un mal (por desgracia) la prueba de que no se puede hacer.
Hay 36 vértices de la cuadrícula.
Supongamos que usted tiene una solución.
16 diagonales que se va a utilizar hasta 32 de estos vértices. Así que exactamente cuatro vértices que no están en uso.
También hay 50 posibles diagonales. Cada uno (interno) vértice que va no utilizada corresponde a la mayoría de los cuatro bordes que no se puede utilizar. [N. B., añadió después de los comentarios: en este punto el resto de la argumentación es errónea, por que hay otras formas de tecnología de punta para ser utilizado-como otros bordes con uno de sus dos extremos. D'oh!] Externo vértice corresponde a 2 o 1 no utilizado de las diagonales. De modo que el mayor número de los diagonales en cualquier acuerdo que deja sólo cuatro no utilizados vértices es de 16. Que significa un arreglo de usa, al menos, 34 de las diagonales. Que es una contradicción.
