المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوال ۱۱

سوال ۱۱

در شکل مقابل دایره‌های سیاه را راس و هر پاره‌خط بین دو دایره‌ی سیاه را یک یال می‌نامیم. کدام یک از گزاره‌های زیر در مورد آن صحیح است؟

  1. می‌توان راس‌های آن را با ‎۴‎ رنگ متفاوت چنان رنگ کرد که رنگ هر دو راسی که با یک یال به هم متصلند متفاوت باشد.
  2. می‌توان اعداد ‎۱‎ تا ‎۱۰‎ را به راس‌های آن نسبت داد به قسمی که راس شماره‌ی ‎$i$‎ به ر‎اس‌های ‎$i-1$‎ و ‎$i+1$‎ وصل باشد ‎($2 \le i \le 9$)‎ و راس ‎۱‎ نیز به ‎۱۰‎ وصل باشد.
  3. می‌توان این شکل را بدون برداشتن قلم از روی کاغذ رسم کرد. ‎(راس‌ها را نقطه و یال‌ها را پاره‌خط در نظر بگیرید‎.‎)
  4. هر سه مورد فوق صحیح است.
  5. هیچکدام از موارد فوق صحیح نیست.

پاسخ

گزینه (۴) درست است.

گزینه‌ی «۱» صحیح است. کافی است راس‌های ۳٬۱ و ۱۰ زرد باشند. راس‌های ۲ و ۴ سبز باشند. راس‌های ۸٬۵ و ۹ قرمز باشند. و بالاخره راس‌های ۶ و ۷ آبی باشند.

گزینه‌ی «۲» نیز صحیح است. مطابق شکل زیر:

و بالاخره گزینه‌ی «۳» نیز صحیح است. مراحل رسم شکل به طریق زیر می‌باشد:

$$1\Rightarrow7\Rightarrow3\Rightarrow9\Rightarrow5\Rightarrow1\Rightarrow10\Rightarrow9\Rightarrow8\Rightarrow7\Rightarrow6\Rightarrow5\Rightarrow4\Rightarrow3\Rightarrow2\Rightarrow10\Rightarrow8 \\ \Rightarrow6\Rightarrow4\Rightarrow2\Rightarrow1$$


ابزار صفحه