OMI 2013 problema 6

Question

Deje $n\geq 3$ ser un número entero, y considerar la posibilidad de un círculo con $n+1$ equidistantes de los puntos marcados en ella. Considerar todos los etiquetados de estos puntos con los números de $0,1,\dots, n$ de manera tal que cada etiqueta se utiliza exactamente una vez; dos de los etiquetados son considerados a ser el mismo si uno puede ser obtenida de la otra por una rotación del círculo. Un etiquetado se llama bella si, para cualquiera de las cuatro etiquetas de $a<b<c<d$$a+d=b+c$, el acorde de unirse a los puntos etiquetados $a$ $d$ no intersecta con el acorde de unirse a los puntos etiquetados $b$$c$.

Deje $M$ el número de hermosa etiquetados y deje $N$ el número de pares ordenados $(x,y)$ de enteros positivos tal que $x+y\leq n$$\gcd(x,y)=1$. Demostrar que $M=N+1$.

Creo que este es un problema muy difícil para la OMI. Usted puede encontrar una discusión de aquí: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3154371

No veo una solución.

mi idea: podemos $$N(n)-N(n-1)=\varphi(n)$$ and This problem only prove $$M(n)-M(n-1)=N(n)-N(n-1)$$

Answer 1

Aquí está la solución , Pero esto no es oficial :

http://imomath.com/index.php?options=785

Suponga que $a$ $b$ son elementos distintos de a $\{1,2,\dots, n\}$ . Una hermosa etiquetado se llamará $(a,b)$ -etiquetado si $a$ $b$ son, respectivamente, la derecha y la izquierda vecino de $0$. Vamos a probar que $(a,b)$ -etiquetado existen si y sólo si $\mbox{gcd }(a,b)=1$$a+b> n $. Por otra parte, si $\mbox{gcd }(a,b)=1$ $a+b> n$ vamos a probar que el $(a,b)$ -etiquetado es único.

Observe que un $(a,b)$ -etiquetado no existe si $a+b\leq n$, desde los acordes $[0,a+b]$ $[a,b]$ se cruzarían en ese caso.

Suponga que $a+b> n$ . Suponga que $R$ es una $(a,b)$ -etiquetado. Por $c\in\{1,2,\dots, n\}$ nos deja definir la secuencia de $(z^c_k)_{k\geq 0}$, de la siguiente manera: $z^c_0=c$ , y para $k\geq 0$ : $$\begin{eqnarray*} z^c_{k+1}&=&\left\{\begin{array}{ll} z^c_k+a& \mbox{if } z^c_k\leq n-a,\newline z^c_k-b&\mbox{if }z^c_k>n-a\mbox{ and }z^c_k\geq b,\newline z^c_k+a-b&\mbox{otherwise.} \end{array}\right. \end{eqnarray*}$$

Observe que para cada $k\geq1$ al menos uno de los siguientes tres igualdades mantenga: $$\begin{eqnarray*} z^c_{k+1}+0&=&z^c_k+a\newline z^c_{k+1}+b&=&z^c_k+0\newline z^c_{k+1}+b&=&z^c_k+a. \end{eqnarray*}$$ Therefore, the ordering of the labels on the circle must be $b,0,a,z^c_k,z^c_{k+1} $. This means that the numbers $b , 0 , a , z^c_1 , \dots , z^c_m$ debe aparecer en ese orden en el círculo.

Si $\mbox{gcd }(a,b)> 1 $, entonces la secuencia de $(z^1_k)_{k\geq 0}$ no contienen el término $0 $. Esto contradice el hecho de que la secuencia tiene un número finito de elementos.

Hemos llegado a la conclusión de que si $(a,b)$ -etiquetado existe,$\mbox{gcd }(a,b)=1 $. Vamos ahora a demostrar que si $\mbox{gcd }(a,b)=1 $, $(a,b)$ - etiquetado debe ser único. Considerar la secuencia de $(z_k^0)_{k\geq 0} $. Observe que siempre tenemos $z_{k+1}\equiv z_k+a (\mod a+b )$ o $z_{k+1}\equiv z_k+2a (\mod a+b )$. Por lo tanto, la secuencia de $(z_k^0)_{k\geq 0}$ se obtiene cuando los números mayores que n se quitan de la secuencia de residuos de $a , 2a , \dots$ modulo $a+b$ . Por lo tanto $z^0_1 , \dots , z^0_n$ es una determinada únicamente permutación de $\{1,2,\dots, n\} $, lo que demuestra la singularidad de la etiqueta

Deje $L_n$ el número de pares de $(a,b)\in\{1,2,\dots, n\}^2$ tal que $\mbox{gcd }(a,b)=1$$a+b> n$. Tenemos que $M=L_n $. Queda por demostrar que $L_n=N_n+1 $ donde $N_n$ es el número de pares de $(a,b)\in\{1,2,\dots, n\}^2$ tal que $\mbox{gcd }(a,b)=1$$a+b\leq n $. Considere la matriz $(D_{i,j})_{i,j\geq 1}$ tal que $$D_{i,j}=\left\{\begin{array}{ll}1&\mbox{if gcd }(i,j)=1,\\ 0&\mbox{otherwise.}\end{array}\right.$$

Vamos a utilizar la inducción para demostrar que $L_n-N_n=1 $. La declaración sostiene claramente por $n=3 $. El número de $N_n$ representa el número en la matriz $D_{i,j}$ que se encuentran sobre y por encima de la diagonal $i+j=n $. El número de $L_n$ representa el número de unos en la matriz $D_{i,j}$ que se encuentran por debajo de la diagonal $i+j=n$ y para el que $i\leq n$$j\leq n$ . Tenemos que mostrar que $(L_{n+1}-N_{n+1})-(L_n-N_n)=0 $. Nos deja denotar por $G_{n+1}$ el número de unos en la $n+1$ -st columna que están en o por encima de la $n+1$ -pt de la vta. Deje $H_{n+1}$ el número de unos en la diagonal $i+j=n+1 $. Luego tenemos a $(L_{n+1}-N_{n+1})-(L_n-N_n)=2G_{n+1}-2H_{n+1}$ desde la nueva diferencia $L_{n+1}-N_{n+1}$ va a ganar todos los de la $n+1$ -st fila y $n+1$ -st columna, pero perder a todos los que están en la diagonal. Sigue a notar que $G_{n+1}=H_{n+1}=\varphi(n+1) $ donde $\varphi(x)$ es el número de números enteros más pequeños que $x$ y relativamente primer a $x$.

Answer 2

Resumen: En la parte 1, de manera explícita a construir los códigos con progresiones aritméticas modulo algo relativamente primos. En la parte 2, se demuestra que no hay muchas maneras de agregar $n$ a un código existente de la longitud de la $n$, por lo que no podemos obtener más de los códigos de la parte 1.

1. Hay, al menos, que muchos arreglos: Para cada una de las $a,b < n$ relativamente primos y $a+b \ge n$, se puede construir un código de circular de longitud $n$, donde 0 ha dejado al prójimo $a$ y vecino de la derecha $b$, por escrito, $bk \mod a + b$ $k=0, 1, \dots, a+b-1$ y, a continuación, la eliminación de los números de más de $n-1$.

   Es fácil ver que estos códigos de trabajo, porque la suma condición es equivalente a la suma condición modulo $a + b$ para estos pequeños números. Por lo tanto, sólo tenemos que entender que el acuerdo $0,1, \dots, N-1$ no tiene cruce de las diagonales de la igualdad de vértice suma, pero esto es evidente, porque se mueven en direcciones opuestas de ambos vértices para llegar a los otros vértices. (En particular, el patrón de las diagonales de la igualdad de sumas son siempre los mismos simple no cruzar la coincidencia de las particiones que el círculo en rayas.)

   También está claro que esto le da el número requerido por mirar el "nuevo" pares con $a+b=n$, lo que claramente da $\phi(n)$ porque $a$ determina la $b$.

2. No hay más acuerdos: Podemos demostrar por inducción que un acuerdo del tipo visto en la 1 de longitud $n$ tiene más de dos hijos (es decir, acuerdos que reducir a una determinada al $n$ es eliminado) cuando los vecinos de 0 suma a$n$, y tiene más de un niño cuando los vecinos no suma de a $n$.

   Esto implica que a partir de la longitud de la $n$ a la longitud de la $n+1$, el número de arreglos que se pueden cultivar en la mayoría de los $\phi(n)$.

   La prueba de la $a + b= n$ caso: Ya que la suma de los vecinos de 0 $n$, e $n+0=n$, tenemos que poner a $n$ el próximo a 0. Sólo hay dos posibilidades para hacerlo.

   La prueba de la $a+b > n$ caso: Ahora, no se nos permite poner a $n$ el próximo a 0 por $a+b =n + x$ y las dos diagonales se cruzarían el uno al otro. Legal ubicación de $n$ también le dará una disposición jurídica de la longitud de la $n-1$ si eliminamos 0 y restar 1 de cada número. La única manera de que no puede haber dos posibilidades es si $n$ se colocan en ambos lados de $1$ (que desempeña el papel de 0 en la menor disposición). Pero la diagonal que conecta 1 y $n-1$ de la fuerza de $n$ a estar en el mismo lado que el original 0, por lo que hay una posibilidad de que funciona.

   Tenga en cuenta que cualquier código sigue siendo hermoso cuando $n$ es tomada de distancia, por lo que todos los códigos surgir mediante la adición de $n$ a un código previo.

Por lo tanto hemos encontrado $\sum_{k=1}^{n-1} \phi(k)$ arreglos de longitud $n$) y hemos demostrado que el número de arreglos que crece en la mayoría de las $\phi(n)$ al pasar de longitud $n$$n+1$.