المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:کاربردهای هم‌خوانی

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

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


وارونگی

یک جایگشت از اعداد $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$ خواهد ماند و از آن‌جایی که هر دو عدد ۱۳۹۵ و ۲۰۱۶ بر ۳ بخش‌پذیر هستند، امکان این کار وجود ندارد.


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

—-

منابع و مراجع

  1. D.Fomin, I.Itenberg, S.Genkin (1996), Mathematical circles (Russian Experience), Mathematical World
  2. Arthur Engel (1998), Problem Solving Strategies, New York, Springer

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

نظرات

نظر خود را وارد کنید. دستورات ویکی مجاز است:
‎ 47 +5 = ? ‎
 

ابزار صفحه