اصل ناوردایی

واژه‌شناسی

فرهنگستان زبان فارسی، وردیدن از ریشه باستانی ورت (ورتیدن)، را به جای فعل to varry برگزیده است و از این فعل مشتقات وردایی(variance)،وردش(variation)، وردا(variant)، هم‌وردا(covariant)، هم وردایی(covariannce)، ناوردا(invariant)، ناوردایی(invariance)، پادوردا(contravariance) را برساخته است.

چگونگی استفاده از اصل ناوردایی

در این‌گونه مسائل معمولاً یک حالت اولیه (فضای ابتدایی) وجود دارد و عملی نیز تعریف شده که در هر گام انجام می‌شود و معمولاً یک حالت به عنوان هدف نهایی معرفی می‌شود و سؤال این است که: آیا می‌توان با تکرار این عمل به هدف نهایی رسید یا خیر؟ بنابراین مسائل این مقاله ۲ حالت دارند:
۱- مسائلی که رسیدن به حالت هدف در آن‌ها ممکن است:
این دسته از مسائل جالبتر هستند، در این مسائل معمولاً به دنبال یک تابع اکیداً صعودی یا اکیداً نزولی می‌گردیم. پس از یافتن این تابع تقریباً ۸۰٪ مسئله حل شده‌است و از اینجا به بعد معمولاً مسئله به ۲ روش حل می‌شود.
الف : از آنجا که تابع یکنواست، به حالت تکراری برنمی‌خوریم چون بایست در این صورت رشد تابع در مواقعی به صورت عکس ادامه یافته باشد. اگر تعداد حالتهای (فضای) مسئله محدود باشد چون در هر گام به یک حالت جدید می‌رسیم پس این عمل نمی‌تواند بینهایت بار انجام شود و بالاخره این عمل متوقف می‌شود و معمولاً توقف عمل معادل حل مسئله‌است.
ب : تابع یکنواست و قدر مطلق رشد (یا نزول) آن از مقدار e بیشتر است حالا اگر تابع مورد نظر یک کران بالا (یا پایین) داشته‌باشد در این صورت این عمل متوقف خواهد شد. ممکن است بپرسید مقدار e چرا لازم است: فرض کنید هدف ما عدد ۲ است و حالت ابتدا عدد ۱ است و در گام اول ۲/۱ در گام دوم ۱/۴ در گام سوم ۸/۱ و… به عدد ۱ اضاقه شود مشاهده می‌کنیم که همیشه می‌توان به عدد موجود عددی اضافه کرد و هیچ وقت هم این عدد به ۲ نمی‌رسیم. از این نکته به لزوم e پی می‌بریم.
۲- مسائلی که رسیدن به حالت هدف در آن‌ها ممکن نیست: در این مسادل معمولاً رابطهٔ ثابتی می‌یابیم که با هر عمل همچنان برقرار باقی می‌ماند. اگر در این رابطه برای حالت نهایی (حالت هدف) برقرار نباشد، به حالت نهایی نمی‌رسیم (به این روش استفاده از اصل همخوانی هم می‌گویند).
حال استفاده اصل ناوردایی را در عمل خواهیم دید:

مثال‌های حالت اول

مثال ۱: فرض کنید n یک عدد طبیعی فرد است. در ابتدا تمام اعداد ۱، ۲، ۳..... ، ۲n روی تخته سیاه نوشته شده‌اند. در هر مرحله a و b را از بین اعداد روی تخته سیاه پاک می‌کنیم و به جای آن‌ها عدد |a-b| را می‌نویسیم. در نهایت تنها یک عدد باقی خواهد ماند. ثابت کنید این عدد فرد است.
حل : فرض کنید S برابر مجموع اعدادی باشد که در هر مرحله روی تخته سیاه نوشته شده‌اند در ابتدا
 است که یک عدد فرد است. فرض کنید در یک مرحله ۲ عدد a و b را انتخاب کنیم. بدون کاسته شدن از کلیت مسئله می‌توانیم فرض کنیم a⇐b باشد در اینصورت a و b خط می‌خورند و به جای آن‌ها b-a قرار می‌گیرد که در نتیجه مقدار S به اندازهٔ ۲a کاهش می‌یابد بنابراین زوج یا فرد بودن S ثابت می‌ماند. در ابتدا S عددی فرد است بنابراین عددی که در نهایت باقی می‌ماند نیز فرد است.
مثال ۲ : یک دایره را به ۶ بخش تقسیم کرده‌ایم و در جهت خلاف حرکت عقربه‌های ساعت عددهای ۰، ۰، ۰، ۱، ۰، ۱ در این بخش‌ها نوشته‌ایم. شما می‌توانید در هر مرحله به دو عدد که در ۲ بخش مجاور قرار دارند بک واحد اضافه نمایید. آیا ممکن است به حالتی برسید که تمام اعداد نوشته شده با هم برابر باشند؟

 
حل : برای حل مسئله فرض می‌کنیم A مجموع اعداد بخش‌های اول و سوم و پنجم و B، مجموع اعداد بخش‌های دوم و چهارم و ششم باشد، روشن است A-B=۲ همیشه برقرار است. چون در هر گام به هر یک از عددهای A و B یک واحد اضافه می‌شود؛ بنابراین امکان ندارد به حالتی برسیم که شش عدد با هم مساوی باشند چون در آن حالت A-B برابر ۰ خواهد بود.

مثال‌های حالت دوم

مثال ۳ : در یک پارلمان هر نماینده حداکثر ۳ مخالف دارد. ثابت کنید این نمایندگان را می‌توان در ۲ خانه قرار داد به‌طوری‌که هر نماینده در خانهٔ خود حداکثر ۱ مخالف داشته‌باشد.
حل : در ابتدا نمایندگان را به صورت دلخواه در ۲ خانه قرار می‌دهیم. فرض کنید H مجموع تعداد مخالفان افراد در خانه‌های خود باشند.
فرض کنید A در خانهٔ خود بیش از ۱ مخالف داشته باشد، بنابراین A حداکثر یک مخالف در خانهٔ دیگر دارد و می‌تواند به خانهٔ دیگر برود. اگر خانهٔ A عوض شود مقدار H کم خواهد شد (مقدار H حداقل یک واحد کمتر می‌شود). از آنجا که H یک عدد طبیعی و محدود است این عمل نمی‌تواند همیشه ادامه یابد و بالأخره متوقف خواهد شد. یعنی بعد از چند مرحله دیگر کسی در خانهٔ خود بیش از یک دشمن ندارد که به خانهٔ دیگر برود.
توجه :(در این از یک ایدهٔ جدید استفاده نمودیم. ما یک تابع اکیداً نزولی یافتیم که در هر مرحله مقدار آن کاهش می‌یابد و همیشه مقدار آن عددی صحیح و غیر منفی است از آن جا که دنباله نامتناهی اکیداً نزولی از اعداد صحیح و غیر منفی وجود ندارد، این دنباله بایستی یک دنبالهٔ متناهی باشد)
مثال ۴:
هر یک از اعداد برابر ۱ یا -۱ هستند و داریم:
ثابت کنید ۴ n را عاد می‌کند.
 حل :این یک مسئله در نظریهُ اعداد است برای حل مسئله باز هم از اصل عدم همخوانی استفاده کنیم. یکی از aᵢها را تغییر می‌دهیم و تغییرات را بررسی می‌کنیم می‌بینیم که علامت ۴ جملهُ متوالی که شامل آن است تغییر خواهد کرد. اگر هر ۴ جمله قبلاً هم علامت بودند، به اندازهُ ±۸ تغییر می‌کند اگر ۲ تا مثبت و ۲ تا منفی بودند، تغییری نمی‌کند و اگر ۳ تا هم علامت بودند و یکی از علامت مخالف، به اندازهُ ±۴ تغییر می‌کند. مشاهده می‌کنیم که باقی‌مانده S در تقسیم بر ۴ نیز ثابت باقی می‌ماند. حالا تغییرات را طوری انجام می‌دهیم که تمام aᵢها برابر ۱ شود مشخص است که در این حالت S=n خواهد شد ولی باقی‌ماندهُ آن به ۴ تغییر نکرده‌است یعنی باقی‌ماندهُ بر ۴ برابر ۰ است.