المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۷:سوال ۳

خط کشی باشگاه

آقای ش. برای تغییر نمای حیاط باشگاه دانش پژوهان جوان می‌خواهد آن‌را خط کشی کند. حیاط باشگاه یک مربع $(2n+1) \times (2n+1)$ است . آقای ش. $2n$ نقطه با فاصله‌های یکسان ($1$ متر)، با گچ روی اضلاع حیاط مشخص کرده است که هیچ‌یک از این نقاط در گوشه نیست و فاصله‌ی نقاط انتها و ابتدای هر ضلع از گوشه نیز $1$ متر است. سپس او بعضی از این نقاط را پاک می‌کند. به‌طور دقیق‌تر، اگر نقاط روی ضلع سمت چپ و راست حیاط را از بالا به پایین، و نقاط روی ضلع بالا و پایین حیاط را از چپ به راست با اعداد $1$ تا $2n$ شماره گذاری کنیم،‌ همه‌ی نقاط با شماره‌ی زوج در ضلع چپ و بالا، و همه ی نقاط با شماره‌ی فرد در ضلع راست و پایین پاک می‌شوند (و بقیه‌ی نقاط شماره‌ی قبلی خود را حفظ می‌کنند).

آقای ش. بقیه کار خط کشی حیاط را به هوشنگ سپرده است. هوشنگ می‌خواهد بعضی از اضلاع حیاط (از بین $4$ ضلع)‌ را انتخاب کند و تعدادی دانش پژوه روی هر نقطه‌ی پاک نشده بر روی هر کدام از اضلاع انتخاب شده قرار دهد. پس از آن، دانش پژوهان را به ترتیب دلخواهش صدا کند. هر دانش پژوه زمانی که اسمش صدا زده شود، به سمت ضلع روبری خود می‌رود و یک خط صاف می‌کشد (عمودی یا افقی)‌، تا زمانی که به خطی عمود در مسیر حرکتش (یا ضلع روبرو)‌ برسد.

ابتدا هیچ خطی جز چهار ضلع حیاط وجود ندارد.

شکل زیر خط کشی حیاط باشگاه برای $n=2$ و این‌که هوشنگ هر چهار ضلع جدول را انتخاب کند را نشان می‌دهد (عدد روی خطوط نشان دهنده ترتیب کشیده شدن آنهاست).

ترتیب صدا زده شدن دانش پژوهان در این حالت:

  1. دانش پژوه روی نقطه $1$ ضلع سمت چپ
  2. دانش پژوه روی نقطه $2$ ضلع سمت راست
  3. دانش پژوه روی نقطه $1$ ضلع بالا
  4. دانش پژوه روی نقطه $3$ ضلع بالا
  5. دانش پژوه روی نقطه $2$ ضلع پایین
  6. دانش پژوه روی نقطه $3$ ضلع سمت چپ
  7. دانش پژوه روی نقطه $4$ ضلع سمت راست
  8. دانش پژوه روی نقطه $4$ ضلع پایین

دو خط کشی (شکل) متفاوت‌اند اگر و تنها اگر نقطه‌ای از حیاط باشد که در یکی رنگی شده‌‌باشد و در دیگری نه.

هوشنگ محاسباتش خیلی خوب نیست و از شما خواسته به سوالات زیر پاسخ دهید.

$1$- الف ($11$ نمره) : اگر $n = 10$ و هوشنگ اضلاع بالا و چپ را انتخاب کند،‌ به ازای همه ی ترتیب های مختلف از این $2n$ دانش پژوه چند خط کشی(شکل) مختلف به وجود می‌آید؟ باقی‌مانده‌ی تقسیم این عدد بر $\Delta$ را بدست آورید.

$2$- ب ($11$ نمره) : اگر $n = 200$ و هوشنگ اضلاع بالا و چپ و راست را انتخاب کند،‌ به ازای همه ی ترتیب های مختلف از این $3n$ دانش پژوه چند خط کشی(شکل) مختلف به وجود می‌آید؟ باقی‌مانده‌ی تقسیم این عدد بر $\Delta$ را بدست آورید.

$3$- ج ($12$ نمره) : اگر $n = 3000$ و هوشنگ همه‌ی اضلاع را انتخاب کند،‌ به ازای همه ی ترتیب های مختلف از این $4n$ دانش پژوه چند خط کشی(شکل) مختلف به وجود می‌آید؟ باقی‌مانده‌ی تقسیم این عدد بر $\Delta$ را بدست آورید.


ابزار صفحه