پلهای ارتباطی
سلطان در نقطهی صفر محور اعداد قرار دارد. مریدان سلطان در نقاط مختلفی روی محور اعداد قرار گرفتهاند، طوری که فاصلههای افراد (شامل سلطان) دوبهدو متمایز است. همه میخواهند به سلطان راه ارتباطی داشته باشند؛ پس هر کس تصمیم میگیرد یک پل ارتباطی جهتدار (به خود سلطان یا بهیکی از مریدان سلطان) ایجاد کند. هزینهی ایجاد هر پل ارتباطی برابر با فاصلهی دو سر آن در محور اعداد است. بهیک حالت از ایجاد پلهای ارتباطی پایدار گوییم، اگر:
- هر کس به سلطان مسیری جهتدار (با استفاده از پل خودش و پلهای دیگران) داشته باشد.
- به ازای هر مرید مانند ایلیچ، اگر دیگر مریدها مسیر ارتباطی خود را تغییر ندهند، ایلیچ نتواند پل ارتباطی خود را جور دیگری با هزینهی کمتر بسازد، طوری که باز هم همه به سلطان مسیری جهتدار داشته باشند.
فرض کنید یک حالت پایدار از پلهای ارتباطی با $n$ مرید داریم. ثابت کنید مجموع هزینهی پلها کمتر یا مساوی $2 \times d \times lg (n+1)$ است که در آن $d$ فاصلهی سمت راستترین فرد با سمت چپترین فرد است.