يك روبات از يك رأس دلخواه روي صفحه شطرنجي حركت كرده و هر بار يك واحد به يكي از جهت‌هاي اصلي روي اضلاع صفحه شطرنجي حركت مي‌كند. اين روبات داراي دو خانه حافظه A و B است كه در ابتداي كار در هر دو خانه عدد صفر قرار دارد. در هر مرحله بر حسب اينكه حركت به سمت شمال، جنوب، شرق يا غرب باشد، به ترتيب به خانه A يكي اضافه مي‌شود، از خانه A يكي كم مي‌شود، به خانه B به اندازه عدد خانه A اضافه مي‌شود و از خانه B به اندازه عدد A كم مي‌شود. فرض كنيد روبات مسيري را طي كند كه خودش را قطع نكرده و در نهايت به جاي اول خود باز گردد. ثابت كنيد در انتهاي مسير، قدرمطلق مقدار خانه حافظه B برابر است با مساحت شكلي كه روبات پيموده است.
سوالي از مرحله دوم رياضي (دوره 21 - تركيبيات)
- ارسال ها
- 46
- لایک ها
- 0
- امتیاز
- 0
1 l_____ ___________l
2 l__ __l
3 l______l
شکل بالا قسمتی از مسیر طی شده توسط روبات را نشان میدهد (جهت آن مهم نیست)
ابتدا ثابت میکنیم اگر چنین چیزی در مسیر وجود داشته باشد(یک تحدب یا تقعر در مسیر) آن گاه میتوان آن را جدا کرد
مثلا" در شکل بالا اگر ارتفاع هر یک از خطوط 1 ,2 یا 3 برابر 1 باشند می توان خط سوم را کلا" برداشت و به جای در قسمت خالی خط 2 خط قرار دهیم
(یعنی ثابت می کنیم عددی که به مساحت کل مسیر اضافه شده یا از آن کم شده برابر همان مقداری است که به حافظه اضافه یا کم شده است که برای راحتی محاسبات هم این تکه ها را با ارتفاع 1 فرض می کنیم)
این گونه:
1 l________ ________l
2 l___________l
همین کار را برای خط 2 نیز انجام میدهیم
حالا واضح است که با این عمل می توان کل مسیر طی شده توسط روبات را به یک مستطیل تبدیل کرد
فقط می ماند که ثابت کنیم که عددی که در حافظه ی روبات پس از طی یک مستطیل باقی می ماند مساحت مستطیل است که این هم راحت است
البته بعضی از ریزه کاری های حین اثبات رو دیگه نگفتم و اونا بمونه برای وقتی که خودتون خواستین اثبات کنین
2 l__ __l
3 l______l
شکل بالا قسمتی از مسیر طی شده توسط روبات را نشان میدهد (جهت آن مهم نیست)
ابتدا ثابت میکنیم اگر چنین چیزی در مسیر وجود داشته باشد(یک تحدب یا تقعر در مسیر) آن گاه میتوان آن را جدا کرد
مثلا" در شکل بالا اگر ارتفاع هر یک از خطوط 1 ,2 یا 3 برابر 1 باشند می توان خط سوم را کلا" برداشت و به جای در قسمت خالی خط 2 خط قرار دهیم
(یعنی ثابت می کنیم عددی که به مساحت کل مسیر اضافه شده یا از آن کم شده برابر همان مقداری است که به حافظه اضافه یا کم شده است که برای راحتی محاسبات هم این تکه ها را با ارتفاع 1 فرض می کنیم)
این گونه:
1 l________ ________l
2 l___________l
همین کار را برای خط 2 نیز انجام میدهیم
حالا واضح است که با این عمل می توان کل مسیر طی شده توسط روبات را به یک مستطیل تبدیل کرد
فقط می ماند که ثابت کنیم که عددی که در حافظه ی روبات پس از طی یک مستطیل باقی می ماند مساحت مستطیل است که این هم راحت است
البته بعضی از ریزه کاری های حین اثبات رو دیگه نگفتم و اونا بمونه برای وقتی که خودتون خواستین اثبات کنین
راه خودم ايده‌اش توي همين مايه‌ها ولي به يه روش ديگست:
روي طول مسير استقراي قوي مي‌زنيم. مي‌دانيم حتماً در طول مسير روبات، جايي وجود دارد كه مي‌توان با يك مسير ميان‌بر، آن‌را به يك مستطيل تبديل كرد (يعني همان چيزي كه شما گفتيد). اين مستطيل حتماً در بالاترين سطري كه روبات رفته است قابل تشكيل است. با كمي بررسي (كه حال گفتنشو ندارم
) متوجه مي‌شويم كه با رفتن از اين مسير ميان‌بر، مساحت مستطيل در خانه B با توجه به جهت آن به صورت مثبت يا منفي ذخيره مي‌شود. بقيه مسير نيز با توجه به فرض استقرا اثبات مي‌شود (پايه استقرا با خودتان).
اما با عرض پوزش من در مورد راه حل شما يه خورده گيج شدم و درست متوجهش نشدم. يعني شما اثبات كرديد هر مسيري را مي‌توان به يك مستطيل كرد و از روي آن اثبات كرديد كه مساحت در خانه B ذخيره مي‌شود؟ شما از كجا مطمئنيد آن شكل قسمتي از مسير روبات است؟
روي طول مسير استقراي قوي مي‌زنيم. مي‌دانيم حتماً در طول مسير روبات، جايي وجود دارد كه مي‌توان با يك مسير ميان‌بر، آن‌را به يك مستطيل تبديل كرد (يعني همان چيزي كه شما گفتيد). اين مستطيل حتماً در بالاترين سطري كه روبات رفته است قابل تشكيل است. با كمي بررسي (كه حال گفتنشو ندارم
اما با عرض پوزش من در مورد راه حل شما يه خورده گيج شدم و درست متوجهش نشدم. يعني شما اثبات كرديد هر مسيري را مي‌توان به يك مستطيل كرد و از روي آن اثبات كرديد كه مساحت در خانه B ذخيره مي‌شود؟ شما از كجا مطمئنيد آن شكل قسمتي از مسير روبات است؟
