سوال ۲۵
در شکل زیر ۲۷ نخود از بالا به سمت پایین انداخته می‌شود. نخودها به سمت پایین حرکت می‌کنند تا در درون یکی از مربع‌ها قرار بگیرند. درون هر دایره یک علامت $\swarrow$ یا $\searrow$ قرار دارد که در حالت عادی دیده نمی‌شود. با توجه به جهت علامت یک دایره، نخود پس از ورود به آن دایره به سمت «پایین سمت راست» یا «پایین سمت چپ» حرکت می‌کند. ما نمی‌توانیم در حالت عادی جهت علامت‌های دایره‌ها یا تعداد نخودهای موجود در مربع‌ها و دایره‌ها را ببینیم.
عمل «تغییر جهت» به این صورت تعریف می‌شود: به یکی از دایره‌ها از نزدیک نگاه می‌کنیم و علامت قرار داده شده در آن را می‌بینیم و اگر خواستیم آن را تغییر می‌دهیم.
ما می‌توانیم هر موقع که خواستیم انداختن نخودها را متوقف کنیم و عمل «تغییرجهت» را به تعداد دلخواه انجام دهیم و دوباره انداختن نخودها را ادامه دهیم.
می‌خواهیم تعدادی عمل «تغییر جهت» انجام دهیم، به طوری که وقتی همه‌ی ۲۷ نخود افتادند،در هر مربّع دقیقاً به تعداد عددی که روی آن نوشته شده نخود قرار بگیرد. حدّاقل چند عمل «تغییر جهت» نیاز داریم به طوری که به هر نحوی که علامت‌ها در ابتدا جهت‌دهی شده باشند، بتوانیم این کار را انجام دهیم؟
- ۶
- ۷
- ۱۱
- ۱۲
- ۱۴
پاسخ
گزینه‌ی (۳) درست است.
از آن‌جایی که از هر دو جهت دایره باید نخود عبور کند پس هر دایره حداقل یک‌بار تغییر جهت نیاز دارد.
از طرفی نخودهایی که از هر دو جهت هر دایره (به جز دایره‌ی سمت راست پایین) باید عبور کنند متفاوتند، پس باید قبل از تغییر جهت بدانیم نخودها در چه جهتی می‌رفتند.در نتیجه در کل به 6+5 عمل تغییر جهت نیاز داریم.
ابتدا با 5 حرکت جهت همه‌ی دایره‌ها را می‌فهمیم به جز دایره‌ی سمت راست پایین که مهم نیست در چه جهتی باشد. سپس هر کیسه که پر شد به ترتیب از پایین دایره‌ها را تغییر می‌دهیم تا همه‌ی کیسه‌ها پر شود
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
