در این قسمت 7 سوال وجود دارد
در یک جدول $n \times n$ اعداد صحیح متمایز نوشته ایم. در هر سطر خانه ماکسیمم را قرمز کردیم نشان دهید قطر پراکنده با مجموع ماکسیمم شامل عددی قرمز است.
جایگشت $\pi$ از اعداد 1,2,3,4,5,6,7 داریم . در هر مرحله میتوان دو عنصر را جابجا کرد . کمینه ی مراحل لازم برای مرتب کردن $\pi$ را $f(\pi)$ مینامیم . مجموع مقادیر $f(\pi)$ را به ازای تمام جایگشت ها پیدا کنید .
یک دسته کارت که روی آن $2n$ عدد از $0$ تا $2n-1$ عمل بر زدن را اینطور تعریف میکنیم : ابتدا کارت ها را به دسته ی $n$ کارتی تقسیم میکنیم . سپس به ترتیب یک کارت از دسته ی اول و یک یک کارت از دسته ی دوم بر میداریم و این کار را تا اتمام کارت ها ادامه میدهیم تا ترتیب جدیدی بدست بیاید . به این کار بُر زدن میگوییم . الف) ثابت کنید بعد از تعدادی محدود از بر زدن به ترتیب اولیه کارت ها میرسیم ب) برای $n=10$ چند بار باید عمل بر زدن را تکرار کنیم تا به دسته کارت اولیه برسیم ؟
جایگشت $a_1,a_2,a_3,a_4,a_5,a_6$ از اعداد 1 تا 6 داریم . در ابتدا یک عدد دلخواه انتخاب میکنیم. سپس در هر مرحله اگر عدد $a_i$ انتخاب شده بود، در مرحله ی بعد به ازای $a_i \ne 6 $ عدد $a_{a_{i+1}}$ را انتخاب میکنیم . برای $a_i = 6$ هم عدد $a_1$ انتخاب میشود . به ازای چند جایگشت مختلف میتوان عدد اول را به گونه ای انتخاب کرد که بعد از تعدادی مرحله همه ی اعداد جایگشت حداقل یکبار انتخاب شده باشند؟
حرکت «بشین سرجات» را اینطور تعریف میکنیم که به ازای $p_i \ne i$ را با $i$ عوض کنیم و جایگشت جدیدی بسازیم . اگر تعداد جایگشت هایی که میتوان با این عمل به آن رسید را $x$ بنامیم ، به ازای جایگشت اولیه $<2,3,5,9,8,7,10,1,4,6>$ ، $x^4$ را پیدا کنید .
یک جایگشت از اعداد 1 تا $2^k$ داریم . میخواهیم آن را مرتب کنیم . برای اینکار از الگوریتم زیر استفاده میکنیم . 1. i را برابر 1 قرار بده 2. $a_i$ را با $a_{a_i}$ جابجا کن 3. به i یک واحد اضافه کن 4. اگر i کمتر از $2^k$ بود به مرحله ی 2 برو 5. پایان الف)ثابت کنید به ازای هر جایگشتی پس از k بار اجرای الگوریتم ، مرتب میشود ب) به ازای هر k جایگشتی ارائه دهید که نتوان آن را با k-1 بار اجرا آن را مرتب کرد
یک نابجایی در یک جایگشت را اینطور تعریف میکنیم که به ازای i<j ، $a_i > a_j$ باشد. $f(x)$ را تعداد نابجایی در یک گراف تعریف میکنیم .جایگشتی از 1 تا 100 داریم . هدف صفر شدن تعداد نابجایی و مرتب شدن صعودی جایگشت است.در هر مرحله میتوانیم دو اندیس مشخص کنیم و به ماشین بدهیم تا آنهارا جابجا کند . روشی ارائه دهید به ازای هر جایگشتی در 198 مرحله آن را به وضعیات ایده آل برساند