سوال شب چهاردهم

سوال امشبم بخاطر درخواست های زیاد(!) گذاشتیم

 

فرض کنید جایگشت <a₁ , a₂ , ... , a_n> جایگشتی از اعداد 1 تا n باشد. به جایگشتی علامت دار میگوییم اگر هر عدد مثبت بین 1 تا n دقیقن یکبار به صورت منفی یا مثبت آمده باشد. مثلن <1 , 3 , -2> جایگشتی علامتدار است اما <2,-1,1> نیست.

 

حاصل دوران (i,j) که i<=j روی یک جایگشت علامتدار <a₁ , a₂ , ... ,a_i, a_i+1,...,a_j, ... , a_n> برابر با جایگشت علامتدار زیر است

<a₁ , a₂ , ... ,-a_j,-a_j-1,...,-a_i, ... , a_n>

 

ثابت کنید برای تبدیل جایگشت علامتدار <a₁ , a₂ , ... , a_n> به <a_n , a_n-1 , ... , a₁> به حداقل n-1 دوران نیاز داریم.

 

مهدی جعفری

 

(همچنین یک گراف G داریم و در آن شایان پردیس به راس F میرود و سلام کرده و آب میخورد.)