آمار پرسش:
- پرسیده شده: 2024-04-19 06:02:40 -0600
- مشاهده شده: 136 بار
- بروز شده: 2024-10-31 10:42:06 -0600
پرسش‌های مشابه:
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
سوال 2 مرحله دوم دوره 34_روز دوم
....................................................................
1 پاسخ
یه گراف جهت دار می‌سازیم که رئوسش همون میز های 1 تا $n$ هستند. حالا به ازای راس $v$ فرض کنید اگه آهنربای ۱ رو روشن کنیم توپ از میز $v$ بره به میز $x$. اگر هم آهنربای $n$ رو روشن کنیم بره به $y$. حالا یه یال جهت دار از $v$ به $x , y$ میذاریم.
حالا اثبات میکنم درجه ورودی هر راسی برابر ۲ هست. اگر $n$ فرد باشه برای میز وسطی واضحه که دقیقا دو راس 1 , $n$ بهش یال دارن. برای سایر میز ها ( شامل حالت $n$ زوج ) میدونیم این میز به یکی از میز های ۱ و $n$ نزدیک تره. مثلا ۱. الانم راحت میشه دید رئوس $2v$ و $2v-1$ به $v$ یال دارن.
پس درجه ورودی و خروجی تمام راس ها برابر ۲ هست و از اونجایی که همه رئوس مسیری به راس ۱ دارن گراف زمینه ای هم‌بنده. پس تور اویلری داریم و برای رسیدن از راس $v$ به $u$ کافیه از تور استفاده کنیم!
