Problemas de probabilidad que implica la teoría de los números

Question

Deje $k \in Z^+$. Asumir enteros 1, 2, 3, . . . , 3k+ 1 están escritas al azar. Calcular la probabilidad de que en ningún momento durante este proceso, la suma de los números enteros es un entero positivo divisible por 3?

Intento: estoy tratando de acercarse a este por encontrar el complemento de lo que se pregunta que es el número de veces que la suma de los números enteros es divisible por 3. El espacio muestral creo que es $\prod_{i = 0}^{3k+1}(3(i)+1)!$ desde que se creo el número de árboles que pueden generar al hacer este proceso.

Creo que mi espacio muestral está apagado. La manera correcta es averiguar cuántas secuencias podemos tener en algún momento me donde $1 \leq i \leq 3k+1$ durante el proceso. Esto es:

$(3k+1) +(3K+1)(3k) + (3k+1)(3k)(3k-1)+ ... + (3k+1)!$

También tengo la sensación de que esto se hace mediante el uso de los estados. Hay sólo tres estados donde la suma puede ser en cualquier momento, y estos son: 0mod3, 1mod3 y 2mod3. Tenemos que encontrar todas las posibles maneras en que podemos alcanzar el estado 0mod3 de alguna manera.

Answer 1

Para el problema donde repitition no está permitido, es decir, estamos mirando las permutaciones de los números de $1,2,3,\dots,3k+1$

Mirando los números modulo3 por ahora, cada arreglo será de la forma $$1.1.2.1.2.1.2.1.\dots2.$$

donde aquellos números que son múltiplos de tres que va a ser colocado en algún lugar donde los puntos son (no el primer número de la secuencia)

El motivo debe ser claro: si la primera no múltiplo de tres es $1$mod3, la próxima no múltiplo de tres no puede ser un $2$, de lo contrario vamos a tener un sub-suma que es un múltiplo de tres. Por lo tanto, el segundo debe ser un $1$. Del mismo modo, el siguiente debe ser una $2$mod3 para evitar un sub-suma un múltiplo de tres de nuevo, y así sucesivamente. Alternativamente, si el primero no múltiplo de tres es $2$mod3, vamos a tener que empezar a $221212121\dots$, pero esto requeriría una o dos números más que se $2mod3$ de los números que se $1$mod3, una imposibilidad. Por último, se puede iniciar con un múltiplo de tres, por razones obvias.

Hay $\binom{3k}{k-1}$ formas de insertar el $k$ copias de $0$ en la secuencia anterior mediante el uso de estrellas y barras , ya que hay $k$ 0 a colocar en $2k+1$ plazas disponibles.

Ahora, en sustitución de la $1$'s con un arreglo de todos los números a los que se $1$mod3, la sustitución de todos los de la $2$'s, con una disposición de los números que se $2$mod3, y lo mismo para las $0$'s, tenemos una secuencia de los números de $1,2,3,\dots,3k+1$ la satisfacción de sus condiciones.

Hay $(k+1)!,k!,$ $k!$ maneras de hacer esto, respectivamente.

Hay, a continuación, $(k+1)!k!k!\binom{3k}{k-1}$ formas de organizar los números que satisfacen sus condiciones deseadas. Esto está fuera de la $(3k+1)!$ igualmente probable arreglos, haciendo que la probabilidad:

$$\frac{(k+1)!k!k!\binom{3k}{k-1}}{(3k+1)!}$$

Answer 2

JMoravitz da buenos comentarios de arriba que conducen a una gran solución para la permutación de problemas. La repetición de problemas es también muy interesante, y me dan algunos detalles sobre esto:

Supongamos que cada paso $t \in \{1, 2, 3, ...\}$ nos independientemente escoger un número uniforme en el $\{1, ..., M\}$ donde $M \geq 3$ es un entero positivo. ¿Cuál es la probabilidad de que la suma de proceso nunca es un múltiplo de 3 $t \in \{1, ..., T\}$?

Caso 1: Si $M$ es un múltiplo de 3, la respuesta es $(2/3)^T$ ya que son igualmente propensos a escoger un número que es 0, 1, o 2 (mod 3).

Caso 2: Si $M$ no es un múltiplo de 3, entonces podemos definir el $p_i$, ya que la probabilidad de escoger un número que es $i$ (mod 3). Por lo que podemos encontrar fácilmente $p_0, p_1, p_2$. A continuación, podemos modelar el problema como un 3-estado de la cadena de Markov con estados $0, 1, 2$ actual mod-3 suma.