تعدادی کاشی مستطیلی با اضلاع طبیعی داریم. کاشی $i$ ام به صورت $a_i \times b_i$ است. مجموع مساحت کاشی‌ها $3n$ است. دو کار زیر را در نظر بگیرید:

1. می‌خواهیم یک جدول $3 \times n$ را با این کاشی‌ها به طور معمول بپوشانیم. حق چرخاندن کاشی‌ها را نداریم؛ یعنی یک کاشی $a \times b$ را نمی‌توان به صورت $b \times a$ استفاده کرد.
2. می‌خواهیم به هر کاشی با شماره‌ی $i$ عدد حسابی $c_i$ را نسبت دهیم، طوری که $a_i + c_i \le n$ شود. متغیرهای $h_1$ تا $h_n$ را نیز تعریف می‌کنیم و در ابتدا مقدار آن‌ها را برابر صفر قرار می‌خواهیم. به ازای هر کاشی با شماره‌ی $i$ به مقدار تمام متغیرهای $h_{c_i + 1}$، $h_{c_i+2}$، $\ldots$ و $h_{c_i+a_i}$ به اندازه‌ی $b_i$ اضافه می‌کنیم. می‌خواهیم طوری عددهای $c_i$ را مشخص کرده باشیم که مقدار تمام $h_i$ ها در انتها برابر ۳ شود.

ثابت کنید کار (۱) امکان‌پذیر است، اگر و تنها اگر کار (۲) امکان‌پذیر باشد.

• سوال بعد