Pregunta: Encontrar la probabilidad de que un azar par de celosía puntos de las esquinas opuestas de una plaza en un $n\times n$ entero de celosía.
Nota: Por una plaza en red, me refiero a un cuadrado cuyos vértices son todos celosía puntos.
Motivación: tengo un desordenado prueba de que la solución es $\frac13$. La prueba se basa en calcular el número total de plazas en cada una de las $n\times n$ celosía, pero quiero saber si hay alguna limpio argumento que evita que el método. No hay razón para pensar que no podría ser ya que el resultado es independiente de $n$.
Antecedentes: el Primer aviso de que en un $n\times n$ entero entramado, hay más plazas que el obvio alineado al eje de plazas, por ejemplo, la siguiente:
Con algunos cálculos, uno puede encontrar que el número total de plazas en esta cuadrícula es $$\sum\limits_{k=1}^nk^2(n-k)=\frac{(n-1)n^2(n+1)}{12}$$ Me di cuenta de que esto también puede ser escrito como $\dfrac{n^2 \choose 2}{6}$, lo que me llevó a la combinatoria de interpretación de la recolección de las esquinas de un cuadrado. Una vez que sabemos que el número de plazas es $\frac{1}{6}$-º del número de pares de puntos, la supuesta solución de $\frac13$ es una consecuencia inmediata (como cada cuadrado tiene dos pares de lados opuestos). Sin embargo, he buscado la semana pasada y no pudo descubrir una prueba sin depender de contar todas las plazas.
Fuente: pensé que de esta pregunta, mientras que tratando de escribir los problemas para una competencia de matemáticas.
Respuestas
¿Demasiados anuncios?
Por $k$, $1\leq k\leq n-1$, una alineado al eje cuadrado de lado de longitud $n-k$ puede ser colocado en $k^2$ maneras, y cada plaza hosts $n-k$ plazas con vértices en su borde. El número total $Q_n$ admisible plazas, por tanto, está dada por $$Q_n=\sum_{k=1}^{n-1}k^2(n-k)=\ldots={n^2(n^2-1)\over12}\ .$$ Creo que la forma exacta de que el resultado final es una coincidencia, cf. la fórmula para $\sum_{k=1}^n k^3$. – Trabajar con las decisiones individuales se hace más difícil por el hecho siguiente: Los puntos elegidos tienen que cumplir con una condición de la paridad de antes de que usted incluso puede pensar en una posible plaza. Si $n$ es impar la probabilidad de que esta paridad condición mantiene el es $\ne{1\over2}$.
Por cierto: Decir "aleatorio par de celosía puntos" desde dos puntos elegidos de forma independiente pueden coincidir.
Yo creo que lo que esquema se parece bastante mejor (y elegante) solución. Como usted ha señalado, una vez que tenemos el recuento de los cuadrados dentro de la red, la reivindicación es una consecuencia inmediata, contando en dos formas en que el número de tripletas $(x,y,Q)$ donde $[x,y]$ es un par de puntos y $Q$ es un cuadrado, y $xy$ es una diagonal de $Q$.
La fórmula $6(\# Q) ={n^2\choose 2}$ también tiene una simple prueba: contamos por separado el número de plazas que se han $(p,q)$ como su borde inferior, con $p\ge 1$, $q\ge 0$. Ya que esto se inscribe en un cuadrado de lado de longitud $p+q$ con lados paralelos a los ejes (y esta es la más pequeña plaza), tenemos $(n-p-q)^2$ dichas plazas. Esto le da $$ \# Q = \sum_{p\ge 1, q\ge 0} (n-p-q)^2 = \sum_{j=1}^n\sum_{p+q=j} (n-j)^2 = \sum_{j=1}^n j(n-j)^2 = \sum_{k=0}^{n-1} k^2(n-k) , $$ como se reivindica.
Mientras que esta respuesta probablemente sólo reproduce lo que ya se hizo a sí mismo, creo que no es demasiado realista esperar una solución alternativa que es mucho más sencillo todavía.
Tal vez tengo una alternativa.
En primer lugar, se observa que, dado un $n \times n$ celosía, hay $n- 1 $ formas para dibujar un cuadrado dentro de ella. Cada cuadrado contribuye dos diagonales. Así, el número de diagonales $p(n)$ $n \times n$ entramado puede ser calculada de forma recursiva de la siguiente manera: $$ p(n) = p(n-1) + \sum_{k=1}^{n-1} 2k (2n – 2k -1) $$ Esto se obtiene mediante la consideración de un $n-1 \times n-1$ celosía, y la adición de puntos a, digamos, la parte inferior y el lado derecho.
Simplemente se cuenta, en la parte superior de todas las diagonales de la inicial $n-1 \times n-1$ celosía (primer término), las diagonales contenida en las plazas de compartir al menos un lado con las líneas dadas por el agregado de puntos en la parte inferior y el lado derecho. Más de conteo es evitado por contar sólo las diagonales relacionados con las líneas de tocar el perímetro de cada uno, de modo definido de la plaza, que se realiza con la fórmula informó al principio. Dado un $n \times n$ celosía, el número total de líneas de $c(n)$ une dos puntos está dado por $$ c(n) = \frac{n^2 (n^2-1)}{2}$$ Para el tipo de individuos calificados hacinamiento de este sitio (a la que yo no pertenezco), una prueba de que $$ \frac {p(n)}{c(n)} = 1/3$$ que bien podría ser una brisa, utilizando el tipo de binomio de las identidades de la OP sugerido.
