المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۱

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

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

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

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

پاسخ

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

  • روش ساختن شکل بالا-چپ: ابتدا یک دایره درون تفرقک آغازین می‌کشیم. سپس تفرقک آغازین را به چهار تفرقک برابر تقسیم می‌کنیم. در انتها دو تفرقک بالا-راست و پایین-چپ را پاک می‌کنیم.
  • روش ساختن شکل بالا-راست: ابتدا تفرقک آغازین را به چهار تفرقک برابر تقسیم می‌کنیم. سپس دایره‌ای درون آن کشیده و درون دایره‌ی کشیده شده یک تفرقک می‌کشیم. دوباره درون تفرقک کشیده شده یک دایره کشیده و درون آن یک تفرقک می‌کشیم. باز هم درون تفرقک کشیده شده یک دایره می‌کشیم. حال با پاک کردن سه تفرقک تودر‌تو، شکل به وجود می‌آید.
  • روش ساختن شکل پایین-راست: ابتدا تفرقک آغازین را به چهار تفرقک برابر تقسیم می‌کنیم. سپس هر کدام از چهار تفرقک ساخته شده را به چهار تفرقک کوچک‌تر تبدیل می‌کنیم. حال درون هر یک از ۱۶ تفرقک کوچک، یک دایره می‌کشیم. شش تفرقک کوچکی را که در شکل نیستند، پاک می‌کنیم (اگر قبل از پاک کردن، قسمتی از آن‌ها از بین رفته بود، دور دایره‌ی متناظرشان یک تفرقک می‌کشیم تا دوباره تفرقک کامل شود، سپس تفرقک را پاک می‌کنیم). ممکن است پس از انجام این کار، برخی از تفرقک‌های کوچک مطلوب نیز ناقص شوند. دایره‌ی این تفرقک‌های مطلوب ناقص را در نظر گرفته و با کشیدن یک تفرقک دور آن‌ها، تفرقک را کامل می‌کنیم. در انتها تمام دایره‌ها را پاک می‌کنیم.
  • اثبات ریسمانی نبودن شکل پایین-چپ: بدون از دست دادن کلّیت مسئله فرض کنید اندازه‌ی ضلع تفرقک آغازین برابر ۱ و مختصات رأس پایین-چپ آن برابر $(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}$ است. تناقض حاصل حکم را ثابت می‌کند.

ابزار صفحه