فرض کنید $w_n$,⋯,$w_1$ رشته‌هایی متمایز با حروف انگلیسی کوچک باشند که مجموع طول آن‌ها از $Q$ تجاوز نمی‌کند. $W$ را نیز یک رشته انگلیسی دلخواه با طول $Q$ در نظر بگیرید.
عدد $a_i$ (که $i$=۱,⋯,$n$ است) را برابر تعداد ظاهرشدن رشته $w_i$ در $W$ تعریف می‌کنیم. به عنوان مثال، اگر $w_1=ab$، $w_2=aca$٬ $w_3=bb$ و $W=abcabbb$ باشند، آنگاه $a_1 = 2$، $a_2 = 0$ و $a_3 = 2$ خواهد بود.
ثابت کنید:
$$min(a_1,a_2,⋯,a_n)\le \frac{2 \times Q \times \sqrt {Q}}n$$
پاسخ
تعریف:
طول رشته $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 $$