Considere la posibilidad de dos enteros positivos $x \ne y$ y deje $n = max\{\lfloor \log_2{x} \rfloor +1 ,\lfloor \log_2{y} \rfloor +1 \}$. Elegir un primer $p$ al azar de la primera $3n$ números primos. ¿Cuál es la probabilidad de que $x \bmod p = y \bmod p$?
Creo que es en la mayoría de las $1/3$. Mi razonamiento es que sólo hay $n$ de los números primos en la mayoría de los que $x \bmod p = y \bmod p$. ¿Tienen sentido y hay una auto-contenido de la prueba?
El problema con esta respuesta
Supuse que algo que no es cierto: que $\left(\prod_{k=1}^{d}p_k\right) + 1> d^d$. Esto es para $d>9$, estoy bastante seguro. Yo sólo supone para $d>8$, por lo que si usted se muda de los límites que me había propuesto $d\ge 8$ $d>8$y comprueba $d = 8$ a mano, usted encontrará que los resultados de mi trabajo sigue.
Respuesta
Para la construcción de $x,y$ de manera tal que la probabilidad es alta:
El resultado pair $x \equiv y \bmod{p}$ por cada primer (y sólo los números primos) que eligió a multiplicar. Desde el teorema del Resto Chino, es evidente que no podemos obtener la "suerte" con un $c$. Por lo $c$ es mejor ser $1$ ($0$desde $y$ debe ser positivo).
Deje $x > y$. Podemos seleccionar un conjunto de números primos $p_k$ $k \in K$ $x \equiv y \bmod p_k$ para los números primos. A continuación, la condición de $y \equiv x$ se cumple para el elegido de los números primos y no en otro. Por lo tanto, del Teorema del Resto Chino: $$x \equiv y \mod{\prod_{k\in K}p_k}$$
En realidad no importa el valor de $x \bmod{\prod_{k\in K}p_k}$; en la medida en $y = c$ $x = \left(\prod_{k\in K}p_k\right) + c$ $c$ lo suficientemente pequeño como para no afectar a $n$. Así que vamos a $c = 1$. Si $c$ fueron a afectar a $n$, sólo podría agregar más números primos en consideración y disminuir la probabilidad, por lo que no perdemos generalidad.
Entonces estamos buscando para el valor máximo de $|{K}|/3n$. $K$ es óptimo cuando contiene todos los números primos menores o iguales a un valor, ya que la adición de un gran primer a $K$ sólo sirve para elevar $n$ más que un pequeño prime. Por lo $K = \{1,2,3,...,d\}$ algunos $d$.
Por lo tanto, la probabilidad es $d/3n$.
El establecimiento $1/3$ unido
Sabemos que $x\geq2^d$ desde el más pequeño prime es $2$. Por lo $n\geq d$ a partir de su definición. A continuación,$d/3n \leq n/3n = 1/3$. Creo que el más fuerte obligado es $2/9$, y se produce cuando $x=7$$y=1$.
Menos límite superior: 2/9
Sabemos que $x = \left(\prod_{k=1}^{d}p_k\right) + 1> d^d$. Esto se desprende de los resultados aquí. A continuación, ya que $n=\lceil{\log_2 x}\rceil$, $$\frac{d}{3n} \leq \frac{d}{3d (\log_2d-1)}=\frac{1}{3(\log_2 d -1)}$$ para $d>2$, donde al menos uno es deshacerse de el techo de la función.
Así que ahora podemos construir un mínimo de límite superior. Observe que para $d\geq8$, la probabilidad es en la mayoría de las $1/6$. Sólo tenemos que comprobar $d \in \{1,2,3,4,5,6,7\}$ encontrar $d=2$ da un valor máximo de $2/9 > 1/6$. Por lo que el valor máximo es $2/9$$x = 7$$y=1$. Creo que el P. E. D. está en orden ahora.
Continuación: $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$
Si $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$, tenemos que cambiar nuestro método de elección de $x$$y$, ya que el $y \ne 1$.
Vamos a elegir a$d$, de modo que $K=\{1,2,\cdots,d\}$ representa los números primos $\{2,3,\cdots,p_d\}$ que $x \equiv y \bmod{p_k}$. El cambio es que tenemos que elegir el $x=c_1 \prod_{k \in K} p_k $$y=c_2 \prod_{k \in K} p_k $. Si $c1/c2 < 2$ tenemos una oportunidad que $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$. De lo contrario, es la garantía de que no se mantenga.
Al mismo tiempo, queremos minimizar $n$. Así que la opción más lógica es$c_1 = 3$$c_2 = 2$. Por supuesto que hay otras posibilidades. Volveremos a estas opciones más adelante, pero por ahora está hecho una suposición. Ahora, $x$ $y$ son elegidos y podemos proceder como antes.
Para los fines de encontrar el máximo de la probabilidad de que, suponemos $n$ a ser tan pequeño como sea posible con las opciones de $x$ y $y$: $n \ge \log_2 y = \log_2 {\left( 2 \prod_{k \in K} p_k \right)}$. Esto no es siempre un número entero, sino que trabaja para los límites.
Sabemos que $n > \log_2 {2d^d} = 1 + d \log_2 d$, por lo que
$$\frac{d}{3n} < \frac{d}{3(1+d\log_2 d)}$$
Para $d \ge 8$, tenemos que la probabilidad es menor que $8/75$ a partir de la ecuación anterior. Mediante la prueba de $d \in \{1,\cdots,7\}$ y tirar valores que no satisfacen $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$, nos encontramos con una probabilidad máxima de $5/39 > 8/75$ a $d=5$, $x=6931$, y $y=4621$ asumiendo $c_1 = 3$.
El aumento de $c_1$ sólo sirve para aumentar la $n$, por lo que el $8/75$ unido para $d \ge 8$ todavía funciona. A continuación, el aumento de $c_1$ sólo puede reducir la probabilidad o deja de ser el mismo.
El valor máximo al$c_1 = 3$$1/7$$d=3$. Tuvimos que tirar esto lejos desde $\lfloor \log_2 x \rfloor \ne \lfloor \log_2 y \rfloor$ al $c_1 = 3$. Si elegimos $c_1 = 4$$c_2 = 3$, podemos lograr el mismo $1/7$ mientras que la satisfacción de la condición. Esto es debido a que el pequeño incremento en el $c_1$ ocurre para no afectar a $n$, pero aporta $x$ $y$ entre dos consecutivos poderes de $2$. Ahora tenemos el resultado final:
La satisfacción de $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$, la probabilidad máxima es $1/7$, y se produce cuando $x = 120$$y=90$.
Añade incluso más tarde
Se me ha ocurrido que en lugar de cambiar a $c_2>0$, sólo podríamos agregar una adecuada grandes constante tanto $y$$x$. Voy a volver y comprobar que el resultado funciona aún en el caso en que una constante aditiva. Parece que uno puede hacer mejor con una modificación de la $2/9$ resultado: agregar $7$ tanto $x=7$ $y=1$ conseguir $1/6>1/7$.
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.
