====== کاربردهای هم‌خوانی ======

در این صفحه با برخی از کاربردهای معروف **اصل هم‌خوانی** آشنا می‌شوید.


----

===== وارونگی =====

یک جایگشت از اعداد $1, 2, \ldots, n$ در نظر بگیرید. هر گاه دو عنصر داشته باشیم که عنصر بزرگ‌تر قبل از عنصر کوچک‌تر آمده باشد (نه لزومن چسبیده به آن)، یک **وارونگی** (نابه‌جایی) رخ داده است. برای مثال جایگشت $3, 1, 4, 2$ شامل ۳ وارونگی است:
  * اعداد ۱ و ۳
  * اعداد ۲ و ۳
  * اعداد ۲ و ۴
وارونگی مفهوم مهمی است که روی جایگشت‌ها تعریف می‌شود و مسائل متنوعی از آن مطرح می‌شود.

**مثال**:
فرض کنید در ابتدا رشته‌ی $01$ را داریم. در هر مرحله می‌توان به جایی دل‌خواه از رشته، زیررشته‌ی $11$ یا زیررشته‌ی $00$ را اضافه کرد و یا از جایی دل‌خواه از رشته، زیررشته‌ی $11$ یا زیررشته‌ی $00$ را حذف کرد. آیا می‌توان با تعدادی گام به رشته‌ی $10$ رسید؟

<پاسخ>
خیر؛
هر گاه یک رقم ۱ قبل از یک رقم ۰ آمده باشد (نه لزومن چسبیده به آن)، گوییم یک وارونگی رخ داده است. در ابتدا تعداد وارونگی‌ها ۰ است و در انتها قرار است برابر با ۱ باشد. از طرفی در هر مرحله تعداد وارونگی‌ها زوج تا تغییر می‌کند؛ پس چنین کاری ممکن نیست.

</پاسخ>

**مثال**:
فرض کنید در ابتدا جایگشت $<1, 2, ..., 10>$ را داریم و می‌خواهیم آن را به جایگشت $<10, 9, ..., 1>$ تبدیل کنیم. در هر مرحله می‌توان جای دو عنصر متوالی را عوض کرد. آیا می‌توان پس از دقیقن ۲۰۱۶ مرحله به هدف‌مان برسیم؟
<پاسخ>
در ابتدا تعداد وارونگی‌های جایگشت ۰ تاست و در انتها قرار است برابر ۴۵ باشد. از طرفی در هر مرحله تعداد وارونگی‌ها یا یکی زیاد می‌شود و یا یکی کم می‌شود. پس به صورت یک در میان در مراحل زوج و فرد وارونگی خواهیم داشت و برای رسیدن به هدف نیاز به تعداد فردی مرحله است؛ پس چنین کاری با دقیقن ۲۰۱۶ مرحله ممکن نیست.
</پاسخ>

----

===== نظریه اعداد =====
در بسیاری از مسائل اصل هم‌خوانی با توجه کردن به عناصر نظریه اعدادی (مانند باقی‌مانده به یک پیمانه‌ی خاص، ب.م.م و ...) می‌توان مسئله را حل کرد.

**مثال**: در ابتدا در نقطه‌ی $(1, 1)$ مبدأ مختصات هستیم. در هر مرحله می‌توان از نقطه‌ی $(x, y)$ به یکی از نقاط زیر رفت:
  * $(x, 2y)$
  * $(2x, y)$
  * $(x-y, y)$ به شرط آن که $x \ge y$ باشد
  * $(x, y-x)$ به شرط آن که $x \le y$ باشد
آیا می‌توان به نقطه‌ی $(1395, 2016)$ رسید؟

<پاسخ>
ب.م.م $x, y$ در هر مرحله یا ثابت می‌ماند یا دو برابر می‌شود. از آن‌جایی که ب.م.م در ابتدا ۱ است، هم‌واره به صورت $2^k$ خواهد ماند و از آن‌جایی که هر دو عدد ۱۳۹۵ و ۲۰۱۶ بر ۳ بخش‌پذیر هستند، امکان این کار وجود ندارد.

</پاسخ>

----
===== مسائل نمونه از المپیادهای کامپیوتر ایران =====

  * [[سوالات_المپیاد/مرحله‌ی_دوم/دوره‌ی_۲۱/سوال_چهار|سوال ۴ بخش تشریحی مرحله دوم دوره‌ی ۲۱]]
  * سوال ۱ آزمون ترکیبیات دوره‌ی تابستانه‌ی ۱۳۹۴
----
===== منابع و مراجع =====
  - [[https://en.wikipedia.org/wiki/Invariant_(mathematics)|ناوردایی، ویکی‌پدیا]]
  - [[https://en.wikipedia.org/wiki/Inversion_%28discrete_mathematics%29|وارونگی، ویکی‌پدیا]]
  - D.Fomin, I.Itenberg, S.Genkin (1996), Mathematical circles (Russian Experience), Mathematical World
  - Arthur Engel (1998), Problem Solving Strategies, New York, Springer

----

خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و ...) در این صفحه، به ما اطلاع دهید:

~~DISCUSSION~~