Apa nilai dari "game" ini (counter rebalancing)?

Pertanyaan ini diposting di CS.SE dua minggu lalu , tetapi tidak mendapatkan jawaban yang memuaskan.

Misalkan Anda memiliki permainan berikut:

Ada banyak sekali penghitung $\{c_1,c_2,\ldots\}$ , semuanya diinisialisasi ke 0.

Di setiap langkah, Anda memilih penghitung $c_i$ dan meningkatkan nilainya 1.

Sayangnya, setiap langkah $T$ , setiap penghitung yang memiliki nilai positif dikurangi sebesar 1.

Selain itu, nilai penghitung dibatasi oleh , jadi Anda tidak bisa menambah penghitung lebih jauh.$M$

1. Diberikan langkah sebanyak yang Anda suka, dapatkah banyak penghitung bernilai positif dapat Anda jangkau?

2. Berapa banyak penghitung bernilai positif yang dapat dijangkau setelah langkah ?$T\cdot M - 1$

---

Untuk pertanyaan (1), inilah aa penumpukan rinci untuk counter positif:$\approx T\log(M)$

1. Meskipun Anda memiliki penghitung kurang dari dengan nilai M : $T-1$$M$
   • Kenaikan indeks kontra minimal yang nilainya ketat kurang dari .$M$

(Ini harus menyatu karena jumlah penghitung terikat untuk meningkatkan setiap langkah )$T$

2. Biarkan .$r = T$

3. Sementara ( )$c_0>1$

   Sebuah. sementara ( )$c_0>c_r$

   • Kenaikan $c_r$

   b. $r = r + 1$

Sekarang untuk analisis: pengamatan pertama adalah bahwa jumlah penghitung positif adalah .$r$

Sekarang mari menjadi nilai maksimal c r yang telah dicapai. Untuk r = T kita mendapatkan M ( 1 - $m_r$$c_{r}$$r=T$. Untukr=T+1kita mendapatkanmr(1-$M(1-\frac{1}{T})$$r=T+1$, atau secara umum∀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}$$

Selanjutnya kita perhatikan bahwa ketika tercapai, c 0 = m r . Ini berarti loop akan berhenti ketika m r < 1 (memberi atau menerima integralitas dan strategi akhir permainan).$\forall m_r$$c_0=m_r$$m_r < 1$

Ini memberi kita (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$$

Apakah mungkin melakukan lebih baik? Adakah yang bisa membuktikan ini optimal?

Batas bawah untuk pertanyaan 2:

$TM-1$$(T-1)\log M$

$1$$TM-1$$TM-1$$Tk$$1 \le k < M$

$M- \lfloor N/T \rfloor$$N$$1$$1$$TM-1$

Strategi: Pada setiap langkah waktu, tambahkan penghitung paling kiri yang nilainya kurang dari batas atas.

$V/UL$$UL$

$T$$(T-1)/UL$$UL$

$1/UL$$UL/UL=1$$1/UL$$1$$UL$$T$$1$$(T-1)/UL$$T-1$$(T-1)/UL$

$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$

Berikut ini adalah batas atas untuk pertanyaan 2.

$TM$$T \log M$

$0$$(-TM+1)$

$0$

$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)$