4 votos

Una pregunta combinatoria

Veamos en un $p\times p$ junta ($(\mathbb{F}_p)^2$ plano) con una pieza única en la esquina izquierda $(0,0)$. Esta es una pieza especial que ha $3$ movimientos legales:

  1. Mover un paso hasta $\pmod p$
  2. Mover un paso a la derecha $\pmod p$
  3. Movimiento x pasos a la derecha y y pasos $\pmod p$ donde $1\leq x,y \leq p-1$

Estoy tratando de demostrar que la pieza puede llegar a cualquier plaza en la tabla (excepto volver a la original $(0,0)$ plaza) en la mayoría de los $p-1$ movimientos legales. Tengo una prueba de al $x=y=1$ e al $x+y=0$. Usted puede ayudar con el resto de los casos?

Gracias

5voto

Esto no es siempre posible. Para un contraejemplo vamos $p=7$, $(x,y)=(6,2)$ y pick $(u,v)=(5,3)$ como la plaza que se desea llegar. Intente como usted puede, usted necesitará por lo menos $8$ se mueve (para una prueba de ver el argumento de abajo).

Sin embargo, puedo demostrar que esto siempre se puede hacer, si queremos hacer el extra suposición de que $x+y\not\equiv 1\pmod p$.


Las diferentes formas de usar movimientos de los 3 tipos, decir $a_i$ se mueve si el tipo de $i$, $i=1,2,3$, cantidad de estudiar el conjunto de soluciones de $(a_1,a_2,a_3)\in\Bbb{F}_p^3$ del sistema subdeterminado $$ a_1(0,1)+a_2(1,0)+a_3(x,y)=(u,v). \qquad(*) $$ Se ve fácilmente que $a_3\in\Bbb{F}_p$ puede ser elegido cualquier forma que desee, y determina la solución única. Así que las soluciones de $(*)$ son parametrizadas por $t\in\Bbb{F}_p$ $$ (a_1,a_2,a_3)=(v-ty,u-tx,t).\qquad(**) $$ Vamos a denotar por $|a|$, $a\in\Bbb{F}_p$, el "valor entero" de un elemento $a$, lo $|a|$ será un número entero en el rango de $[0,p-1]$. El número de movimientos requeridos por la solución de $(**)$ es así $$ S(t)=|v-ty|+|u-tx|+|t|. $$

Un promedio argumento de la siguiente manera. Vamos a empezar por calcular la suma de todas estas posibilidades $$ \sum_{t=0}^{p-1}S(t)=\sum_{t=0}^{p-1}|v-ty|+\sum_{t=0}^{p-1}|u-tx|+\sum_{t=0}^{p-1}|t|. $$ Porque se supone que ni $x$ ni $y$$\equiv 0\pmod p$, los tres sumas de dinero en la r.h.s. tiene todos los números de $0,1,\ldots,p-1$ términos en cierto orden. Por ejemplo, $|v-ty|\equiv v-ty\pmod p$, así que de a pares no congruentes opciones para $t$ de plomo para no congruentes, y por lo tanto distintos, los valores de $|v-ty|$.

Por lo tanto, podemos concluir que $$ \sum_{t=0}^{p-1}S(t)=\frac32p(p-1). $$ Vemos esto como diciendo que, con el parámetro $t$ variable, el promedio de número de movimientos que usted necesita en diferentes soluciones de $(*)$$3(p-1)/2$.

Echemos un vistazo a la distribución de la mudanza de los recuentos $S(t)$. Nos seee que $$ S(t)=|v-ty|+|u-tx|+|t|\equiv (u-tx)+(v-t)+t=u+v-t(x+y-1)\pmod p. $$ Entonces, si asumimos que el $x+y\not\equiv1\pmod p$, se deduce que el $S(t)\not\equiv S(t')$ siempre $t\not\equiv t'$. En particular, los números de $S(t), t=0,1,\ldots,p-1$, son todos distintos, en este caso. Podemos deducir que al menos uno de ellos es $<p$. De lo contrario, su suma sería de al menos $p+(p+1)+\cdots+(2p-1)=p(3p-1)/2>3p(p-1)/2$ contradecir el anterior resultado acerca de su promedio.

Por desgracia, cuando se $x+y\equiv1\pmod p$ cosas puede ir hacia el Sur. En el ejemplo anterior caso $p=7$, $(x,y)=(6,2)$, $(u,v)=(5,3)$ se ve fácilmente que $S(t)=8$ para todos, pero una sola opción de $t$ con el valor excepcional de ser $S(6)=|4|+|5|+|6|=15$. El promedio es todavía como se predijo, porque $(6\cdot8+1\cdot15)/7=9=3(7-1)/2$. Observar que, de nuevo, de acuerdo con los cálculos anteriores, aquí todos los movimientos de los recuentos $S(t)$ son congruentes a $u+v=8$ modulo $7$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X