اصل ناوردایی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

تعریف[ویرایش]

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

در اینگونه مسائل معمولاً یک حالت اولیه (فضای ابتدایی) وجود دارد و عملی نیز تعریف شده که در هر گام انجام می‌شود و معمولاً یک حالت به عنوان هدف نهایی معرفی می‌شود و سوال این است که: آیا می‌توان با تکرار این عمل به هدف نهایی رسید یا خیر؟ بنابراین مسائل این مقاله ۲ حالت دارند:

۱- مسائلی که رسیدن به حالت هدف در آنها ممکن است:
این دسته از مسائل جالبتر هستند، در این مسائل معمولاً به دنبال یک تابع اکیداً صعودی یا اکیداً نزولی می گردیم. پس از یافتن این تابع تقریباً ۸۰٪ مسئله حل شده‌است و از اینجا به بعد معمولاً مسأله به ۲ روش حل می‌شود.

الف : از آنجا که تابع یکنواست [۱]، به حالت تکراری برنمی خوریم چون بایست در این صورت رشد تابع در مواقعی به صورت عکس ادامه یافته باشد. اگر تعداد حالتهای(فضای) مسئله محدود باشد چون در هر گام به یک حالت جدید می‌رسیم پس این عمل نمی‌تواند بینهایت بار انجام شود و بالاخره این عمل متوقف می‌شود و معمولاً توقف عمل معادل حل مسئله‌است.

ب : تابع یکنواست و قدر مطلق رشد (یا نزول) آن از مقدار e بیشتر است حالا اگر تابع مورد نظر یک کران بالا(یا پایین) داشته‌باشد در این صورت این عمل متوقف خواهد شد. ممکن است بپرسید مقدار e چرا لازم است: فرض کنید هدف ما عدد ۲ است و حالت ابتدا عدد ۱ است و در گام اول ۲/۱ در گام دوم ۱/۴ در گام سوم ۸/۱ و..... به عدد ۱ اضاقه شود مشاهده می‌کنیم که همیشه می‌توان به عدد موجود عددی اضافه کرد و هیچ وقت هم این عدد به ۲ نمی‌رسیم. از این نکته به لزوم e پی می‌بریم.

۲- مسائلی که رسیدن به حالت هدف در آنها ممکن نیست: در این مسادل معمولاً رابطهٔ ثابتی می‌یابیم که با هر عمل همچنان برقرار باقی می‌ماند. اگر در این رابطه برای حالت نهایی (حالت هدف) برقرار نباشد، به حالت نهایی نمی‌رسیم (به این روش استفاده از اصل همخوانی هم می‌گویند). حال استفاده اصل ناوردایی را در عمل خواهیم دید:

مثال‌های حالت اول[ویرایش]

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

حل : فرض کنید S برابر مجموع اعدادی باشد که در هر مرحله روی تخته سیاه نوشته شده‌اند در ابتدا \frac{2n(2n+1)}{2} است که یک عدد فرد است. فرض کنید در یک مرحله ۲ عدد 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 یک عدد طبیعی و محدود است این عمل نمی‌تواند همیشه ادامه یابد و بالأخره متوقف خواهد شد. یعنی بعد از چند مرحله دیگر کسی در خانهٔ خود بیش از یک دشمن ندارد که به خانهٔ دیگر برود.

توجه :( در این از یک ایدهٔ جدید استفاده نمودیم. ما یک تابع اکیداً نزولی یافتیم که در هر مرحله مقدار آن کاهش می‌یابد و همیشه مقدار آن عددی صحیح و غیر منفی است از آن جا که دنباله نامتناهی اکیداً نزولی از اعداد صحیح و غیر منفی وجود ندارد، این دنباله بایستی یک دنبالهٔ متناهی باشد.)

مثال ۴ : هر یک از اعداد برابر ۱ یا -۱ هستند و داریم:

S=a_{1}a_{2}a_{3}a_{4}+a_{2}a_{3}a_{4}a_{5}+...+a_{n}a_{1}a_{2}a_{3}=0


ثابت کنید ۴ n را عاد می‌کند.

حل :این یک مسئله در نظریهُ اعداد است برای حل مسئله باز هم از اصل عدم همخوانی استفاده کنیم. یکی از aiها را تغییر می‌دهیم و تغییرات را بررسی می‌کنیم می‌بینیم که علامت ۴ جملهُ متوالی که شامل آن است تغییر خواهد کرد. اگر هر ۴ جمله قبلاً هم علامت بودند، به اندازهُ ±۸ تغییر می‌کند اگر ۲ تا مثبت و ۲ تا منفی بودند، تغییری نمی‌کند و اگر ۳ تا هم علامت بودند و یکی از علامت مخالف، به اندازهُ ±۴ تغییر می‌کند. مشاهده می‌کنیم که باقی‌مانده S در تقسیم بر ۴ نیز ثابت باقی می‌ماند. حالا تغییرات را طوری انجام می‌دهیم که تمام aiها برابر ۱ شود مشخص است که در این حالت S=n خواهد شد ولی باقی‌ماندهُ آن به ۴ تغییر نکرده‌است یعنی باقی‌ماندهُ بر ۴ برابر ۰ است.

پیوندهای مرتبط[ویرایش]

پانویس[ویرایش]

  1. ص۹ استراتژی حل مسئله

منابع[ویرایش]

  • انگل، آرتور. استراتژی‌های حل مسئله، چاپ دوم . تهران: مبتکران ، ۱۳۸۴ . شابک ۵-۴۱۴-۳۹۵-۹۶۴
  • http://mathworld.wolfram.com

کاربردها[ویرایش]