Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۷

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

الف) می‌خواهیم همه‌ی این دنباله‌ها را طوری پشت سرهم (روی یک خط) قرار دهیم که هر دنباله از دنباله‌ی قبلی و با تغییر بیت n ام و دقیقا یک بیت دیگر به‌دست آمده باشد. ثابت کنید در حالتی که بیش از یک دنباله در این مجموعه وجود داشته باشد و n2k و n3 این کار امکان‌پذیر نیست.

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


ابزار صفحه