سوال ۱۷
$n$ رشته‌ی دودویی متمایز به طول $l$ داریم ($n,l>0$). گراف $G$ را از روی این رشته‌ها بدین ترتیب می‌سازیم:
به ازای هر رشته یک رأس قرار می‌دهیم، و دو رأس را به هم وصل می‌کنیم اگر و تنها اگر طول «بزرگترین پیشوند مشترک» رشته‌های متناظر آن‌ها عددی زوج باشد.
به عنوان مثال رئوس متناظر رشته‌های $1101001$ و $1101100$ را به هم وصل می‌کنیم زیرا بزرگترین پیشوند مشترکشان $1101$ است، ولی رئوس متناظر رشته‌های $0100111$ و $0101001$ را به هم وصل نمی‌کنیم زیرا بزرگترین پیشوند مشترکشان $010$ است. همچنین رئوس متناظر دو رشته‌ی $0100111$ و $1000111$ را نیز به هم وصل می‌کنیم زیرا طول بزرگترین پیشوند مشترکشان صفر است.
فرض کنید در گراف $G$ حاصل، بزرگترین زیرگراف کامل، $k$ رأسی باشد و عدد استقلال (اندازه‌ی بزرگترین مجموعه مستقل رأسی) آن $e$ باشد. ثابت کنید $e \times k \geq n$ .
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
