المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

می‌خواهیم دور دایره، $m$ عدد طبیعی کوچک‌تر مساوی $n$، قرار دهیم به طوری که هر جایگشت از ۱ تا $n$ به صورت زیردنباله‌ای از اعداد دور دایره (در جهت عقربه‌های ساعت یا خلاف جهت عقربه‌های ساعت) باشد. زیردنباله دور دایره، بدین معناست که اعدادی (نه لزوما پشت سر هم) را انتخاب کنیم و در جعت عقربه‌های ساعت یا خلاف آن به ترتیب قرار دهیم. (در قرار دادن اعدادد انتخاب شده، نمی‌توان بیش از یک دور، دور دایره را پیمود.) مثلا اگر ترتیب $1,3,2,3$ را دور دایره قرار دهیم، همه‌ی جایگشت‌ها را تولید می‌کند. اگر $m=\lfloor n/2 \rfloor(n-1)+n \quad mod \quad 2$، ثابت کنید می‌توان $m$ عدد با این مشخصه دور دایره قرار داد.


ابزار صفحه