هم‌خوانی
در این صفحه با اصل هم‌خوانی آشنا می‌شوید. هم‌خوانی یکی از مهم‌ترین و کلاسیک‌ترین انواع ناوردایی و یک ایده‌ی ساده برای حل مسائل ترکیبیات است.
تعریف
با یک مثال شروع می‌کنیم. فرض کنید در ابتدا عدد ۸ را داریم. در هر مرحله می‌توانیم یکی از اعداد $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$ ثابت می‌ماند. در ابتدا مقدار دلتا برابر ۴ است و در انتها قرار است برابر با ۶۴ باشد که امکان ندارد.
مسائل نمونه از المپیادهای کامپیوتر ایران
منابع و مراجع
- D.Fomin, I.Itenberg, S.Genkin (1996), Mathematical circles (Russian Experience), Mathematical World
- Arthur Engel (1998), Problem Solving Strategies, New York, Springer
خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
نظرات