Processing math: 20%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۴:سوال ۵

سوال ۵

n‎ یک عدد طبیعی دلخواه است. یک ترتیب دلخواه از اعداد ‎۱‎ تا ‎n‎ که در آن هر یک از اعداد ‎۱‎ تا ‎n‎ دقیقاً یک بار آمده باشد را یک جایگشت از ‎\{1‎, ‎2‎, ‎\dots‎, ‎n\}‎ می‌نامیم. می‌گوییم جایگشت ‎p_1‎, ‎p_2‎, ‎\dots‎, ‎p_n‎ در دنباله ‎a_1‎, ‎a_2‎, ‎\dots‎, ‎a_k‎ ظاهر شده است اگر اندیس‌های ‎1 \le i_1 < i_2 < \cdots < i_n \le k‎ وجود داشته باشند به طوری که برای هر ‎1 \le j \le n‎ داشته باشیم ‎a_{i_j}=p_j‎ . به‌عنوان مثال جایگشت ‎1,3,2‎ در دنباله 3,1,2,3,2,3 ظاهر شده است.

یک دنباله از اعداد ‎۱‎ تا ‎n‎ یک دنباله جالب نامیده می‌شود اگر هر جایگشت دلخواهی از ‎\{1‎, ‎2‎, ‎\dots‎, ‎n\}‎ در این دنباله ظاهر شده باشد.

ثابت کنید برای هر عدد طبیعی ‎n‎ حداقل یک دنباله جالب به طول ‎2^n‎ - ‎1‎ وجود دارد.

پاسخ


ابزار صفحه