آمار پرسش:
- پرسیده شده: 2019-04-18 04:22:39 -0600
- مشاهده شده: 352 بار
- بروز شده: 2019-08-22 17:32:46 -0600
پرسش‌های مشابه:
سنگ بازی توی یک جدول یک در n پایان پذیر است
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
جایگشت‌های علامت‌دار - مرحله دوم
یک جایگشت، یک ترتیب از اعداد ۲،۱،… و $n$ است. برای مثال ($3,1,4,2,5$) جایگشتی از اعداد ۱ تا ۵ است. یک جایگشت علامت‌دار از روی یک جایگشت عادی به این شکل به دست می‌آید که صفر یا چند عدد آن جایگشت را منفی میکنیم. برای مثال ($-3,1,-4,-2,5$) جایگشتی علامت‌دار است.
اگر $A=(a_1,a_2,…,a_n)$ یک جایگشت علامت‌دار باشد، دوران $(i,j)$ که در آن $1\leq i \leq j \leq n$ آن را به جایگشت علامت‌دار زیر تبدیل می‌کند:
$(a_1,a_2,…,a_{i-1},-a_j,-a_{j-1},…,-a_{i+1},-a_{i},a_{j+1},…,a_n)$
برای مثال با انجام متوالی دوران‌های $(1,2)$، $(2,3)$ و $(1,2)$ روی جایگشت علامت‌دار $(1,2,3)$ ، به ترتیب جایگشت‌های علامت‌دار زیر به‌دست می‌آیند:
$(1,2,3) \rightarrow (-2,-1,3) \rightarrow (-2,-3,1) \rightarrow (3,2,1)$
ثابت کنید دست کم $n-1$ دوران برای تبدیل $(a_1,a_2,…,a_n)$ به $(a_n,a_{n-1},…,a_1)$ لازم است.
2019-04-18 04:22:39 -0600
غزوو 1304 ● 7 ● 14 ● 24
نظرات
1 پاسخ
اقا من همین اول یک عذرخواهی بکنم وقتم کمه واسه همین خیلی خلاصه مینویسم
اول میایم میگیم از هر زوج دو تایی که که از n تا بگیریم حتما یکیشون یک بار بدون اون یکی اومده یعنی مثلا اگه ax و ay در نظر بگیریم غیر ممکنه تو هر i j که انتخاب میکنیم یا شامل هر دو باشه یا شامل هیچ کدوم حالا دلیلش
اول از همه باید بدونیم هر ai حتما زوج بار انتخاب شده چون علامتش میخوایم مثبت باشه حالا فرض کنید دو تا ax و ay همیشه با هم انتخاب شده بودن فرض کنید تو دنباله اصلی ax سمت چپ ay باشه بدیهیه که اگه همیشه با هم انتخاب شن و زوج بار انتخاب شن ترتیبشون به همون صورت میمونه و باز هم ax چپ ay میمونه ولی از اونجا که میخوایم دنباله رو برعکس کنیم باید ax سمت راست بره و با برهان فهمیدیم خلافش غیر ممکنه
حالا اثبات اینکه چرا با این شرایط باید حداقل n-1 بار انتخاب شه اثبات این خیلی سادس راحت در میاد ولی راهنمایی بخوام بکنم بهتون
با استقرا ی ساده و راحت اثبات میشه بازم
اگه کسی نتونست اثبات کنه این تیکه رو بگه اضافه میکنم
پینوشت : آقا بازم ببخشید کامل ننوشتم درگیر کنکورم این روزا سوالم جوابشو یکم با تاخیر گذاشتم که کسی خواست فکر کنه وقت باشه واسش
2019-08-22 17:30:08 -0600
مرشد 336 ● 3 ● 3 ● 12