جابجایی کتاب ها

[M_Sharifi]

سوال هشتم (از amir.ekhlasi):
[FONT=&quot]- [FONT=&quot] n میز مختلف داریم که در آنها کتابهای متفاوتی قرار داده شده است. محمد در هر مرحله می تواند جای دو کتاب را عوض کند. ما به او اجازه می دهیم که بعضی از حرکات را انجام دهد و بعضی دیگر را انجام ندهد. یعنی به او مثلا اجازه می دهیم که می تواند جای کتابهای میز اول و دوم را عوض کند ولی جای کتابهای میز اول و سوم را عوض نکند. (یا حرکات دیگر) فرض کنید [/FONT][FONT=&quot]X مجموعه جایگشتهایی باشد که محمد[/FONT][FONT=&quot] با استفاده از حرکات مجاز می تواند بسازد. (محمد می تواند به هر تعداد که بخواهد از حرکات مجاز پشت سر هم استفاده کند.) فرض کنید تعداد اعضای X[/FONT][FONT=&quot] برابر m باشد و [/FONT][FONT=&quot]p عدد اولی باشد که

[/FONT][FONT=&quot]. ثابت کنید دنباله ای متناهی از حرکات مجاز وجود دارد[/FONT][FONT=&quot] که اگر یک بار آن را انجام دهیم به حالت اولیه نمی رسیم. ولی اگر p[/FONT][FONT=&quot] بار آن را انجام دهیم به حالت اولیه می رسیم.[/FONT][/FONT]

 

[mojtabaaa1373]

پاسخ : جابجایی کتاب ها

دو تا سوال یکی این که کتابها متمایزند دوم این که آیا جابه جایی ها دوطرفه است(یعنی اجزه ی جا به جایی میز 1 به دو مساوی است با اجازه ی 2 به 1؟؟؟

 

[mojtabaaa1373]

پاسخ : جابجایی کتاب ها

پاسخ سوال دوم رو گرفتم اگه گرافی رو که راساش میز و یال های جهت دارش اجازه ها باشند رو در نظر بگیریم اون وقت یه دور رو که یه یالش حذف شده رو در نظر بگیریم امکان نداره به حالت اولیه برگردیمو

 

[mojtabaaa1373]

پاسخ : جابجایی کتاب ها

حالا اگه کتاب ها متمایز باشند و گرافی رو که در بالا ساختیمو در نظر بگیرم گراف از یه سری مولفه ی همبندی تشکیل میشه که m از ضرب حالات اونها به دست میاد بنابراین یکی از مولفه ها باید تعداد حالاتش توسط p عاد شه
اگر تعداد رووس مولفه t تا باشه و تعداد کتبش r تا تعداد حالات میشه t^rبنابر این p عاملی از t میشه
حالا حرکاتمون رو این جوری تعریف میکنیم جای کتابهای میز 1 را با کتابهای میز 2 کتابهای میز 2 را باکتابهای میز 3 و... و کتابهای میزt را با کتابهای میز 1 عوض کن.