فهرست مندرجات
سوالات ۲۴ و ۲۵
اعضای تیم پلیس مخفی سلطان شامل پنج پلیس ماهر با شماره‌های ۱ تا ۵ است. این پنج نفر در آفتاب سوزان بندر دور یک میز گرد نشسته و هر کدام یک عینک آفتابی زده‌اند. عینک‌های آفتابی این افراد، یکی از سه رنگ قرمز، آبی و زرد را دارد. طبیعی است که این افراد، اجسام را به رنگ واقعی نمی‌بینند؛ بلکه ترکیب رنگ آن جسم با رنگ عینک خود را می‌بینند! برای مثال فردی که عینک زرد به چشم زده است، یک جسم آبی را به رنگ سبز و یک جسم زرد را به رنگ زرد می‌بیند. فرض کنید شیوه‌ی ترکیب رنگ اجسام با عینک‌ها مطابق جدول زیر است:
این قاعده برای عینک‌ها هم صادق است. پس برای مثال اگر پلیس $A$ عینک قرمز و پلیس $B$ عینک زرد داشته باشد، $A$ با نگاه کردن به $B$ تصوّر می‌کند رنگ عینک $B$ نارنجی است!
سوال ۲۴
سلطان که در کویری دور در حال انجام مأموریتی دیگر است، جویای احوال پلیس‌های خود می‌شود. هر یک از پلیس‌ها در گزارش خود، مجموعه‌ی رنگ‌هایی را که در میان عینک بقیه‌ی پلیس‌ها می‌بیند، می‌گوید. برای مثال فرض کنید پلیس‌ها به ترتیب عینک‌های قرمز، قرمز، آبی، زرد و زرد داشته باشند. پلیس شماره ۲ در پیام خود به سلطان می‌گوید:
«درود بر سلطان بزرگ! پلیس شماره ۲ هستم. من در عینک‌های پلیس‌های دیگر، رنگ‌های قرمز، بنفش و نارنجی را می‌بینم.»
حال سلطان پیام تمام پلیس‌ها را دریافت کرده و می‌خواهد تشخیص دهد اکنون رنگ عینک هر پلیس چیست. توجه کنید که سلطان می‌داند رنگ عینک هر پلیس، قرمز یا زرد یا آبی است. به ازای چند حالت از $3^5$ حالت (برای رنگ عینک پلیس‌ها)، سلطان پس از دریافت گزارش‌ها به طور یک‌تا می‌تواند بفهمد رنگ عینک هر پلیس چیست؟
- $150$
- $153$
- $183$
- $213$
- $243$
پاسخ
گزینه (۵) درست است.
اگر در پیام یک پلیس، یک رنگ اصلی (مثلاً قرمز) باشد، عینک خود او نیز به همان رنگ است. هم‌چنین اگر دو رنگ غیر اصلی در پیام یک پلیس باشند، رنگ عینک او یک‌تا تعیین می‌شود. پس در هر صورت رنگ یک پلیس از روی پیامش به طور یک‌تا تعیین می‌شود، مگر در حالتی که فقط یک رنگ غیر اصلی در پیامش باشد. در این حالت نیز ۴ پلیس دیگر باید به یک رنگ باشند و او به رنگی دیگر. با تعیین رنگ ۴ پلیس دیگر، رنگ این پلیس نیز مشخص خواهد شد. پس در هر صورت سلطان می‌تواند به هدف‌ش برسد.
سوال ۲۵
در نوع جدید پیام‌رسانی، هر پلیس، یک پلیس دیگر را انتخاب کرده و به سلطان پیام می‌دهد که رنگ عینک آن پلیس را چگونه می‌بیند. برای مثال فرض کنید رنگ عینک پلیس‌ها به ترتیب قرمز، قرمز، آبی، زرد و زرد باشد. پیام‌های پلیس‌ها می‌تواند به شکل زیر باشد:
- «درود بر سلطان بزرگ! پلیس شماره ۱ هستم. من عینک پلیس شماره ۵ را نارنجی می‌بینم.»
- «درود بر سلطان بزرگ! پلیس شماره ۲ هستم. من عینک پلیس شماره ۱ را قرمز می‌بینم.»
- «درود بر سلطان بزرگ! پلیس شماره ۳ هستم. من عینک پلیس شماره ۱ را بنفش می‌بینم.»
- «درود بر سلطان بزرگ! پلیس شماره ۴ هستم. من عینک پلیس شماره ۲ را نارنجی می‌بینم.»
- «درود بر سلطان بزرگ! پلیس شماره ۵ هستم. من عینک پلیس شماره ۴ را زرد می‌بینم.»
حال سلطان پیام تمام پلیس‌ها را دریافت کرده و می‌خواهد تشخیص دهد اکنون رنگ عینک هر پلیس چیست. توجه کنید سلطان می‌داند رنگ عینک هر پلیس قرمز یا زرد یا آبی است. $3^5$ حالت برای رنگ عینک پلیس‌ها و $4^5$ حالت برای این داریم که هر پلیس، رنگ عینک چه کسی را بفرستد. از این $3^5 \times 4^5$ حالت، در چند حالت سلطان به طور یک‌تا نمی‌تواند رنگ عینک پلیس‌ها را تشخیص دهد؟
- $0$
- $720$
- $13680$
- $17760$
- $18840$
پاسخ
گزینه (۴) درست است.
یک گراف می‌سازیم که رأس‌های آن متناظر با پلیس‌ها باشند و اگر پلیس $i$ عینک پلیس $j$ را به رنگ $c$ اعلام کرده باشد، یک یال جهت‌دار به رنگ $c$ از $i$ به $j$ می‌کشیم.
ابتدا جهت یال‌ها را برمی‌داریم؛ زیرا اگر پلیس $i$، عینک پلیس $j$ را به رنگ $c$ ببیند، پلیس $j$ نیز عینک پلیس $i$ را به همان رنگ می‌بیند.
یک مؤلفه در این گراف در نظر بگیرید. با مشخص شدن رنگ عینک یکی از رئوس آن، رنگ عینک هم‌سایه‌های آن و به همین ترتیب بقیه‌ی رئوس مؤلفه مشخص خواهد شد. اگر یک یال به رنگی اصلی داشته باشیم، عینک دو سر آن یال به رنگ خود یال است. اگر هم دو یال با رأس مشترک داشته باشیم که دو رنگ غیر اصلی متفاوت را داشته باشند، رنگ عینک رأس مشترک‌شان مشخص خواهد شد. پس تنها حالتی که رنگ عینک‌ها مشخص نمی‌شود، حالتی است که مؤلفه‌ای داشته باشیم که رأس‌هایش شامل دو رنگ اصلی باشند و هر یال شامل یک رأس از هر یک از این دو رنگ باشد. از طرفی هر مؤلفه‌ی $k$-رأسی این گراف شامل $k$ یال است و دقیقاً یک دور دارد. این دور نمی‌تواند به طول فرد باشد. پس تنها می‌تواند به طول ۲ یا ۴ باشد که با حالت‌بندی، پاسخ به‌دست می‌آید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
