سوال ۲۰
یک متغیر منطقی٬ یکی از دو مقدار «درست» یا «غلط» را می‌پذیرد. اگر $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}$ یعنی ۱۲۶ جواب دارد٬ به ازای هر جوابی از معادله یک دنباله‌ی صعودی و به ازای هر دنباله‌ای صعودی یک جواب مطلوب برای جدول به‌دست می‌آید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
