آمار پرسش:
- پرسیده شده: 2021-06-06 03:39:02 -0500
- مشاهده شده: 411 بار
- بروز شده: 2024-03-02 08:38:08 -0500
پرسش‌های مشابه:
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
ضدعفونی درخت - سوال سه مرحله دو سال 1399
زاریچ که زندگی خود را وقف شکست ویروس کرونا کرده است، عقیده دارد که برای شکست واقعی این ویروس لازم است درخت‌ها نیز ضدعفونی شوند (حتی اگر مفاهیمی ریاضی باشند). یک درخت n رأسی در نظر بگیرید که رأس‌های آن با اعداد ۱، ۲، … و n شمارهگذاری شده باشند. میزان آلودگی هر یال برابر تفاضل شمارههای رأس‌های دو سرش است. مثلا یالی که دو رأس با شمارههای ۳ و ۵ را به یکدیگر وصل می‌کند دارای آلودگی ۲ است. میزان آلودگی یک درخت برابر مجموع آلودگی یال‌هایش است. زاریچ باید خود را برای پاک‌سازی هر نوع درختی آماده کند. لذا می‌خواهد بداند بیشینه‌ی آلودگی برای یک درخت n رأسی (با رأس‌های شمارهگذاری شده از ۱ تا n) چه‌قدر است. این مقدار بیشینه را بیابید. دقت کنید که ابتدا باید این مقدار را به ازای هر n به دست آورید و یک درخت n رأسی با بیشینه‌ی آلودگی را توصیف کنید، سپس اثبات کنید که درختی n رأسی با آلودگی بیشتر از آن وجود ندارد.
1 پاسخ
خب، ساختار کلی درختمون باید به صورت زیر باشه:
مقدار جواب هم با توجه به شکل، راحت به دست می یاد (خودم دیگه واقعا حال نداشتم حساب کنم 🗿)
حالا اول برا n های زوج اثباتشو می گم: آقا هر راسی توی درخت یه پدر داره (البته به جز ریشه) و منطقا هر یال در درخت هم بین یک پدر و فرزند هست. خب پس ما باید به ازای هر راس i، پدر اون راس رو j قرار بدیم؛ به طوریکه قدر مطلق i-j بیشینه بشه. با این حساب، خیلی واضحه که به ازای اعداد 1 تا n/2، باید پدرشون راس n باشه و به ازای اعداد n/2+1 تا n، باید پدرشون راس 1 باشه. حالا به ازای هر راسی باید بیاید اختلاف عددش با عدد پدرش رو حساب کنید و اعداد به دست اومده رو با هم جمع کنید (البته، راس 1 و n که نمی تونن هردوتاشون پدر هم باشن؛ پس تو حساب کردن مجموع، حواستون باشه که عدد یال بین راس 1 و n رو فقط یک بار حساب کنید؛ نه دو بار).
برای n=2k+1 هم به طریق مشابه بیان می شه؛ فقط اینکه، راس k+1 اختلافش با 1 و n یکسان هس و فرقی نداره که پدرش راس 1 باشه یا راس n؛ ولی من تو رسم درخت، راس k+1 ام رو فرزند راس 1 قرار دادم.
