پل‌های ارتباطی

سلطان در نقطه‌ی صفر محور اعداد قرار دارد. مریدان سلطان در نقاط مختلفی روی محور اعداد قرار گرفته‌اند، طوری که فاصله‌‌های افراد (شامل سلطان) دوبه‌دو متمایز است. همه می‌خواهند به سلطان راه ارتباطی داشته باشند؛ پس هر کس تصمیم می‌گیرد یک پل ارتباطی جهت‌دار (به خود سلطان یا به یکی از مریدان سلطان) ایجاد کند. هزینه‌ی ایجاد هر پل ارتباطی برابر با فاصله‌ی دو سر آن در محور اعداد است. به یک حالت از ایجاد پل‌های ارتباطی پایدار گوییم،‌ اگر:

فرض کنید یک حالت پایدار از پل‌های ارتباطی با $n$ مرید داریم. ثابت کنید مجموع هزینه‌ی پل‌ها کم‌تر یا مساوی $2 \times d \times lg (n+1)$ است که در آن $d$ فاصله‌ی سمت راست‌ترین فرد با سمت چپ‌ترین فرد است.