سوال ۳

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

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

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