المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۱

یک مربّع با اضلاع موازی محورهای مختصات را تفرقک می‌نامیم. سلطان یک تفرقک در صفحه کشیده است. او در هر مرحله می‌تواند یکی از کارهای زیر را انجام دهد:

  • یک تفرقک با خطوط کشیده شده انتخاب کند و دایره‌ای درون آن، مماس بر اضلاع تفرقک بکشد.
  • یک دایره با خطوط کشیده شده انتخاب کند و تفرقکی درون آن بکشد، طوری که هر چهار رأس‌ش روی محیط دایره باشند.
  • یک دایره با خطوط کشیده شده انتخاب کند و تفرقکی دور آن بکشد، طوری که اضلاع‌ش مماس بر دایره باشند.
  • یک تفرقک با خطوط کشیده شده انتخاب کند و آن را پاک کند.
  • یک دایره با خطوط کشیده شده انتخاب کند و آن را پاک کند.
  • یک تفرقک با خطوط کشیده شده انتخاب کند و با کشیدن دو پاره‌خط عمودی و افقی، آن را به چهار تفرقک برابر تقسیم کند.

توجه کنید ممکن است با پاک کردن یک تفرقک، قسمتی از یک یا چند تفرقک دیگر نیز از بین برود. سلطان یک شکل را ریسمانی می‌گوید، هر گاه قابل ساختن از شکل اولیه (یک تفرقک) با تعدادی مرحله باشد. چند تا از چهار شکل زیر، ریسمانی هستند؟

  1. ۳
  2. ۰
  3. ۱
  4. ۴
  5. ۲

راهنمایی

ابتدا سعی کنید شکل بالا راست را با استفاده از گام‌های داده شده رسم کنید.

راهنمایی

در راستای راهنمایی پیشین، از گام‌های اول، دوم، چهارم و ششم استفاده کنید.

راهنمایی

در راستای راهنمایی پیشین، با اجرای به ترتیب گام‌های اول، دوم، اول، دوم، اول، دوم می‌توانید بخش خوبی از شکل بالا راست را رسم کنید.

راهنمایی

سعی کنید با استفاده از گام‌های اول، ششم و چهارم شکل بالا چپ را رسم کنید.

راهنمایی

در راستای راهنمایی قبل، سعی کنید اعمال را به ترتیب اول، ششم، چهارم، چهارم اجرا کنید.

راهنمایی

برای رسم شکل پایین راست، سعی کنید از اعمال اول، سوم، چهارم، پنجم و ششم استفاده کنید.

راهنمایی

در راستای راهنمایی پیشین، سعی کنید ابتدا جدولی ۴×۴ شکل دهید.

راهنمایی

در راستای راهنمایی پیشین، دقت کنید اگر در هر خانه از جدول شکل داده شده یک دایره رسم کنید، کشیدن و پاک کردن تفرقک‌های خانه‌ها نسبت به هم مستقل خواهد شد.

راهنمایی

سعی کنید نشان دهید نمی‌توان شکل پایین چپ را رسم کرد.

راهنمایی

بدون از دست دادن کلّیت مسئله فرض کنید اندازه‌ی ضلع تفرقک آغازین برابر ۱ و مختصات رأس پایین-چپ آن برابر $(0, 0)$ باشد.

راهنمایی

از محل قرارگیری سه دایره‌ی شکل و مقادیری که ممکن است عرض نقاط پایینی دایره‌های شکل گرفته باشد، سعی کنید به تناقض برسید.

پاسخ

گزینه‌ی ۱ درست است.

  • روش ساختن شکل بالا-چپ: ابتدا یک دایره درون تفرقک آغازین می‌کشیم. سپس تفرقک آغازین را به چهار تفرقک برابر تقسیم می‌کنیم. در انتها دو تفرقک بالا-راست و پایین-چپ را پاک می‌کنیم.
  • روش ساختن شکل بالا-راست: ابتدا تفرقک آغازین را به چهار تفرقک برابر تقسیم می‌کنیم. سپس دایره‌ای درون آن کشیده و درون دایره‌ی کشیده شده یک تفرقک می‌کشیم. دوباره درون تفرقک کشیده شده یک دایره کشیده و درون آن یک تفرقک می‌کشیم. باز هم درون تفرقک کشیده شده یک دایره می‌کشیم. حال با پاک کردن سه تفرقک تودر‌تو، شکل به وجود می‌آید.
  • روش ساختن شکل پایین-راست: ابتدا تفرقک آغازین را به چهار تفرقک برابر تقسیم می‌کنیم. سپس هر کدام از چهار تفرقک ساخته شده را به چهار تفرقک کوچک‌تر تبدیل می‌کنیم. حال درون هر یک از ۱۶ تفرقک کوچک، یک دایره می‌کشیم. شش تفرقک کوچکی را که در شکل نیستند، پاک می‌کنیم (اگر قبل از پاک کردن، قسمتی از آن‌ها از بین رفته بود، دور دایره‌ی متناظرشان یک تفرقک می‌کشیم تا دوباره تفرقک کامل شود، سپس تفرقک را پاک می‌کنیم). ممکن است پس از انجام این کار، برخی از تفرقک‌های کوچک مطلوب نیز ناقص شوند. دایره‌ی این تفرقک‌های مطلوب ناقص را در نظر گرفته و با کشیدن یک تفرقک دور آن‌ها، تفرقک را کامل می‌کنیم. در انتها تمام دایره‌ها را پاک می‌کنیم.
  • اثبات ریسمانی نبودن شکل پایین-چپ: بدون از دست دادن کلّیت مسئله فرض کنید اندازه‌ی ضلع تفرقک آغازین برابر ۱ و مختصات رأس پایین-چپ آن برابر $(0, 0)$ باشد. در این صورت مختص $y$ پایین‌ترین نقطه‌ی هر دایره یا تفرقک جدیدی که به وجود می‌آید، به صورت $a+b\sqrt{2}$ است که $a$ و $b$ اعدادی گویا هستند. هم‌چنین شعاع هر دایره‌ی جدید و ضلع هر تفرقک جدید نیز به همین صورت است. در شکل داده شده، سه دایره‌ی کشیده شده را در نظر بگیرید. اگر مختص $y$ پایین‌ترین نقطه‌ی دو دایره‌ی پایین $a+b\sqrt{2}$ و شعاع دایره برابر $a'+b'\sqrt{2}$ باشد، مختص $y$ پایین‌ترین نقطه‌ی دایره‌ی بالا برابر $a+b\sqrt{2}+(a'+b'\sqrt{2})\sqrt{3}$ است. تناقض حاصل حکم را ثابت می‌کند.

ابزار صفحه