سوالات ۱۹ و ۲۰
مارال جایگشتِ $n$,تاییِ تماما صعودیِ $ {\langle 1,2,3,\ldots,n-1,n \rangle} $ را دارد و میخواهد آن را با تعدادی حرکت، به جایگشتِ تماما نزولیِ $\langle n,n-1,\ldots,3,2,1 \rangle$ تبدیل کند.
او در هر حرکت، میتواند مانند شکل زیر، سه جایگاهِ $ (i,j,k) $ را با شرطِ $\leq i < j < k \leq n$ در جایگشت خود انتخاب کند و اعدادِ این سه جایگاه را در آن، دَوَران دهد؛ یعنی عدد جایگاهِ $j$اُم را به جایگاهِ $i$اُم ببرد، عدد جایگاهِ $k$اُم را به جایگاهِ $j$اُم ببرد، و عدد جایگاهِ $i$اُم را به جایگاهِ $k$اُم ببرد.
مثلا با فرضِ داشتنِ جایگشتِ $\langle 3,\mathbf {6},\mathbf {5},4,1,\mathbf {2} \rangle$ ، اگر او سه جایگاهِ $ (2, 3, 6) $ را برای حرکتِ دوَران انتخاب کند، بعد از انجام این حرکت، به جایگشتِ $\langle 3,\mathbf {5},\mathbf {2},4,1,\mathbf {6} \rangle$ میرسد.
سوال ۱۹
بهازای چند عدد صحیحِ $n$ در محدودهی $2000$ تا $2025$ (شامل هر دوی این اعداد)، مارال میتواند با انجام تعدادی حرکت دوَران، جایگشتِ $n$ تاییِ تماما صعودیِ خود را به جایگشتی تماما نزولی تبدیل کند؟
- $14$
- $13$
- $0$
- $26$
- $17$
پاسخ
گزینه (1) درست است.
انجام این دَوَران معادل انجام دو جابهجایی (swap) است. به این شکل که ابتدا $p_i$ را با $p_j$ جابهجا میکنیم، سپس $p_j$ را با $p_k$ جابهجا میکنیم.
با انجام این دو جابهجایی میبینیم که اعداد مشابه دَوَران جابهجا میشوند. حال توجه کنید که در ابتدا، تعداد نابهجاییهای دنباله معادل انتخاب دو از $n$ است. هر جابهجایی (swap) زوجیت تعداد نابهجاییها را تغییر میدهد، بنابراین هر دَوَران زوجیت تعداد نابهجاییها را ثابت نگه میدارد. زوجیت تعداد نابهجاییها در انتهای فرآیند زوج (صفر) است، بنابراین اگر در ابتدا فرد باشد این کار ممکن نیست. تعاداد انتخاب از دو از $n$ برای $n$های به شکل $4k$ و $4k+1$ زوج است و برای بقیه فرد است.
حال ثابت میکنیم این کار برای $n=4k$ یا $n=4k+1$ ممکن است. این مسئله را با استقرای ریاضی ثابت میکنیم:
پایه: برای $k=0$ این موضوع مشخص است.
گام: اگر فرض کنیم این کار برای $n$ ممکن است، ثابت میکنیم اینکار برای $n+4$ نیز ممکن است. ابتدا جای $1$ را با $n$ و جای $2$ را با $n-1$ تغییر میدهیم. این کار را مطابق شکل زیر انجام میدهیم.
سپس بازهی $3$ تا $n-2$ را با استفاده از فرض استقرا برعکس میکنیم. با این کار گام استقرا ثابت میشود. تعداد اعدادی که به شکل $4k+1$ یا $4k$ هستند و در بازهی خواسته شده قرار دارند، $14$ عدد است.
سوال ۲۰
بهازای $n=3333$، مارال حداقل چند حرکت دوَران نیاز دارد تا بتواند جایگشتِ $n$ تاییِ تماما صعودیِ خود را به جایگشتی تماما نزولی تبدیل کند؟
- $1111$
- $2499$
- $1113$
- $1666$
- $2222$
پاسخ
گزینه (4) درست است.
اگر به روش گرفته شده در سوال قبل عمل کنیم، با $1666$ حرکت میتوان اعداد را برعکس کرد. برای هر $4$ عدد باید $2$ دَوَران انجام داد. بنابراین با $1666$ حرکت میتوانیم به هدفمان برسیم.
چرا با کمتر از این مقدار نمیتوانیم به هدفمان برسیم؟ هر دَوَران دقیقاً یک عدد را یک جایگاه جلوتر از جایگاه فعلیاش میبرد. در جایگشت اعداد $1$ تا $1666$ هر عدد باید به جایگاهی جلوتر از خود منتقل شود. بنابراین به حداقل $1666$ دَوَران نیاز داریم.
| ▸ سوال قبل |