پس از این که تولد مصطفی به خوبی برگزار نشد. خانواده‌ی او تصمیم گرفتند یک جشن تولد مردانه با حضور جمعی از مردان خاندان برگزار کنند. $n$ نفر از مردان خاندان (از جمله بزرگ خاندان) در جشن شرکت کردند و به طرز جالبی پدر هر فرد حاضر در جشن (به جز بزرگ خاندان). در تولد حضور داشت. گوييم فرد $A$ جد فرد $B$ است. اگر $A$ یکی از افراد زیر باشد:
پدر $B$، پدر پدر $B$، پدر پدر پدر $B$، …. بزرگ خاندان به زیرمجموعه‌ای از افراد حاضر در جشن سلسله‌ای گوییم. اگر از هر دو عضو زبرمجموعه. یکی جد دیگری باشد و همچنین به جز بزرگ‌ترین فرد زیرمجموعه. پدر هر فرد زیرمجموعه. در زبرمجموعه باشد. در انتهای جشن مصطفی تصمیم گرفت برای یادگاری تعداد عکس تهیه کند. او برای این کار یک عکاس آورد. بزرگ خاندان به عکاس گفت که تنها از زیر مجموعه‌های سلسله‌ای افراد حاضر در جشن عکس بگیرد. سپس عکاس گفت که عکاسی از هر زیرمجموعه‌ی سلسله‌ای $S_i$ هزینه‌ی $T_i$ را دارد. خاندان مصطفی بسیار خانواده دوست هستند و به پدر خود احترام می‌گذارند. بنابراین تصمیم گرفتند تعدادی عکس بگیرند. طوری که هر کس با پدر خود در دست کم دو عکس آمده باشد. مصطفی برآورد کرد کمینه‌ی هزینه‌ی ممکن برای این کار $m$ واحد است. ثابت کنید افراد می‌توانند کار خود را با $m$ واحد هزینه. طوری انجام دهند که از هر زیرمجموعه‌ی سلسله‌ای، صفر يا دو بار عکس گرفته شده باشد.
پاسخ
سوال را به درخت در گراف تبدیل می کنیم.
بر روی حکم مساله استقرا می زنیم: برای n⇐۲ حکم برقرار است.
حال یک برگ در نظر بگیرید که ریشه نباشد. ( چون درخت حداقل دو برگ دارد می توان این کار را کرد ). طبق صورت سوال این برگ باید با پدرش در حداقل دو عکس آمده باشد. تمام زیر مجموعه های سلسله ای که این برگ عضوشان هست را در نظر بگیرید. مینیمم هزینه این مجموعه ها را x در نظر بگیرید. برای این که شرط صورت سوال برآورده شود حداقل باید 2x هزینه کنیم. حال این برگ را حذف می کنیم و از هزینه همه آن محموعه های سلسله ای، x واحد کم می کنیم. درختی جدید با n-1 راس ساخته می شود. طبق فرض استقرا این درخت روشی برای عکس گرفتن دارد که هم مینیمم هزینه را بدهد و هم از هر زیر مجموعه دقیقا 0 یا 2 بار عکس گرفته شده باشد. در این روش، از زیر مجموعه هایی که از هزینه شان x واحد کم کردیم ( با برگ محذوف اشتراک داشتند ) حداکثر یکیشان دو بار و بقیه ۰ بار استفاده شده اند. چرا؟ زیرا اگر بیشتر از یکیشان دقیقا دو بار استفاده شده باشد، آن مجموعه ای که راس های کمتری دارد قطعا زیر مجموعه دیگریست پس با حذف آن هنوز شرط مساله که از هر زیرمجموعه دو بار عکس گرفته باشیم برقرار است.
حال در میابیم که اگر هزینه درخت ساخته شده k باشد، m⇐k+2x چرا ؟ چون اگر برگ را برگردانیم و هزینه ها را هم x واحد اضافه کنیم، اگر مجموعه ای از آن هایی که این برگ را می پوشاندند انتخاب شده بود که اکنون هزینه آن محموعه x واحد بیشتر شده و ما یک عکاسی خوب برای درخت اولیه با هزینه k+2x پیدا کرده ایم. اگر هم نبود که مجموعه مینیمم را دو بار عکس می گیریم و چون هزینه های مجموعه هایی که در درخت ساخته شده عکس گرفته ایم تغییر نکرده اند، باز یک عکاسی خوب برای درخت اولیه با هزینه k+2x پیدا کرده ایم.
همچنین می دانیم که m>=k+2x چون یک عکاسی با مینیمم هزینه در درخت اولیه را در نظر بگیرید. این عکاسی حداقل یک عکس از برگ مذکور و پدرش دارد. بنابراین همین زیر مجموعه ها در درختی که ما ساختیم m-2x حد اکثر هزینه شان می تواند باشد. پس حکم ثابت شد.
اکنون دریافتیم که m=k+2x . اگر در اثبات m⇐k+2x دقت کنید می بینید که در روشی که ما برای عکاسی درخت اولیه ارائه دادیم فقط از مجموعه هایی که در درخت ساخته شده عکس گرفته شده اند استفاده شده و تنها یکی از مجموعه ها ( مجموعه مینیمم ) ممکن است اضافه شود و آن هم به طور جدا گفته شده که دقیقا دو بار از آن عکس گرفته می شود. پس ما یک روش که شرط مساله را پیدا می کند با هزینه k+2x پیدا کرده ایم. که همان m است. پس حکم ثابت شد.