کشور «$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$ در سه رقم متفاوت هستند.

با توجه به توضیح بالا به چهار سوال زیر پاسخ دهید:

سوال ۸: در کشور ۴-منگولیا می‌خواهیم به هر $\underline{شهر}$ یک رنگ اختصاص دهیم طوری که هیچ دو شهر مجاوری (که با جاده‌ی مستقیم متصل شده‌اند) هم‌رنگ نباشند. حداقل چند رنگ مختلف نیاز داریم؟

1. 2
2. 16
3. 8
4. 3
5. 4

سوال ۹: حداقل با چند رنگ می‌توانیم به هریک از $\underline{جاده‌های}$ کشور ۷-منگولیا رنگی اختصاص دهیم٬ که به هیچ شهری دو جاده‌ی هم‌رنگ متصل نباشند؟

1. ۸
2. $۲^۷$
3. ۷
4. ۵
5. ۶

سوال ۱۰: در کشور ۱۰-منگولیا حداقل چند $\underline{جاده}$ را باید گل‌کاری کنیم طوری که به هر شهر حداقل یک جاده‌ی گل‌کاری شده متصل باشد؟

1. $۲^{۱۰}$
2. ۱۱
3. ۱۰
4. $۲^۹$
5. ۹

سوال ۱۱: در کشور ۱۱-منگولیا حداقل چند $\underline{شهر}$ را باید چراغانی کنیم طوری که دست‌کم یکی از دو شهر متصل به هر جاده چراغانی باشد؟

1. $۲^۹$
2. ۱۰
3. ۱۱
4. ۹
5. $۲^{۱۰}$