المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۸:سوال ۲۹

سوال ۲۹

کامبیز شکل سمت چپ را روی کاغذ رسم کرده و به شاندیز داده است. این شکل از تعدادی «تکه‌خط» تشکیل شده است. تکه‌خط چیزی شبیه پاره‌خط است با این تفاوت که دو سر آن حتما دو دایره‌ی کوچک سیاه قرار دارد. شاندیز در هر مرحله می‌تواند سه دایره‌ی سیاه $A$٬ $B$ و $C$ که $A$ به $B$ و $A$ به $C$ با تکه‌خط متصل هستند ولی $B$ به $C$ متصل نیست را انتخاب کند٬ سپس تکه‌خط‌های $AB$ و $AC$ را حذف کرده و تکه خط $BC$ را به جای آن دو رسم کند (مانند شکل پایین). با تکرار این عمل تا جای ممکن٬ حداقل چه تعداد «تکه‌خط» ممکن است باقی بماند؟ (دقت کنید که در شکل سمت چپ هیچ سه نقطه‌ای روی یک خط نیستند.)

  1. ۱
  2. ۷
  3. ۸
  4. ۱۰
  5. ۱۴

پاسخ

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

شکل سوال را به صورت رو‌به‌رو رسم می‌کنیم:

در شکل $B$ شرایط لازم برای اجرای «عمل» وجود ندارد. پس هر ۶ تکه خط آن باقی می‌ماند.

تعداد تکه خط‌های متصل به هر نقطه را درجه‌ی آن نقطه می‌نامیم. این «عمل»، زوجیت درجه‌ی نقطه‌ها را تغییر نمی‌دهد. درجه‌ی همه‌ی ۸ نقطه در شکل $A$ فرد(۳) است. پس در پایان هم درجه‌ی آن‌ها فرد یعنی دست کم ۱ خواهد بود. بنابراین از این شکل هم دست‌کم ۴ خط باقی خواهد ماند.


ابزار صفحه