سوال ۱۰

گرافی ۱۰۰۰ رأسی با رأس‌های ۱ تا ۱۰۰۰ در نظر بگیرید. برای هر $1 \le i < j \le 1000$ ، بین دو رأس $i$ و $j$ یال قرار می‌دهیم، اگر و تنها اگر $i$ اُمین رقم نمایش دودویی عدد $j$ (از سمت راست) برابر ۱ باشد. کوچک‌ترین $k$ را بیابید که بتوان با $k$ رنگ رأس‌های این گراف را رنگ‌آمیزی کرد، طوری که هر دو رأس مجاور ناهم‌رنگ باشند.

۲
۳
۴
۵
۶

پاسخ

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

ابتدا ثابت می‌کنیم رنگ‌آمیزی با کم‌تر از چهار رنگ امکان ندارد. رأس‌های شماره ۱، ۳، ۵ و ۲۱ دوبه‌دو به هم وصل هستند. پس دست کم به ۴ رنگ نیاز داریم. حال نشان می‌دهیم چهار رنگ برای رنگ‌آمیزی کافی است. رأس‌های ۱ و ۲ را با رنگ $A$ ، رأس‌‌ ۳ را با رنگ $B$ ، رأس‌های ۴ تا ۱۵ را با رنگ $C$ و رأس‌های ۱۶ تا ۱۰۰۰ را با رنگ $D$ رنگ کنید.

المپدیا

ابزار کاربر

ابزار سایت

سوال ۱۰

ابزار صفحه