سوال ۱۵
در یک ردیف ۳۳ خانه قرار دارد. که با اعداد ۱ تا ۳۳ شماره‌گذاری شده‌اند. زِبل خان در یک طرف این خانه ها قرار دارد (در کنار خانه‌ی شماره‌ی ۳۳). در هر صبح یک توپ در یکی از خانه‌ها قرار می‌دهیم. زبل خان هر روز ظهر اگر توپی دید به آن شلیک می‌کند و توپ می‌ترکد ( حدّاکثر در هر روز به یک توپ شلیک می‌کند و فقط همان توپ می‌ترکد). اگر یک توپ در خانه‌ی $i$ باشد، زبل خان خانه‌های پشت آن را نمی‌بیند (خانه‌های ۱ تا $i-۱$). دود حاصل از ترکیدن یک توپ در خانه‌ی $i$ام باعث می‌شود که زبل خان تا بعد از ظهر روز بعد نیز خانه‌های پشت آن را نبیند و در نتیجه اگر تا روز بعد توپی در آن خانه‌ها گذاشته شود، زبل خان آن را نمی‌بیند و به آن تیراندازی نمی‌کند. ما ۳۳ روز وقت داریم تا ۳۳ توپ در این خانه‌ها بگذاریم و همچنین در هر خانه حدّاکثر می‌توانیم یک‌بار توپ قرار دهیم. در پایان ۳۳ روز، به اندازه‌ی مجموع شماره‌ی خانه‌هایی که توپ در آنها قرار دارد، به ما جایزه می‌دهند. بیشترین جایزه‌ای را که می‌توان به دست آورد چقدر است؟
- ۱۳۶
- ۲۴۰
- ۲۵۶
- ۲۷۲
- ۲۸۹
پاسخ
گزینه‌ی (۴) درست است.
برای این که یک توپ در آخر سالم باقی بماند باید حداقل یک توپ در یکی از خانه‌های جلوی آن بترکد (یعنی خانه‌های بزرگ‌ترش) از طرفی یک توپ که منفجر شود فقط می‌تواند یک توپ به تعداد توپ‌هایی که قرار است آخرش بماند اضافه کند. از آن‌جا که حداقل نصف روزها داریم توپ می‌ترکانیم پس حداکثر 16 تا توپ داریم که برای هر توپ حتما یک توپ در خانه‌ای با عدد بیش‌تر ترکیده بوده پس جمع اعداد خانه‌هایی که در آخر در آنها توپ است نمی‌تواند از نصف بیش‌تر باشد.
حال اگر روز اول توپ را در خانه‌ی یک بگذاریم و از این به بعد روز 2i توپ را در خانه $2i+1$ بگذاریم و روز بعدش توپ را در خانه‌ی 2i بگذاریم در این صورت توپ خانه‌های 1 تا $2i$ نمی‌ترکد و در آخر توپ در خانه‌های زوج است که جمع آنها می‌شود 272.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
