المپدیا

برای ساخت مثال، اعداد ۱ تا $n$ را به $⌊\sqrt{n}⌋$ بلوک از اعداد متوالی که هر یک شامل $⌊\sqrt{n}⌋$ عدد می‌شوند بخش بندی کنید. (از اعدادی که در هیچ بلوکی قرار نگرفته‌اند صرف نظر کنید.)

سعی کنید n دنباله، هر یک به طول $⌊\sqrt{n}⌋$، بسازید که هر کدام شامل دقیقا یک عدد از هر بلوک باشند.

ساختار این $n$ دنباله را به $\sqrt{n}$ روش مختلف ارائه دهید که هر یک از الگویی خاص پیروی کنند. این روش‌ها را در راهنمایی‌های بعد تحت عنوان نوع صفر تا نوع $n$ خطاب کرده‌ایم.

دنباله‌های نوع صفر: برای $i$امین دنباله‌ی این نوع، از هر بلوک عدد $i$ام آن‌ را انتخاب کنید.

دنباله‌های نوع اول: برای $i$ امین دنباله‌ی این نوع، از بلوک اول $i$ امین عضوش را بردارید. برای هر بلوک $j>۱$، اگر از بلوک $j-1$، $x$امین عدد آن بلوک انتخاب شده بود، به سراغ $x+1$ امین عدد بلوک $j$ بروید. (دقت کنید که اگر بلوکی $a$ عدد داشته باشد، منظور از عدد $a+1$ ام همان عدد اول بلوک است.)

دنباله‌های نوع $k$ ام: برای $i$ امین دنباله‌ی این نوع، از بلوک اول $i$ امین عضوش را بردارید. برای هر بلوک $j>۱$، اگر از بلوک $j-1$، $x$ امین عدد آن بلوک انتخاب شده بود، به سراغ $x+k$ امین عدد بلوک $j$ بروید. (دقت کنید که اگر بلوکی $a$ عدد داشته باشد، منظور از عدد $a+1$ ام همان عدد اول بلوک است.)

آیا ممکن است در دنباله‌های بالا زوجی بیابیم که دو بار در مجاورت هم ظاهر شده باشند؟

مجموع تعداد اعضای دنباله‌ها را بر اساس تعداد جفت‌های مجاور در تمام دنباله‌ها به دست آورید

اگر تعداد کل جفت های مجاور در یک $n$-تیر تپر، $x$ باشد، مجموع تعداد اعضای دنباله‌های آن برابر با $x + n$ خواهد بود (ثابت کنید)

مانند بخش قبل اعداد را به $\sqrt{n}$ بلوک از اعداد متوالی که هر یک شامل $\sqrt{n}$ عدد هستند تقسیم کنید.

برای هر دنباله اگر دو عدد مجاور از دو بلوک متفاوت راهنمایی قبل وجود داشت، این مجاورت را یک مجاورت خارجی و اگر دو عدد مجاور از یک بلوک بودند، مجاورت را یک مجاورت داخلی نامید. تعداد مجاورت‌های داخلی و خارجی را به طور مجزا بشمارید.

نشان دهید تعداد یال‌های خارجی از $O(n\sqrt{n})$ است.

چون در هر دنباله از هر دسته حداکثر یک یال خارجی خارج می شود پس در هر دنبال حداکثر $\sqrt{n}$ مجاورت خارجی وجود دارد و چون $n$ دنباله داریم حداکثر $n\sqrt{n}$ مجاورت خارجی وجود دارد

نشان دهید تعداد مجاورت‌های داخلی از $O(n\sqrt{n})$ است.

در مجموع $2\sqrt{n}$ مجاورت داخلی می‌توانیم داشته باشیم در کل دنباله‌ها که بر اساس راهنمایی ۲ ثابت می شود $f(n) \in O(n\sqrt{n})$