سوالات ۸ و ۹ و ۱۰ و ۱۱
کشور «$k$-منگولیا» $۲^k$ شهر دارد که با شمارههای ۱ تا $۲^k-۱$ نامگذاری شدهاند. در این کشور بعضی از جفت شهرها با جاده به هم وصل هستند. برای اینکه بدانیم دو شهر با شمارههای $x$ و $y$ با یک جاده به هم وصل هستند یا خیر٬ ابتدا دو عدد $x$ و $y$ را در مبنای ۲ مینویسیم. اگر هر یک از دو عدد حاصل کمتر از $k$ رقم داشت٬ تعداد مناسبی ۰ به سمت چپ آن اضافه میکنیم تا هر دوی آنها $k$رقمی شوند. نهایتا شهرهای $x$ و $y$ با یک جاده به هم متصل هستند اگر و تنها اگر دو عدد به دست آمده دقیقا در یکی از $k$ رقم با هم متفاوت بودند. مثلا در کشور ۴-منگولیا٬ بین شهرهای ۱ و ۹ جادهی مستقیم وجود دارد چرا که $(\underline{0} 0 0 1)_2$ و $(\underline{1} 0 0 1)_2$ تنها در رقم سمت چپ با هم تفاوت دارند٬ ولی شهرهای ۲ و ۹ جادهی مستقیم ندارند چرا که $(\underline{0} 0 \underline{10})_2$ و $(\underline{1} 0 \underline{01})_2$ در سه رقم متفاوت هستند.
با توجه به توضیح بالا به چهار سوال زیر پاسخ دهید:
در کشور ۴-منگولیا میخواهیم به هر شهر یک رنگ اختصاص دهیم طوری که هیچ دو شهر مجاوری (که با جادهی مستقیم متصل شدهاند) همرنگ نباشند. حداقل چند رنگ مختلف نیاز داریم؟
پاسخ
گزینهی (۱) درست است.
این کشور با دو رنگ، قابل رنگآمیزی است. اعدادی که مجموع ارقام آنها فرد هستند را به رنگ ۱ و بقیه اعداد (با مجموع ارقام زوج) را به رنگ ۲ رنگآمیزی میکنیم. با این روش هر دو عدد مجاوری (چون دقیقا در یک رنگ متفاوتاند) در دو دسته قرار دارند و ناهمرنگ هستند.
حداقل با چند رنگ میتوانیم به هریک ازجادههای کشور ۷-منگولیا رنگی اختصاص دهیم٬ که به هیچ شهری دو جادهی همرنگ متصل نباشند؟
پاسخ
گزینهی (۳) درست است.
چون درجه هر راس ۷ است پس جواب کمتر از ۷ نیست و با روش زیر با ۷ رنگ گراف را رنگ میکنیم پس ۷ رنگ لازم و کافی است.
روش:
اگر دو عدد فقط در بیت $i$ام متفاوت بودند با رنگ $i$ یال بین آنها را رنگ میکنیم و چون هر بیت دو حالت دارد هر عدد دقیقا با یک عدد دیگر فقط در بیت $i$ ام متفاوت است پس هر راس از هر رنگ دقیقا یک یال خواهد داشت.
در کشور ۱۰-منگولیا حداقل چند جاده را باید گلکاری کنیم طوری که به هر شهر حداقل یک جادهی گلکاری شده متصل باشد؟
پاسخ
گزینهی (۴) درست است.
جادههای یکه برای تفاوت بیت اول کشیده شدهاند را گلکاری میکنیم. هر عدد با یک عدد دیگر در بیت اول متفاوت است پس همهی شهرها پوشش داده میشوند. همچنین هرجاده میتواند دو شهر را پوشش دهد و در کل $2^{10}$ شهر داریم پس $2^9$ جاده گلکاری شده لازم است.
در کشور ۱۱-منگولیا حداقل چند شهر را باید چراغانی کنیم طوری که دستکم یکی از دو شهر متصل به هر جاده چراغانی باشد؟
پاسخ
گزینهی (۵) درست است.
$2^{11}$ شهر داریم که به هر یک ۱۱ جاده متصل است. پس در کل $11×2^{10}$ جاده داریم و با چراغانی کردن هر شهر شرط برای ۱۱ جاده متصل به آن برقرار میشود. پس $2^{10}$ شهر چراغانی شده لازم است.
حال اگر شهرهایی که شمارهی آنها تعداد زوجی یک دارد را چراغانی کنیم شرط سوال برای همهی جادهها برقرار میشود. زیرا هر جاده بین دو شهر کشیده شده است که شمارهی آنها به جز در یک بیت یکسان است. پس زوجیت تعداد یکهای آنها با هم متفاوت است و یکی از آنها چراغانی شده است. بنابراین $2^{10}$ شهر چراغانی کافی است.