يك سوال تركيبيات زيبا

[Amir hasan]

يك دسته كارت ٢n+١تايي شامل يك تصوير و دو كارت به شماره يk،به ازاي هر عدد طبيعيkكهn>_ k،مي باشد.فرض كنيد كه ٢n+1كارت را به كونه اي در يك رديف قرار داده ايم كه اولاً كارت تصوير در وسط قرار دارد و ثانياً بين هر دو كارت با شماره ي برابرk،دقيقاًk-1كارت قرار داشته باشد.همه ي مقادير10>_n>_ ١ را بيابيد كه براي انها چنين ارايشي در يك رديف براي دسته كارت2n+1تايي ممكن است.به ازاي چه مقاديري ازn چنين ترتيبي ممكن نيست؟

 

[comlover]

پاسخ : يك سوال تركيبيات زيبا

این سئوال خیلی آشناست مطمئنم قبلا دیده بودمش از کدوم کتابه؟

 

[حالا هرکی]

پاسخ : يك سوال تركيبيات زيبا

در ابتدا تعریف میکنیم

فاصله بین i,j باشه قصد داریم

رو به پیمانه ی 2

کنیم .

از یک طرف میدانیم که قرار گرفتن i, j به ازای هر i,j از این حالت ها خارج نیست

1-

2-

3-

در هر حالت 4 نوع f داریم (i1,j1)+,(i1,j2)+,(i2,j1)+,(i2,j2) =g(i1,12,j1,j2) با اندکی محاسبات طبق فرض مسئله که فاصله بین i,i نیز i است به دست می آوریم که به

ازای هر

نیز

به پیمانه ی 2 برابر صفر است خب از طرفی دیگر سیگمای فواصل برابر

به پیمانه ی 2 به ازای هر i بین 1 تا 2n .

پس داریم

پس فقط 4k+1 ,4k ها میتوانند n باشند و 4k+3 ها و 4k+2 ها نمیتواند

فعلا نتونستماثبات الگوریتمی برای 4k+1,4k بدم اگه چیزی به ذهنم رسید مینویسم .