المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:تئوری:سوال ۱۷

سوال ۱۷

مجموعه‌ی همه‌ی دنباله‌های $n$ تایی از صفر و یک که دقیقا $k$ یک دارند، در نظر می‌گیریم.

الف) می‌خواهیم همه‌ی این دنباله‌ها را طوری پشت سرهم (روی یک خط) قرار دهیم که هر دنباله از دنباله‌ی قبلی و با تغییر بیت $n$ ام و دقیقا یک بیت دیگر به‌دست آمده باشد. ثابت کنید در حالتی که بیش از یک دنباله در این مجموعه وجود داشته باشد و $n\neq 2k$ و $n\geq 3$ این کار امکان‌پذیر نیست.

ب) می‌خواهیم همه‌ی این دنباله‌ها را طوری پشت سرهم (روی یک خط) قرار دهیم که هر دنباله از دنباله‌ی قبلی و با تغییر دو بیت متوالی در دنباله، به دست آمده باشد. ثابت کنید اگر $k\neq 0,1,n-1,n$ باشد و $n$ فرد یا $k$‌زوج باشد، این کار امکان‌پذیر نیست.


ابزار صفحه