====== سوال ۱۷ ======


‎$n$‎ رشته‌ی دودویی متمایز به طول ‎$l$‎ داریم ‎($n,l>0$)‎. گراف ‎$G$‎ را از روی این رشته‌ها بدین ترتیب می‌سازیم:

//به ازای هر رشته یک رأس قرار می‌دهیم، و دو رأس را به هم وصل می‌کنیم اگر و تنها اگر طول ‎«بزرگ‌‌ترین پیشوند مشترک»‎ رشته‌های متناظر آن‌ها عددی زوج باشد. 
//

به عنوان مثال رئوس متناظر رشته‌های ‎$1101001$‎ و ‎$1101100$‎ را به هم وصل می‌کنیم زیرا بزرگ‌ترین پیشوند مشترکشان 
‎$1101$‎ است، ولی رئوس متناظر رشته‌های ‎$0100111$‎ و ‎$0101001$‎ را به هم وصل نمی‌کنیم زیرا بزرگ‌ترین پیشوند 
مشترکشان ‎$010$‎ است. همچنین رئوس متناظر دو رشته‌ی ‎$0100111$‎ و ‎$1000111$‎ را نیز به هم وصل می‌کنیم زیرا طول بزرگ‌ترین پیشوند مشترکشان صفر است.

فرض کنید در گراف ‎$G$‎ حاصل، بزرگ‌ترین زیرگراف کامل، ‎$k$‎ رأسی باشد و عدد استقلال (‎اندازه‌ی بزرگترین مجموعه مستقل رأسی) آن ‎$e$‎ باشد. 
ثابت کنید ‎$e \times k \geq n$‎ .

  * [[سوال ۱۸|سوال بعد]]
  * [[سوال ۱۶|سوال قبل]]