المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۲:سوال ۲۰

سوال ۲۰

یک متغیر منطقی٬ یکی از دو مقدار «درست» یا «غلط» را می‌پذیرد. اگر $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.$$‎ صدق می‌کنند. به چند طریق می‌توان به این متغیرها مقادیر ‎«درست»‎ و ‎«غلط‍»‎ داد؟

  1. $126$
  2. $127$‎
  3. $128$
  4. $129$
  5. $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}$ یعنی ۱۲۶ جواب دارد٬ به ازای هر جوابی از معادله یک دنباله‌ی صعودی و به ازای هر دنباله‌ای صعودی یک جواب مطلوب برای جدول به‌دست می‌آید.


ابزار صفحه