تکرار رشته‌ها

تعریف: طول رشته $w_i$ برابر است با $len_{w_i}$ .
حرف $i$‌‌‌ام رشته $W$ نیز برابر است با $W_i$.

لم $1$: اگر مجموع $n$ عدد طبیعی متفاوت برابر با $S$ باشد، به دلیل متفاوت بودن اعداد، در حالتی $S$ مینیمم است که این مجموعه اعداد، همان اعداد $1,2,...,n$ باشند و در این حالت نیز $S$ برابر $\frac { n \times (n+1) } 2$ می‌شود. پس: $\frac { n \times (n+1) } 2 \le S$.

اکنون عدد $b_i$ را اینگونه تعریف می‌کنیم. $b_i$ برابر است با تعداد دفعات ظاهر شدن رشته‌های $w_1$,..,$w_n$ در رشته $W$ به صورتی که اولین حرف از رشته ظاهر شده، حرف $i$ام رشته $W$ باشد. یعنی $b_i$ برابر است با تعداد $j$ هایی که: $\overline{ { W_i{W_{i+1} }...W_{ {len_{w_j}} -1 } } } = w_j$ و نیز $B_i$ برابر با مجموعه این رشته‌ها (رشته‌هایی که در $b_i$ شمردیم) است . (به وضوح $|B_i| = b_i$)

حال می‎توانیم بگوییم $\sum{a_i} = \sum{b_i}$، زیرا با هر بار ظاهر شدن یکی از رشته‌ها در $W$، یکی از $a_i$ ها و یکی از $b_i$ ها هر کدام یک واحد افزایش میابند.

اکنون رشته‌های $B_i$ را در نظر بگیرید. طول هیچ دوتایی از این رشته‌ها نمی‎توانند با هم برابر باشند، زیرا اگر طول دو تا از این رشته‌ها، مانند $w_j$ و $w_k$ با هم برابر باشند (${len_{w_j}} = {len_{w_k}}$)، آنگاه $w_j = \overline{ { {W_i}{W_{i+1}}...{W_{ {len_{w_j}} -1 } } } } = w_k$ و این با فرض متفاوت بودن رشته‌های $‎w_n$,⋯,$w_1‎$ تناقض دارد. پس طول رشته‌های موجود در $B_i$ ها اعدادی طبیعی و متفاوت‌اند و نیز طبق فرض سوال می‌دانیم، مجموع این طول‌ها کمتر از $Q$ است. پس اگر این مجموع برابر $S$ باشد، طبق لم $1$ و فرض سوال داریم: (تعداد اعضای $B_i$ = $b_i$)

$$\frac { (b_i) \times (b_i+1) } 2 \le S \le Q$$
$$\Rightarrow { b_i \times (b_i +1) } \le {2 \times Q }$$
$$\Rightarrow { b_i \times b_i } \le { 2 \times Q }$$
$$\Rightarrow b_i \le { \sqrt {2 \times Q } } \le {2 \times {\sqrt Q } }$$

حال همه $b_i$‌ ها کوچکتر از ${2 \times {\sqrt Q } }$ هستند. در نتیجه داریم:
$$\sum{b_i} \le {Q \times 2 \times {\sqrt Q} }$$ (چون تعداد $i$ های ممکن $Q$ تا است).

و نیز داشتیم که $\Sigma{a_i} = \Sigma{b_i}$. در نتیجه:
$$\sum{a_i} \le {Q \times 2 \times {\sqrt Q} }$$
$$\Rightarrow min(a_1‎,‎a_2‎,‎⋯‎,‎a_n) \times n \le \sum {a_i} \le {Q \times 2 \times {\sqrt Q} }$$
$$\Rightarrow min(a_1‎,‎a_2‎,‎⋯‎,‎a_n) \le \frac {Q \times 2 \times {\sqrt Q}}n$$