چرخش (۱۸ نمره)

عمل چرخش روی جایگشت $P=\langle P_1,P_2,\ldots,P_{1402}\rangle$ از اعداد $1$ تا $1402$ به این صورت تعریف می‌شود که یک عدد طبیعی $i$ را انتخاب می‌کنیم (که $1\le i\le 1402$) و جایگشت $P$ را از جایگاه $i$ام می‌شکنیم تا دو زیرجایگشت $A=\langle P_1,P_2,\ldots,P_i\rangle$ و $B=\langle P_{i+1},P_{i+2},\ldots,P_{1402}\rangle$ ایجاد شود. سپس جایگشت $P$ را با یکی از جایگشت‌های زیر جایگزین می‌کنیم:

• $B.A=\langle P_{i+1},P_{i+2},\ldots,P_{1402},P_1,P_2,\ldots,P_i\rangle$
• $A.\bar{B}=\langle P_1,P_2,\ldots,P_i,P_{1402},P_{1401},\ldots,P_{i+1}\rangle$
• $\bar{A}.B=\langle P_i,P_{i-1},\ldots,P_1,P_{i+1},P_{i+2},\ldots,P_{1402}\rangle$

جایگشت آغازینی از اعداد $1$ تا $1402$ داده شده است. هدف، منظم کردن جایگشت است؛ به این معنی که با استفاده از تعدادی عمل چرخش به یکی از جایگشت‌های $\langle 1,2,\ldots,1401,1402\rangle$ یا $\langle 1402,1401,\ldots,2,1\rangle$ برسیم.

• الف) نشان دهید هر جایگشت آغازینی را می‌توان با حداکثر $2800$ بار استفاده از عمل چرخش، منظم کرد. (۹ نمره)

• ب) نشان دهید جایگشت آغازینی وجود دارد که نمی‌توان آن را با حداکثر $1400$ بار استفاده از عمل چرخش منظم کرد. (۹ نمره)