سلام.
من فکر می کنم گزینه یک درست باشه !
درصورتی درخت دودویی پر باشه آلفا برابر ۱ . و درصورتی درخت غیر پر باشه آلفا کوچکتر از یک خواهد بود.
گزینه ۳ تحت هیچ شرایطی درست نیست.

ممکنه توضیح بفرمایید چرا ۲ ؟

(۲۱ خرداد ۱۳۹۲ ۰۶:۲۶ ب.ظ)Pakniat نوشته شده توسط:  در یک درخت دودویی T ، برای هر برگ x واقع در عمق d تابع $\omega (x)= 2^{-d}$ را تعریف می کنیم . کدام یک از گزینه های زیر برابر است با $\alpha = \sum_{leaf x}\omega (x)^{}$ است ؟
$1) \alpha \leq 1$
$2) \alpha =1$
$3) \alpha > 1$
$4) \alpha < 1$
------
خب با استقرا به گزینه ۲ می رسیم ، آیا با روشی دیگر می توان این مسئله را حل کرد ؟

با یک مثال ساده ثابت میشه که گزینه ۱ درسته :
حالتی که یک نود داریم که هم ریشه و هم برگ که جواب سیگما میشه ۱
استقرایی که بگم : حالا به ازای هر بچه ای که برای اولین بار به برگی در لول x اضافه میشه و اونو تبدیل به یک والد می کنه ،
$2^(-x)$
به سیگما اضافه میشه و بجاش دوبرابر اون عدد از حاصل سیگما کم میشه (خود والد دیگه برگ نیست) و برای بچه دوم حداکثر عدد مربوط به والد به جمع سیگما اضافه میشه که قبلا کم کردیم . (یعنی ۲ برابر عدد فوق که میشه برابر با عددی که قبلا به ازای برگی در لول x به سیگما اضافه شده بود)
پس حداکثر نتیجه سیگما ۱ خواهد بود.

حداکثر برگهای درخت دودویی در عمق d یعنی حالتی که درخت فول باشه برابر $2^{_{d}}$ هست. به این ترتیب جواب سیگما میشه: $2^{^{d}}\times 2^{^{-d}}$
که جواب یک هست و گزینه دو صحیحه.

اصلاح: الان که با دقت نگاه کردم گزینه ۱ درسته. درخت اگه فول باشه حداکثر مقدار یک هست ولی درخت میتونه فول نباشه بنابراین کمتر از یک هم میتونه باشه.