Il faut exiger de chacun ce que chacun peut donner

marzo 5, 2010

J’ai le droit d’exiger l’obéissance
parce que mes ordres sont raisonn
ables.
Le Petit Prince, Chapitre X

El rey invita un día n parejas a un banquete para la noche siguiente alrededor de una mesa redonda de 2n+1 lugares . Para cada pareja el rey decidirá en la noche del banquete una cierta distancia d entre 1 y n a la que que los integrantes de esa pareja deberán sentarse (o sea, de modo que haya d-1 personas entre ellos) Probar que para todas las posibilidades que decida el rey hay siempre una distribución posible sí y sólo si 2n+1 es primo.

Sugerido por godelian, comunicación personal.

About these ads

6 comentarios hacia “Il faut exiger de chacun ce que chacun peut donner”

  1. Ivan S escribió

    Ahora si está completa la demostración que casi habíamos terminado con Daniel.

    Consideramos las parejas (x_i,y_i), con las distancias d_i asignadas por el rey.
    Veremos que es posible elegir los valores de los x_i de modo que los 2n números x_1, ...  x_n,  x_1+d_1,  ...  x_n+d_n resulten distintos dos a dos módulo p.

    Vamos a construir un polinomio en las n variables x_i que valga 0 módulo p si y solo si dos de esos 2n números resultan iguales.

    Luego usaremos Combinatorial Nullstellensatz para probar que el polinomio evaluado en {\mathbb{F}_p}^n no vale siempre 0 (usamos que \mathbb{F}_p es un cuerpo).

    Es natural elegir como polinomio al producto de todas las diferencias de los 2n números:

    \prod_{1\leq i<j\leq n}{(x_i-x_j)(x_i+d_i-x_j)(x_i-x_j-d_j)(x_i+d_i-x_j-d_j)}

    Por Nullstellensatz basta ver que hay un monomio de grado máximo, con coeficiente no nulo, tal que el grado en cada variable sea estrictamente menor a p=2n+1. Vamos a elegir el monomio con igual grado en todas las variables: {x_1}^{2n-2}{x_2}^{2n-2} ... {x_n}^{2n-2} (el grado total del polinomio es n(2n-2)).

    Solo necesitamos los monomios de grado máximo, asi que el polinomio se reduce a:
    \prod_{1\leq i<j\leq n}{(x_i-x_j)^4}

    Hallaremos indirectamente el coeficiente de este monomio:
    \prod_{1\leq i<j\leq n}{(x_i-x_j)^4}={x_1}^{2n-2}{x_2}^{2n-2} ... {x_n}^{2n-2} \prod_{i\neq j}{(1-\frac{x_i}{x_j})^2}
    Pero el término constante en \prod_{i\neq j}{(1-\frac{x_i}{x_j})^2} es \frac{(2n)!}{2^n} \equiv \pm 1 módulo p. Esto es un caso particular de la conjetura de Dyson.

    Terminó siendo una demostración teórica, y no dice demasiado sobre el problema.

    El paper del Combinatorial Nullstellensatz.
    Una demostración combinatoria (no la pude ver) de la conjetura de Dyson.

    • godelian escribió

      Excelente! De una forma u otra el problema está resuelto. Una prueba muy cortita de la conjetura de Dyson es la siguiente (Good, 1970):

      Sean x=(x_1,\dots,x_n), a=(a_1, \dots, a_n) y F(x;a)=\prod_{i\neq j}{(1-\frac{x_i}{x_j})^{a_j}}. Interpolando la función constante 1 en los x_i con el polinomio de Lagrange y evaluando en 0 obtenemos la identidad 1=\sum_j{\prod_{i\neq j}{(1-\frac{x_i}{x_j})^{-1}}}, que multiplicada por la anterior nos da F(x;a)=\sum_j{F(x;a_1,\dots,a_{j-1}, a_j-1, a_{j+1},\dots, a_n)}. Esto implica que si G(a) es el término constante de F(x;a) se cumple G(a)=G(a_1,\dots,a_{j-1}, a_j-1, a_{j+1},\dots, a_n) (1). Por otro lado, si a_j=0, x_j sólo aparece con exponente negativo en la expresión de F(x;a), por lo que necesariamente G(a) es en ese caso igual al término constante de F(x_1,\dots,x_{j-1}, x_{j+1},\dots, x_n;a_1,\dots,a_{j-1}, a_{j+1},\dots, a_n), es decir, G(a)=G(a_1,\dots,a_{j-1}, a_{j+1},\dots, a_n) si a_j=0 (2). Además, claramente se tiene G(0)=1 (3), con lo que (1), (2) y (3) determinan por recursión G(a) unívocamente. Pero la expresión \frac{(a_1+ \dots +a_n)!}{a_1! \dots a_n!} satisface (1), (2) y (3), con lo que necesariamente será igual a G(a).

    • domotorp escribió

      Hi, sorry to write in english but I don’t speak spanish, luckily I could still understand your proof. I do not know whether you are aware of it but a longer, Nullstellensatz-free proof appeared in AMS:
      http://www.ingentaconnect.com/content/maa/amm/2009/00000116/00000003/art00008

      I am working on something else and this is just the result I need, so I am citing the above mentioned paper and I would also like to cite this proof. Did it appear anywhere or should I just refer to this page? May I ask your full name? Please write to me at gmail, I have the same username.

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: