======   کاشی‌کاری  ======



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


  - می‌خواهیم یک جدول $3 \times n$ را با این کاشی‌ها به طور معمول بپوشانیم. حق چرخاندن کاشی‌ها را نداریم؛ یعنی یک کاشی $a \times b$ را نمی‌توان به صورت $b \times a$ استفاده کرد.
  - می‌خواهیم به هر کاشی با شماره‌ی $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$ ها در انتها برابر ۳ شود.

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




  * [[سوال ۲|سوال بعد]]