سوال ۱۸
در ابتدا یک مهره روی نقطه‌ی
$(0, 0)$
صفحه‌ی مختصات قرار داده شده است. در هر مرحله می‌توان یک مهره با مختصات
$(x, y)$
به همراه یک عدد طبیعی $n$ انتخاب کرده و پس از برداشتن مهره‌ی مذکور، در هر یک از نقطه‌های
$$(x, y+1), (x, y+2), \ldots, (x, y+n-1)$$
و هم‌چنین نقطه‌های
$$(x-1, y+n), (x+1, y+n)$$
یک مهره قرار داد. گام‌ها باید طوری انجام شود که در هر لحظه در هر نقطه حداکثر یک مهره باشد. برای مثال در گام نخست با انتخاب تنها مهره‌ی موجود و $n=3$، صفحه به شکل زیر در می‌آید:
با انجام تعدادی مرحله، به کدام اشکال زیر می‌توان رسید؟ (محورهای مختصات کشیده نشده است. شکل در هر جایی از صفحه ایجاد شود، قابل قبول است).
- شکل ۲
- هیچ یک از شکل‌ها
- هر سه شکل
- شکل‌های ۱ و ۳
- شکل ۱
راهنمایی
عمل مطرح شده را با $n=2$ انجام دهید. همین کار را روی مهره‌های متفاوت حاصل انجام دهید تا برخی اشکال داده شده ساخته شوند.
راهنمایی
شکل ۱ را با چهار بار تکرار عمل تعریف شده‌ی راهنمایی پیشین بسازید.
راهنمایی
سعی کنید به خانه‌های صفحه‌ی مختصات وزن‌هایی نسبت دهید که با انجام یک عمل، مجموع وزن مهره‌های حاضر در جدول تغییری نکند.
راهنمایی
دقت کنید که $2^k = 2^{k-1} + 2^{k-2} + ... + 2^{k-x} + 2^{k-x}$
راهنمایی
به خانه‌های حاضر در عرض $y$ وزن $2^{-y}$ نسبت دهید. امکان تشکیل دو شکل ۲ و ۳ را رد کنید.
پاسخ
گزینه‌ی ۵ درست است.
به هر نقطه از صفحه با مختصات $(x, y)$ عدد $2^{y}$ را نسبت می‌دهیم. با انجام هر گام، مجموع اعداد نقاط مهره‌دار تغییری نمی‌کند. در ابتدا این مقدار برابر ۱ است، پس در انتها نیز باید برابر ۱ باشد. در شکل‌های ۲ و ۳ مقدار گفته شده نمی‌تواند به صورت $2^{t}$ باشد، پس رسیدن به این دو شکل امکان ندارد. با اعمال زیر می‌توان شکل ۱ را ساخت:
- انتخاب مهره‌ی روی نقطه‌ی $(0, 0)$ با $n=2$
- انتخاب مهره‌ی روی نقطه‌ی $(0, 1)$ با $n=2$
- انتخاب مهره‌ی روی نقطه‌ی $(0, 2)$ با $n=2$
- انتخاب مهره‌ی روی نقطه‌ی $(0, 3)$ با $n=2$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
