====== سوال ۱۰ ====== گرافی ۱۰۰۰ رأسی با رأس‌های ۱ تا ۱۰۰۰ در نظر بگیرید. برای هر $1 \le i < j \le 1000$، بین دو رأس $i$ و $j$ یال قرار می‌دهیم، اگر و تنها اگر $i$ اُمین رقم نمایش دودویی عدد $j$ (از سمت راست) برابر ۱ باشد. کوچک‌ترین $k$ را بیابید که بتوان با $k$ رنگ رأس‌های این گراف را رنگ‌آمیزی کرد، طوری که هر دو رأس مجاور ناهم‌رنگ باشند. - ۲ - ۳ - ۴ - ۵ - ۶ <پاسخ> گزینه‌ی ۳ درست است. ابتدا ثابت می‌کنیم رنگ‌آمیزی با کم‌تر از چهار رنگ امکان ندارد. رأس‌های شماره ۱، ۳، ۵ و ۲۱ دوبه‌دو به هم وصل هستند. پس دست کم به ۴ رنگ نیاز داریم. حال نشان می‌دهیم چهار رنگ برای رنگ‌آمیزی کافی است. رأس‌های ۱ و ۲ را با رنگ $A$، رأس‌‌ ۳ را با رنگ $B$، رأس‌های ۴ تا ۱۵ را با رنگ $C$ و رأس‌های ۱۶ تا ۱۰۰۰ را با رنگ $D$ رنگ کنید. * [[سوال ۹|سوال قبل]] * [[سوال ۱۱|سوال بعد]]