المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۶:سوال ۳۳

سوال ۳۳

یک مثلث‌بندی، افرازی از سطح یک ‎$n$‎ ضلعی به مثلث‌ها است به نحوی که برای هر دو مثلث یکی از حالات زیر برقرار باشد‎:‎

  1. دو مثلث دقیقاً در یک ضلع کامل مشترک باشند.
  2. دو مثلث دقیقاً در یک رأس مشترک باشند.
  3. دو مثلث هیچ اشتراکی نداشته باشند.

می‌خواهیم هر یک از این مثلث‌ها را با یکی از دو رنگ سیاه و سفید رنگ کنیم به نحوی که هر دو مثلث مشترک در یک ضلع، رنگ متفاوت داشته باشند و در ضمن اضلاع ‎$n$‎ ضلعی متعلق به مثلث‌های سفید باشند. به عنوان مثال در شکل بالا چنین مثلث‌بندی‌ای برای یک ‎۶‎ ضلعی داده شده است.

آیا می‌توان یک مثلث‌بندی با شرایط فوق برای یک ‎۸‎ ضلعی ارائه داد؟

پاسخ

تعداد اضلاع مثلث‌های سفید از تعداد اضلاع مثلث‌های سیاه به اندازه‌ی تعداد اضلاع چندضلعی بیش‌تر است. برای یک ۸ ضلعی تعداد اضلاع مثلث‌های سفید ۸ واحد از تعدا اضلاع مثلث‌ها سیاه بیش‌تر است. چون هم تعداد اضلاع مثلث‌های سفید بر ۳ بخش‌پذیر است و هم تعداد اضلاع مثلث‌های سیاه پس این‌که اختلاف آن‌ها ۸ واحد باشد امکان‌پذیر نیست.


ابزار صفحه