المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:تئوری مقدماتی دوم:سوال ۳

سوال ۳

یک ‎$n$‎-مینوی قشنگ در یک جدول ‎$n\times n$‎ به این شکل تعریف می شود:

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

اگر تعداد ‎$n$‎-مینوهای قشنگ را با ‎$T_{n}$‎ نشان دهیم، ثابت کنید: ‎$2^{n‎ - ‎1} \le T_{n}$‎ و‎$T_{n}\le 4^{n+1}$ ‎.


ابزار صفحه