فهرست مندرجات
سوالات ۱۳ تا ۱۵
۴۰ توپ را در ۵ جعبه با شماره‌های ۱٫۲٫۳٫۴٫۵ قرار می‌دهیم (جعبه‌ها می‌توانند خالی هم باشند). عمل «وسط به دو طرف» عملی است که در طی آن دو توپ از جعبه‌ی $۲ \le i \le ۴$ (در صورت وجود) خارج می‌شوند و یکی از آن‌ها به جعبه‌ی $i-۱$ و یکی به جعبه‌ی $i+۱$ می‌رود.
با توجه به توضیحات بالا به ۳ سوال زیر پاسخ دهید:
سوال ۱۳
تعداد راه‌های قرار دادن توپ‌ها در جعبه‌ها به نحوی که تعداد توپهای جعبه‌ی اول با جعبه‌ی پنجم و جعبه‌ی دوم با جعبه‌ی چهارم برابر باشد٬ در کدام یک از بازه‌های زیر قرار می‌گیرد؟
- [۲۰۰٫۴۰۰]
- [۶۰۰٫۸۰۰]
- [۴۰۰٫۶۰۰]
- [$\infty$+۸۰۰٫]
- [۰٫۲۰۰]
پاسخ
گزینه (۱) درست است.
فرض کنید در جعبه‌ی $i$ ام $a_i$ توپ قرار داشته باشد. چون $a_1=a_5$ و $a_2=a_4$ پس $a_3$ زوج است. داریم: $a_1+a_2+\frac{a_3}{2}=20$. پس تعداد پاسخ‌ها برابر است با $\binom{22}{2}$.
سوال ۱۴
به حالتی از قرارگیری توپ‌ها در سبد حالت «گوشه‌گیر» می‌گوییم اگر با انجام تعدادی عمل وسط‌به‌دو‌طرف از آن حالت به حالتی برسیم که تمام توپ‌ها در جعبه‌ی اول و آخر قرار بگیرند. تعداد حالت‌های گوشه‌گیر چند است؟
- تعداد حالت‌هایی که تعداد توپهای جعبه‌ی اول با جعبه‌ی پنجم و جعبه‌ی دوم با جعبه‌ی چهارم برابر باشد.
- صفر
- ۴۱
- ۴۰
- تعداد حالت‌هایی که مجموع توپهای خانه‌های دوم و سوم و چهارم زوج باشد.
پاسخ
گزینه (۳) درست است.
پس از انجام هر عمل وسط به دو طرف حداقل یک توپ به یکی از جعبه‌های ۲ و ۳ و ۴ منتقل می‌شود، پس یک حالت گوشه‌گیر است اگر و فقط اگر از ابتدا گوشه‌گیر باشد یعنی ۴۱ حالت گوشه‌گیر داریم.
سوال ۱۵
به حالتی از قرارگیری توپ‌ها «بی‌حرکت» می‌گوییم اگر نتوان هیچ عمل وسط‌به‌دو‌طرفی روی آن انجام داد. با شروع از یک حالت دل‌خواه حداکثر چند مرحله طول می‌کشد تا به یک وضعیت بی‌حرکت برسیم.
- ۷۹
- ۸۰
- ۷۷
- ۷۵
- ۷۸
پاسخ
گزینه (۳) درست است.
وضعیت بی‌حرکت وضعیتی است که در هرکدام از جعبه‌های ۲ و ۳ و ۴ حداکثر یک توپ قرار داشته باشد. بیش‌ترین تعداد گام در حالتی رخ می‌دهد که توپ‌ها در ابتدا همه در جعبه‌ی سوم باشند. حال برای هر حالت مقدار $s$ را اینگونه تعریف کنید: $s=\textstyle \sum_{i=1}^5 a_{i}^{2}$. پس از هر عمل وسط به دو طرف دقیقا دو واحد به $s$ اضافه می‌شود. از طرفی هنگامی که تمام توپ‌ها در جعبه‌ی سوم باشند، به راحتی مشاهده می‌شود که حالت بی‌حرکت نهایی حالتی است که در آن : $a_1=19,a_2=1,a_3=0,a_4=1,a_5=19$. تعداد مراحل برای رسیدن به این حالت برابر است با $\frac{1}{2}(s_{end}-s_{start})=\frac{514-360}{2}=77$.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
