====== هم‌خوانی ======

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


----

===== تعریف =====

با یک مثال شروع می‌کنیم. فرض کنید در ابتدا عدد ۸ را داریم. در هر مرحله می‌توانیم یکی از اعداد $12, 33$ را به عددمان اضافه کنیم. می‌خواهیم ببینیم آیا می‌توان با تعدادی مرحله به عدد ۱۳۹۵ رسید یا خیر. پاسخ ساده است. در ابتدا عددمان به صورت $3k+2$ است. در هر مرحله یک عدد مضرب ۳ به آن اضافه می‌شود. پس هم‌واره به صورت $3k+2$ می‌ماند؛ در حالی که عدد ۱۳۹۵ (عدد انتهایی) به صورت $3k+2$ نیست. پس نمی‌توان به عدد ۱۳۹۵ رسید.

به طور کلی فرض کنید در ابتدا در وضعیت $S$ با ویژگی $P$ هستیم و در هر مرحله از وضعیتی به وضعیت دیگر برویم؛ طوری که ویژگی $P$ حفظ شود. **اصل هم‌خوانی** می‌گوید به هیچ وضعیتی مانند $F$ نمی‌توانیم برسیم که ویژگی $P$ را نداشته باشد. در مثال بالا وضعیت $S$ متناظر عدد ۸، وضعیت $F$ متناظر عدد ۱۳۹۵ و ویژگی $P$ همان به صورت $3k+2$ بودن است.


**مثال**:
در ابتدا عدد $7^{2016}$ را داریم. در هر مرحله اگر عدد $d$ با رقم یکان $a$ را داشته باشیم، آن را به $\frac{d-a}{10}+a$ تبدیل می‌کنیم (در واقع رقم یکان آن را از عدد کنده و با عدد جمع می‌کنیم). آن‌قدر این کار را انجام دهید تا به یک عدد ۱۰-رقمی برسید. ثابت کنید در این عدد دو رقم برابر وجود دارد.

<پاسخ>
برهان خلف می‌زنیم. فرض کنید عدد نهایی دو رقم برابر نداشته باشد؛ در این صورت از هر یک از ارقام $0, 1, ..., 9$ دقیقن یکی دارد. پس بر ۹ بخش‌پذیر است. از طرفی در حین مراحل باقی‌مانده عدد در پیمانه‌ی ۹ ثابت می‌ماند. از آن‌جایی که عدد ابتدایی بر ۹ بخش‌پذیر نیست، طبق اصل هم‌خوانی نمی‌توان به عددی رسید که بر ۹ بخش‌پذیر است و به تناقض می‌رسیم. 

</پاسخ>

----

===== چند مثال =====
**مثال**:
در ابتدا یک کارت داریم که زوج مرتب $(5, 19)$ روی آن نوشته شده است. یک دست‌گاه داریم که در هر مرحله می‌تواند یکی از کارهای زیر را انجام دهد:
  * با دادن کارت $(a, b)$ به آن، یک کارت $(a+1, b+1)$ تولید کند.
  * با دادن کارت $(a, b)$ به آن که $a, b$ زوج هستند، یک کارت $(\frac{a}{2}, \frac{b}{2})$ تولید کند.
  * با دادن کارت‌های $(a, b), (b, c)$ به آن، کارت $(a, c)$ را تولید کند.
توجه کنید کارت‌هایی که به دست‌گاه می‌دهیم از بین نمی‌روند و دوباره به ما برگردانده می‌شوند. آیا می‌توان با تعداد مرحله کارت $(1, 100)$ را ساخت؟
<پاسخ>
اختلاف دو عدد زوج مرتب اولیه برابر با $19-5=14$ است و بر ۷ بخش‌پذیر است. در حین مراحل نیز تنها زوج مرتب‌هایی ساخته می‌شوند که اختلاف دو عدد آن‌ها بر ۷ بخش‌پذیر است. پس نمی‌توان به زوج مرتب $(1, 100)$ رسید.

</پاسخ>


**مثال**:
چندجمله‌ای درجه دوم $f(x)$ در هر مرحله می‌تواند با یکی از دو چندجمله‌ای
$x^2f(1 + \frac{1}{x})$
یا
$(x-1)^2f(\frac{1}{x-1})$
جای‌گزین شود. آیا می‌توان با تعدادی مرحله از چندجمله‌ای $x^2+4x+3$ به چندجمله‌ای $x^2+10x+9$ رسید؟ (المپیاد ریاضی روسیه - ۱۹۹۳)
<راهنمایی>
به مقدار $\Delta$ توجه کنید.

</راهنمایی>
<پاسخ>

خیر؛
فرض کنید در یک مرحله چندجمله‌ای $ax^2+bx+c$ را داشته باشیم.
  * با انجام گام نوع اول به چندجمله‌ای $$x^2\big(a(1+\frac{1}{x})^2+b(1+\frac{1}{x})+c \big) = (a+b+c)x^2+(b+2a)x+a$$ می‌رسیم که مقدار $\Delta$ در آن برابر با $$(b+2a)^2-4a(a+b+c) = b^2-4ac$$ است.
  * با انجام گام نوع دوم به چندجمله‌ای $$(x-1)^2\big(a(\frac{1}{x-1})^2+b(\frac{1}{x-1})+c \big) = cx^2+(b-2c)x+(a-b+c)$$ می‌رسیم که مقدار $\Delta$ در آن برابر با $$(b-2c)^2-4c(a-b+c) = b^2-4ac$$ است.

پس در هر صورت در هر مرحله مقدار $\Delta$ ثابت می‌ماند. در ابتدا مقدار دلتا برابر ۴ است و در انتها قرار است برابر با ۶۴ باشد که امکان ندارد.
</پاسخ>
----
===== مسائل نمونه از المپیادهای کامپیوتر ایران =====

  * [[سوالات المپیاد: مرحله‌ی اول: دوره‌ی ۲۵: سوال ۱۴|سوال ۱۴ مرحله اول دوره‌ی ۲۵]]
  * [[سوالات_المپیاد/مرحله‌ی_اول/دوره‌ی_۲۵/سوالات_۲۴_و_۲۵_و_۲۶|سوال ۲۴ مرحله اول دوره‌ی ۲۵]]

----
===== منابع و مراجع =====
  - [[https://en.wikipedia.org/wiki/Invariant_(mathematics)|ناوردایی، ویکی‌پدیا]]
  - D.Fomin, I.Itenberg, S.Genkin (1996), Mathematical circles (Russian Experience), Mathematical World
  - Arthur Engel (1998), Problem Solving Strategies, New York, Springer

----

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

~~DISCUSSION~~