======تکرار رشته‌ها======	
				
فرض کنید $‎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 $$

</پاسخ>

  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]