المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۴:سوال یک

بازی رنگی

دیروز ببعی و گاوی پس از چریدن طولانی خسته شدند و تصمیم گرفتند یک بازی انجام دهند. در این بازی ۳ دایره وجود دارد که هر یک به ۳n قطاع برابر تقسیم شده‌اند. ابتدا ببعی هر یک از قطاع‌های دایره‌ی شماره‌ی ۱ را با یکی از رنگ‌های زرد، نارنجی و بنفش رنگ می‌کند. گاوی پس از دیدن رنگ‌آمیزی ببعی، هر یک از قطاع‌های دایره‌ی شماره‌ی ۲ را با یکی از همین سه‌رنگ، رنگ می‌کند. ببعی نیز پس از دیدن رنگ‌آمیزی گاوی، دایره‌ی شماره‌ی ۲ را روی دایره‌ی شماره‌ی ۱ می‌گذارد و آن را به هر مقداری که می‌خواهد، می‌چرخاند به طوری‌که هر قطاع آن بر قطاعی از دایره‌‌ی شماره‌ی ۱ منطبق شود. حال دایره‌ی شماره‌ی ۳ روی دو دایره‌ی دیگر گذاشته ‌می‌شود، طوری که هر قطاع آن بر قطاعی از دایره‌های زیرین منطبق شود. پس از این کار هر قطاع دایره‌ی شماره‌ی ۳به صورت زیر رنگ می‌شود:

  • اگر رنگ دو قطاع زیرین دایره‌های شماره‌ی ۱ و ۲ یکسان بود، این قطاع را نیز به همان رنگ درمی‌آوریم.
  • اگر رنگ دو قطاع زیرین یکسان نبود، رنگ این قطاع را به رنگ سوم‌ (رنگی که در دو قطاع زیرین نیامده است) درمی‌آوریم.

گاوی اصلیتی هلندی دارد و به همین دلیل به رنگ نارنجی بسیار علاقه‌مند است و می‌خواهد تا حد ممکن تعداد قطاع‌های نارنجی دایره‌ی شماره‌ی ۳ زیاد شود؛ در حالی که ببعی می‌خواهد از این کار جلوگیری کند.

  • الف)‌ ثابت کنید گاوی می‌تواند طوری بازی کند که دایره‌ی شماره‌ی ۳ در انتها حداقل n قطاع نارنجی داشته‌باشد. (۲۰ نمره)
  • ب) ثابت کنید ببعی می‌تواند طوری بازی کند که دایره‌ی شماره‌ی ۳ در انتها حداکثر n قطاع نارنجی داشته‌باشد. (۲۰ نمره)

پاسخ

الف) پس از زنگ‌آمیزی دایره‌ی شماره ۱ توسط ببعی، طبق اصل لانه کبوتری رنگی وجود دارد که دست کم $n$ قطاع، به آن رنگ در آمده باشد. اگر این رنگ، نارنجی، زرد یا بنفش باشد، به ترتیب کافی است گاوی تمام قطاع‌های دایره‌ی شماره‌ی ۲ را به رنگ نارنجی، بنفش یا زرد در بیاورد. با این کار در دایره‌ی شماره ۳ دست کم $n$ قطاع نارنجی تولید خواهد شد.

ب) در ابتدا ببعی برای هر رنگ، $n$ قطاع از دایره‌ی شماره ۱ انتخاب می‌کند و آن‌ها را به آن رنگ در می‌آورد. فرض کنید گاوی در رنگ‌آمیزی خود، $x$ قطاع به رنگ زرد، $y$ قطاع به رنگ بنفش و $n-x-y$ قطاع را به رنگ نارنجی درآورده باشد. $3n$ انتخاب ممکن برای چرخش دایره‌ی شماره‌ی ۲ برای ببعی وجود دارد. تعداد قطاع‌های نارنجی‌ای که در مجموع این $3n$ حالت در دایره‌ی شماره‌ی ۳ پدید خواهند آمد برابر است با:

$$(x\times n)+(y\times n)+((n-x-y)\times n)=3\times n^2$$

پس طبق اصل لانه‌ی کبوتری، انتخابی برای ببعی وجود دارد که در آن حالت دست کم

$$\lceil \frac{3n^2}{3n} \rceil=n$$

قطاع از دایره‌ی شماره ۳ به رنگ نارنجی در بیاید.


ابزار صفحه