¿Cuál es el valor de este "juego" (reequilibrio de contadores)?

Esta pregunta se publicó en CS.SE hace dos semanas , pero no obtuvo una respuesta satisfactoria.

Supongamos que tienes el siguiente juego:

Hay infinitos contadores , todos inicializados en 0.$\{c_1,c_2,\ldots\}$

En cada paso, elige un contador y aumenta su valor en 1.$c_i$

Desafortunadamente, cada pasos, cada contador que tiene un valor positivo se reduce en 1.$T$

Además, los valores de los contadores están delimitados por , por lo que no puede incrementar un contador más.$M$

1. Dado tantos pasos como desee, ¿pueden alcanzar muchos contadores de valor positivo?

2. ¿Cuántos contadores valorados positivamente son accesibles después de pasos?$T\cdot M - 1$

---

Para la pregunta (1), aquí hay una acumulación detallada de contadores positivos:$\approx T\log(M)$

1. Si bien tiene menos de contadores en el valor : $T-1$$M$
   • Incrementar el contador de índice mínimo cuyo valor es estrictamente menor que .$M$

(Esto tiene que converger ya que la suma de los contadores está destinada a aumentar cada pasos).$T$

2. Dejar que .$r = T$

3. Mientras que ( )$c_0>1$

   a. while ( )$c_0>c_r$

   • Incremento$c_r$

   si. $r = r + 1$

Ahora para el análisis: la primera observación es que el número de contadores positivos es .$r$

Ahora dejemos que sea ​​el valor máximo que han alcanzado . Para obtenemos . Para obtenemos , o en generalc r r = T M ( 1 - $m_r$$c_{r}$$r=T$r=T+1mr(1-$M(1-\frac{1}{T})$$r=T+1$∀r≥T:mr=M(1-$m_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$

$$\forall r\geq T:m_r = M(1-\frac{1}{T})^{r-T+1}$$

Luego notamos que cuando se alcanza , . Esto significa que el ciclo se detendrá cuando (dar o tomar integralidad y estrategias de fin de juego).c 0 = m r m r < $\forall m_r$$c_0=m_r$$m_r < 1$

Esto nos da (1-

$$M(1-\frac{1}{T})^{r-T+1} < 1$$ (r-T+1)log(1- $$(1-\frac{1}{T})^{r-T+1} < M^{-1}$$ r-T+1<-log $$({r-T+1}) \log (1-\frac{1}{T}) < -\log M$$ r<-log $${r-T+1} < \frac{-\log M}{\log (1-\frac{1}{T})}$$ r<log $$r < \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$ $$r < \frac{\log M}{\sum_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 < T(\log M + 1) -1$$

¿Es posible hacerlo mejor? ¿Alguien puede probar que esto es óptimo?

Límite inferior para la pregunta 2:

Teorema: después pasos de , con la estrategia descrita a continuación, tendrá al menos contadores positivos.( T - 1 ) log $TM-1$$(T-1)\log M$

Notación: Definir tiempo de la etapa a ser el comienzo de los pasos, y para ser el final. Las disminuciones ocurren en el paso de tiempo , .T M - 1 T M - 1 T k 1 ≤ k < $1$$TM-1$$TM-1$$Tk$$1 \le k < M$

Defina que el límite superior sea , donde es el paso de tiempo actual. Este límite comienza en M y disminuye en uno cada vez que disminuyen los contadores, terminando en . Este límite se elige porque si alguna vez se colocan más contadores en una celda que el límite superior, se desperdiciarán, porque el contador tendrá un valor superior a en el paso .N 1 1 T M - $M- \lfloor N/T \rfloor$$N$$1$$1$$TM-1$

Estrategia: en cada paso de tiempo, incremente el contador más a la izquierda cuyo valor es menor que el límite superior.

Notación: defina la importancia de que un contador sea , donde V es su valor actual y es el límite superior actual.U $V/UL$$UL$

Lema: en cada grupo de pasos que terminan en una disminución, la suma de las importancia de los contadores aumenta al menos , donde es el límite superior actual.( T - 1 ) / U L U $T$$(T-1)/UL$$UL$

Prueba de lema: cada vez que se incrementa un contador, su importancia aumenta en . Cuando ocurre la disminución, todos los contadores menos uno están en su límite superior y tienen una importancia de . La importancia del contador restante se reduce en como máximo , porque su valor disminuye en y no aumenta. Por lo tanto, los incrementos de y la disminución de aumentan la importancia total en al menos . Además, en el último grupo de incrementos de , donde no se produce disminución, la suma de importancias aumenta en .U L / U L = 1 1 / U L 1 U L T 1 ( T - 1 ) / U L T - 1 ( T - 1 ) / U $1/UL$$UL/UL=1$$1/UL$$1$$UL$$T$$1$$(T-1)/UL$$T-1$$(T-1)/UL$

Prueba del teorema: en cada grupo de pasos que terminan en decremento, y en los pasos finales , la suma de las importancias aumenta al menos en . Por lo tanto, después de pasos, la suma de importancias será de al menos , que es al menos . Como en el paso de tiempo el límite superior es , debe haber contadores positivos en este momento.T - 1 ( T - 1 ) / U L T M - 1 ∑ m k = 1 ( T - 1 ) / k ( T - 1 ) log M T M - 1 1 ( T - 1 ) log $T$$T-1$$(T-1)/UL$$TM-1$$\sum_{k=1}^m(T-1)/k$$(T-1)\log M$$TM-1$$1$$(T-1)\log M$

Aquí hay un límite superior para la pregunta 2.

Teorema: Después de $TM$ pasos, puede tener como máximo $T \log M$ contadores positivos.

Notación: asignamos cada paso un número, que termina con el $0$ ^º paso, y a partir de la ^ésimo paso.$(-TM+1)$

Observación: en la estrategia óptima, si incrementa un contador, no lo deja volver a .$0$

Prueba: permítanos asignar un valor de a cada vez que incremente un contador en la última$1$$T$$\frac{1}{2}$$T$$\frac{1}{3}$$T$$-kT+1$$-(k-1)T$$\frac{1}{k}$

$1$

$T \sum_{i=1}^M \frac{1}{i} \approx T \log M$$1$

$-kT$$-(k-1)T$$k-1$$k$$\frac{1}{k}$

$\frac{1}{k}$$-kT+1$$-(k-1)T$$\frac{1}{M}$$-2MT$$-MT$$0$$0$$-2MT$$1$$-2MT$$1$$M$$T\log M + T$$T (\log M + 1)$