سوال ۲۰

یک متغیر منطقی٬ یکی از دو مقدار «درست» یا «غلط» را می‌پذیرد. اگر $P$ ‎ و $Q$ ‎ دو متغیر منطقی باشند٬ $P\Rightarrow Q$ ؛ یعنی اگر $P$ ‎ «درست» باشد٬ $Q$ ‎ هم «درست» است.

‎ $20$ ‎ متغیر منطقی‎ $q_{i,j}$ ‎ ( $1\leq i\leq 5‎ , 1\leq j\leq 4$ ) داریم که در رابطه زیر: ‎ $\left\{‎ ‎\begin{array}{l r}‎ ‎q_{i,j}&\Rightarrow&q_{i+1,j}&i<5\\‎q_{i,j}&\Rightarrow&q_{i,j+1}&j<4 ‎\end{array}‎ ‎\right.$ ‎ صدق می‌کنند. به چند طریق می‌توان به این متغیرها مقادیر ‎«درست»‎ و ‎«غلط‍»‎ داد؟

$126$
$127$ ‎
$128$
$129$
$130$ ‎

پاسخ

گزینه (۱) درست است.

گزاره‌های درست را با خانه‌ی سیاه و گزاره‌های غلط را با خانه سفید نمایش می‌دهیم(مانند شکل مقابل)

با ارتفاع خانه‌های سیاه ستون‌ها یک دنباله‌ی چهار عضوی می‌سازیم. دنباله‌ی متناظر به شکل ارائه شده $0,2,2,5$ می‌باشد٬ معلوم است که با شرایط مسئله همه‌ی دنباله‌های به‌دست آمده صعودی خواهند بود.

تعداد صفرهای دنباله را $x_0$ ، تعداد ۱ های دنباله را $x_1$ ،… و بالاخره تعداد ۵های دنباله را $x_5$ می‌نامیم که در این صورت به معادله‌ی $x_0+x_1+x_2+x_3+x_4+x_5=4$ می‌رسیم که در مجموعه اعداد نامنفی $\binom{9}{5}$ یعنی ۱۲۶ جواب دارد٬ به ازای هر جوابی از معادله یک دنباله‌ی صعودی و به ازای هر دنباله‌ای صعودی یک جواب مطلوب برای جدول به‌دست می‌آید.