Permutar al azar $\{1,\cdots,100\}$. ¿Cuál es la probabilidad de que ninguno de lo $S_k$ ' s por $\sigma(1)+\cdots+\sigma(k)$ es divisible por $3$?

Question

Después al azar permuting los números de $1$ a $100$, ¿cuál es la la probabilidad de que ninguno de los $S_k$'s definida por $S_k =\sigma(1)+\cdots+\sigma(k)$ es divisible por $3$?

Creo que tengo una solución. Aquí está mi propuesta de solución:

Considere la posibilidad de que todos los números de $1$ a $100$ modulo $3$. Tenemos $33$ ceros, $34$ queridos y $33$ dos. Ahora vamos a ver que las permutaciones son elegibles:

Primero de todo, no importa en donde los números divisibles por $3$ se colocan después de la permutación porque son cero modulo $3$. Yo reclamo, sólo existe un posible patrón:

$$1 \hspace{5px} \underbrace{1\hspace{5px} 2\hspace{5px} 1\hspace{5px} 2\hspace{5px} 1\hspace{5px} 2\hspace{5px} 1\hspace{5px} \cdots \hspace{5px} 1 \hspace{5px}2}_{\text{33 times}}$$

el resto de los ceros se pueden poner en cualquier lugar. ¿Por qué es este el único patrón? Bueno, aviso que después de haber escogido $\sigma(1)$, no hay dos consecutivos sigmas puede ser $1$ modulo $3$. Porque si $S_k\equiv x \pmod{3}$, a continuación, $S_{k+1} \equiv x+1 \pmod{3}$ e $S_{k+2} \equiv x+2 \pmod{3}$. Uno de estos tres deben ser divisible por $3$. Por lo tanto, no consecutivas $1$'s puede estar en la lista después de la primera entrada.

El mismo argumento se aplica a cualquiera de los dos consecutivos sigmas que son iguales a $2$ modulo $3$. Así que, después de haber escogido $\sigma(1)$, el resto de la lista debe ser llenado con la alternancia de $1$'s y $2$'s $0$'s colocados arbitrariamente. Así, tenemos dos opciones:

$$\text{Pattern I: } \hspace{5px} 1 \hspace{5px}1\hspace{5px} 2\hspace{5px} 1\hspace{5px} 2\hspace{5px} 1\hspace{5px} 2\hspace{5px} 1\hspace{5px} \cdots$$ $$\text{Pattern II: } \hspace{5px} 2 \hspace{5px}2\hspace{5px} 1\hspace{5px} 2\hspace{5px} 1\hspace{5px} 2\hspace{5px} 1\hspace{5px} 2\hspace{5px} \cdots$$

El segundo patrón es imposible. Debido a que el número de $1$'s y $2$'s son limitados y no podemos encajar $34$ queridos y $33$ dos en dos con el segundo patrón.

Por lo tanto, sólo necesitamos contar el número de maneras en las que podemos colocar ceros en el único patrón (patrón I) encontrar la probabilidad. La respuesta final es por lo tanto igual a:

$$\frac{{67+33-1}\choose{33}}{{100 \choose 33} \times {67 \choose 34}}=\frac{{99}\choose{33}}{{100 \choose 33} \times {67 \choose 34}} \approx 4.7\times 10^{-20}$$

Así, la respuesta es muy pequeño y la probabilidad es casi $0$.

Answer 1

El razonamiento parece correcto.

Pero el recuento de formas parece equivocado. El denominador de <span class="math-container">$3^{100}$</span> no tiene sentido para mí. Más bien debería ser el multinomial <span class="math-container">$ \binom{100}{33, 34,33}$</span>. Además, el numerador debe ser <span class="math-container">$\binom{99}{66}=\binom{99}{33}$</span>

Answer 2

Su análisis es correcto. Así me puedo concentrar en el recuento.

Obviamente una secuencia no puede comenzar con un número que es igual a cero mod 3. Esto significa que los ceros pueden ser colocados en algún lugar en el restante 99 lugares. Esto le da a ${99}\choose{33}$ posibilidades. La secuencia de ceros son 33 los diferentes valores. Por lo tanto, hay $33!$ diferentes secuencias.

El patrón de los unos y los doses ha sido demostrado ser $1, 1, 2, 1, 2, 1, ...$ Hay 34 que pueden ser ordenados en $34!$ maneras. Y para los dos tenemos $33!$ diferentes secuencias.

Esto significa que tenemos $33! * 34! * 33! * {{99}\choose{33}}$ secuencias válidas. Son en total $100!$ secuencias posibles. La probabilidad de golpear a uno de los deseados es así

$$ \frac{33! * 34! * 33! * {{99}\seleccione{33}}}{100!} $$

Wolfram me dice que esta es $\frac{1}{21233613041224311000} \approx 4.71 \times 10^{-20}$