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

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

یک جایگشت از اعداد $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)$ رسید؟

• سوال ۴ بخش تشریحی مرحله دوم دوره‌ی ۲۱
• سوال ۱ آزمون ترکیبیات دوره‌ی تابستانه‌ی ۱۳۹۴

—-

1. ناوردایی، ویکی‌پدیا
2. وارونگی، ویکی‌پدیا
3. D.Fomin, I.Itenberg, S.Genkin (1996), Mathematical circles (Russian Experience), Mathematical World
4. Arthur Engel (1998), Problem Solving Strategies, New York, Springer

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