یه سوال: با تغییر کلید آیا لامپ هاجداگانه تغییر وضعیت می دن یا مثلا وقتی کلید پایینه هر دو لامپ باید روش باشه؟
2015-03-12 11:09:12 -0500 سی پلاس پلاسآمار پرسش:
- پرسیده شده: 2015-03-12 10:29:19 -0500
- مشاهده شده: 662 بار
- بروز شده: 2015-04-11 10:42:27 -0500
پرسش‌های مشابه:
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
روشن کردن چراغ های خانه به طوری که هر اتاق چراغ خاموش و روشن داشته باشد(بالا خره حل شد!)
در یک خانه تعداد زوجی لامپ و تعدادی اتاق وجود دارد در هر اتاق حداقل 3 لامپ وجود دارد و هر لامپ به دقیقا 1 کلید متصل است و در ضمن هر کلید به دقیقا 2 لامپ وصل است ثابت کنید با شروع از هر وضعیت اولیه لامپ ها می توان به وضعیتی از لامپ ها رسید که هر اتاق هم لامپ روشن داشته باشد و هم لامپ خاموش.
2015-03-12 10:29:19 -0500
عطا 1110 ● 7 ● 12 ● 29
نظرات
3 پاسخ
اگر لامپ های یک اتاق همه روشن باشند وضعیت این اتاق 1 است و اگر همه ی لامپ های یک اتاق خاموش باشند وضعیت این اتاق 0 است و در غیر اینصورت وضعیت اتاق 2 است
حال یک اتاق 1(0) را درنظر می گیریم و یکی از کلید های متصل به لامپ های این اتاق رو می زنیم اگر که این کلید دوتا لامپ در این اتاق رو تغییر داد تعداد اتاق های 2 افزایش داشته است اگر که این کلید به اتاق دیگری وصل بود و این اتاق در ابتدا در وضعیت 2 نبود بازهم تعداد اتاق های 2 افزایش یافته است در غیر اینصورت این اتاق جدید از 2 به وضعیت 1 یا 0 رفته است کلیدی به جز کلیدیی که تا به الان زده شده و به این اتاق متصل است رو می زنیم این اتاق 2 می شود و اگر دوباره یک اتاق دیگر از 2 به 1 یا 0 تبدیل شد به سراغ این اتاق می ریم و کارهای روی اتاق قبلی رو روی این هم انجام می دیم این کارها رو تا جایی انجام می دهیم که به اولین اتاق تکرار برسیم قبل از آخرین حرکت این اتاق 2 بوده است و در مرحله ی قبل از این که این اتاق 2 شود فرض کنیم که 1 بوده است الان دو حالت پیش میاد
حالت ا:این اتاق بعد از آخرین حرکت 1 شود:پس یا اتاق قبلی تکراری بوده است یا یک لامپ به دو کلید متصل است که هر دو تناقض اند
حالت2:این اتاق بعد از آخرین حرکت 0 شود:پس دو لامپ در این اتاق تغییر وضعیت داده اند و این یعنی این که یک کلید به 3 لامپ وصل بوده که یعنی تناقض
پس هیچ وقت به یه اتاق تکرار نمی رسیم و این یعنی بازهم اتاق های 2 حداقل 1 واحد افزایش یافته و چون تعداد اتاق ها محدود است این افزایش ها جایی تمام می شوند و آن جا جایی است که همه 2 شده اند و حکم مسئله برقرار شده است
2015-04-11 10:40:14 -0500
عطا 1110 ● 7 ● 12 ● 29
نظرات
اتاقی که هم لامپ روشن داشته باشد و هم لامپ خاموش «واجد شرایط» می نامیم.
کلید ها را k1, k2, ..., kp می نامیم.(kp یعنی کلید آخر.)
اتاق ها را r1, r2, ..., rn می نامیم.
با استقرا روی تعداد اتاق ها اثبات می کنیم(n یعنی تعداد اتاق ها).
پایه که برای n=1 درسته.
حالا فرض می کنیم برای n-1 درسته.
ثابت می کنیم برای n درسته.
در ابتدا اتاق rn را کنار گذاشته و بقیه ی اتاق ها رو طبق فرض استقرا واجد شرایط می کنیم.
حالا اگه اتاق rn واجد شرایط بود که هیچ وگرنه به کلید ها رجوع می کنیم.
فرض می کنیم که کلید های kp و kp-1 به اتاق rn وصل هستند.
کلید kp رو تغییر نمی دیم ولی بقیه کلید ها رو تغییر وضعیت می دیم(همه ی اونها رو).
حالا می دونیم اتاق rn واجد شرایط هست. چون در بقیه ی اتاق ها لامپهای روشن، خاموش شدن و لامپ های خاموش، روشن شدن؛ اونها هم واجد شرایط هستن.
پس می تونیم همه ی اتاق ها رو واجد شرایط کنیم و تمام.■
2015-03-12 11:26:38 -0500
سی پلاس پلاس 439 ● 3 ● 4 ● 12
نظرات
غلطه چون ممکنه یه اتاق 3 تا لامپ داشته باشه و 1 لامپ از این اتاق به kp وصل باشه و وضعیتش با اون دوتای دیگه فرق داشته باشه(مثلا این روش و اون دوتا خاموش) و زمانی که ما همه ی کلید ها به جز kp رو می زنیم این اتاق دیگه واجد شرایط نیست
2015-03-13 00:02:30 -0500 عطاخوب اگه وضعیتش فرق داشته باشه که اونوقط همه ی اتاق ها واجد شرایط هستن که به این هم توی جواب اشاره شده.
2015-03-13 03:37:33 -0500 سی پلاس پلاساتاقی که گفتم اتاق rn نیست. یعنی kp بین دوتا اتاقه که یکی rn و اون یکی اتاقی که الان گفتم
2015-03-13 05:54:54 -0500 عطاحرف شما درسته @عطا بله به اینجاش فکر نکرده بودم. پس جوابم غلطه ، عذر میخوام از همه. اگر جواب درست رو پیدا کنم ،پستم رو ویرایش می کنم. عذر میخوام.
2015-03-13 09:17:44 -0500 سی پلاس پلاسبا استقرا قوی روی تعداد اتاق ها سول حل میشه !! یه اتاق رو بزارید کنار و بقیه رو درست کنید بعد برید سراغ اتاق آخر . یکی از لامپ هاش رو تغییر وضعیت بدین بعد ممکنه یه اتاق دیگه خراب شه. بعد یکی از لامپ های اون اتاق خرابه جدید رو تغییر بدید و بعد ممکنه یه اتاق دیگه خراب شه. حالا ثابت کنید این کار متوقف میشه !!
2015-03-13 12:37:54 -0500
غلیظ 117 ● 5 ● 8 ● 12
نظرات
استقرات غلته حتی این که یه اتاق رو بزاری کنار یه لامپی باهاش حذف میشه بعد اون لامپه که حذف بشه اون کلیدی که بهش وصله دیگه چون یه لامپش حذف شده دیگه به دو تا لامپ وصل نیست و به یک لامپ وصله پس توی کاهشی که دادی دیگه شرایطه مسئله برقرار نیست :)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
2015-03-13 13:25:55 -0500 حمیدرضاهوقتی گفته میشه یه اتاق حذف میشه به این معنی نیست که میایم اون اتاق رو از ریشه و بن خراب می کنیم. یعنی کلید هایی که برای درست کردن لامپ های اتاق های دیگه استفاده میکنیم ، تاثیرش رو اتاق کنار گذاشته برامون مهم نیست و میگوییم اتاق کنار گذاشته شده پس از مرتب کردن بقیه اتاق ها قابل مرتب شدن هستش.
2015-03-14 14:29:17 -0500 غلیظ