پنجشنبه ۶ ارديبهشت ۱۴۰۳   |  كاربر مهمان   |    
 مسابقه‌ی تصادفی

 
 
 برش يك كيك شكلاتي (مسابقه‌ي شماره‌ي 46)
برش يك كيك شكلاتي (مسابقه‌ي شماره‌ي 46)مسابقه كامپيوتر
استقراي قوي ... سؤال همراه با جواب

برش يك كيك شكلاتي





اشاره

آن‌چه كه با عنوان «چكيده» در اول مسابقه‌ها و زنگ تفريح‌ها مشاهده مي‌كنيد صرفاً مخصوص معلمان، مربيان، كارشناسان محترم آموزشي و ساير علاقه‌مندان است.



چكيده
 اهداف آموزشي
اهداف آموزشي در حوزه‌ي شناختي - دانش
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش روش‌ها يا روش‌شناسي»
    - «دانش امو كلي و مسائل انتزاعي» > «دانش اصل‌ها و تعميم‌ها»
اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
    - «فهميدن» > «كاربستن»
    - «فهميدن» > «تحليل» > «تحليل عناصر»
    - «فهميدن» > «تركيب» > «توليد يك نقشه يا مجموعه اقدام‌هاي پيشنهادي»
    - «فهميدن» > «تركيب» > «استنتاج محموعه‌اي از روابط انتزاعي»
 نتايج مورد نظر
    - آشنايي با مفاهيم استقراي قوي
    - روش حل مسأله با استقراي قوي
محتواي آموزشي (سرفصل‌هاي المپياد جهاني)
    - استقرا > استقراي قوي




سؤال
از شما خواسته مي‌شود يك كيك شكلاتي مكعب مستطيلي را به  شكلات مكعبي (با اضلاع برابر) تقسيم كنيد. به‌عبارت ديگر هدف آن است كه  كيكي مربعي مستقل به‌دست آيد.

از طرف ديگر تنها اجازه داريد در هر مرتبه تنها يك قطعه شكلات را با استفاده از يك برش عمودي يا افقي ببريد.

به‌عنوان مثال فرض كنيد بنا داريد كيك شكلاتي مكعب مستطيلي را به  قطعه‌ي شكلاتي ببريد. اولين برش دو قطعه‌ي  ايجاد مي‌كند. با يك برش ديگر مي‌توانيد هر دو قطعه‌ي ايجاد شده را به دو قطعه‌ي مستقل تبديل كنيد. بدين‌ترتيب نهايتاً سه برش مورد نياز خواهد بود.


ثابت كنيد براي تقسيم كيك شكلاتي مكعب مستطيلي را به  شكلات مكعبي (با اضلاع برابر) به  برش نياز داريد. 




جواب
براي اثبات اين مسأله به‌راحتي نمي‌توان از «استقرا» استفاده كرد به‌علت آن‌كه دو متغير وجود دارد. معمولاً در استدلال‌هايي كه چند متغير وجود داشته باشد با استفاده از مجموعه‌اي از استقراهاي تو در تو مي‌توان آن را اثبات كرد. اما به هر حال در اين حالت مي‌توانيم از استقرا در مورد يك متغير و يك عمليات ماهرانه استفاده كنيم.

به‌طور استدلالي اگر بخواهيم يك كيك شكلاتي را به‌طور كامل برش دهيم نياز داريم كه يك‌بار آن را به دو نيم كنيم و سپس به‌صورت بازگشتي هر نيمه را به دو نيم قسمت تقسيم كنيم.

اين بيانگر استفاده از «استقراي قوي» در اندازه‌ي كيك شكلاتي است كه اندازه برحسب واحد چهارگوش كيك بيان مي‌شود. اكنون به‌جاي مسأله‌اي كه شامل دو متغير باشد (مسأله‌ي دو بعدي) مسأله يك متغيره (برحسب اندازه) خواهد بود. با اين ساده‌سازي مي‌توانيم مسأله را با «استقراي قوي» حل كنيم.

براي اثبات از «استقراي قوي» در اندازه‌ي كيك شكلاتي استفاده مي‌كنيم. فرض كنيد  گزاره‌اي باشد كه عبارت است از: يك كيك شكلاتي با اندازه‌ي  كه به  برش نياز دارد.

 مرحله‌ي اول
ابتدا  را 1 در نظر مي‌گيريم:




(رابطه‌ي 1)

 صحيح است چون براي اين‌كه تنها يك چهارگوش كيك شكلاتي داشته باشيم به  برش نياز است.

 مرحله‌ي استقرايي
فرض كنيد  و هر قطعه كيك شكلاتي با اندازه‌ي  كه در آن:  است نياز به حداكثر  برش است. حالا بايد نشان دهيم كه براي برش يك قطعه شكلات به‌اندازه‌ي  به حداكثر  برش نياز است.

براي اين منظور ابتدا قطعه كيك شكلاتي با اندازه‌ي  را به قطعه‌هاي كوچك‌تر با اندازه‌ي  و  برش مي‌دهيم؛ لذا داريم:




(رابطه‌ي 2)

اين امر مطمئناً ممكن است به‌خاطر اين‌كه اندازه‌ي قطعه كيك شكلاتي حداقل 2 است. اكنون قطعه‌هاي با اندازه‌ي  و  بين 1 و  است بنابراين با استفاده از «استقراي قوي» برش دادن اين دو قطعه به چهارگوش‌هاي مستقل به‌طور جداگانه نياز به  و  برش است.

بنابراين حداكثر تعداد كل برش‌هاي مورد نياز براي برش قطعه كيك شكلاتي با اندازه‌ي به  چهارگوش‌هاي مجزا از رابطه‌‌ي ذيل محاسبه خواهد شد:








(رابطه‌ي 3)


اين رابطه نشان مي‌دهد كه  بر دلالت داشته و بدين‌ترتيب مسأله با استقراي قوي ثابت مي‌شود.
1386/9/28 لينک مستقيم
فرستنده :
محمد.ح.ب HyperLink HyperLink 1386/10/8
مـتـن : بسمه تعالي
ابتدا به روش استقرا اثبات مي كنيم براي ايجاد k قطعه نياز به k-1 برش نياز داريم :
اصل : (تعداد برشهاي مورد نياز) n=2 => 1 (تعداد قطعات)
فرض : n=k => k-1
حكم : n=k+1 => k
بنابراين با افزودن 1 به دو طرف فرض حكم ثابت مي شود . يعني ميدانيم براي تبديل k مكعب چسبيده به k-1 برش نياز داريم.حال ميتوانيم بنويسيم در برش يك مكعب n*m به مكعبهاي يكسان:1- اگر ابتدا ضلع n را تقسيم كنيم به n-1 برش نياز داريم. 2- بنابراين در اثر اين برش n قطعه به وجود مي ايد. حال اگر بخواهيم هر كدام از n قطعه را m قطعه كنيم به(n.(m-1 برش نياز داريم. بنابراين كل برشها مي شود:
(n-1) + n(m-1)كه اگر ساده شود ميشود : (n*m)-1
يعني براي ايجاد مكعب هاي مساوي در صورتي كه يكي از اضلاع مكعب مستطيل يك باشد تنها مي توان مكعبات 1*1 كه مساوي باشند ايجاد كرد.
حال اگر بخواهيم ارتفاع را نيز تاثير دهيم از فرمول زير استفاده مي كنيم :
n-1)+n(m-1)+n.m(p-1) = (m.n.p)-1)
دراين فرمول اگر بخواهيم شكل را به k*k مكعب يكسان تقسيم كنيم بايد اضلاع را بر k تقسيم كرده و انهارا در فرمول بگذاريم واگر تقسيم پذير نبودند يعني نمي توان قطعه را به k*k مكعب يكسان تقسيم كرد .
پاسـخ : ايميل فرستنده: mb70js2@yahoo.com
تاريخ ارسال: 1386/10/5

محمد جان!
از اين‌كه بدين زيبايي استدلال كردي تشكر مي‌كنيم. شما موفق شدي يكي از قضايايي را حل كني كه حل اون رو بعضي از محققان به خود نسبت مي‌دهند. به‌راستي فرزندان اين خاك و بوم افرادي با استعداد هستند كه فقط با پشتكار و انگيزه مي‌توانند پيشتاز در علوم مختلف باشند.
موفق باشي و درود بر شما!
فرستنده :
ناشناس HyperLink HyperLink 1386/10/8
مـتـن : سلام
پاسـخ : ايميل فرستنده: mb70js2@yahoo.com

سلام دوست خوبم!
از اين‌كه با دوستانت در شبكه‌ي رشد ارتباط برقرار كردي تشكر مي‌كنيم. درخواست مي‌كنيم در بخش‌هاي مختلف سايت نظير: مسابقه، زنگ تفريح، مشاوره و پرسش و پاسخ علمي مشاركت فعال داشته باشي.
موفق باشي!
نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 المپیاد کامپیوتر

 

     

 

  

صفحه‌ي اصلي
     

 

راهنماي سايت
     

 

  

آموزش
     

 

بانك سوال
     

 

  

مسابقه
     

 

  

زنگ تفريح
     

 

  

مصاحبه و گزارش
     

 

  

معرفي كتاب
     

 

  

مشاوره
     

 

  

پرسش‌و‌پاسخ‌علمي
     

 

اخبار

 

فعاليت‌هاي علمي
 بازديدها
كاربران غيرعضو آنلاين كاربران غيرعضو آنلاين:   2175
  كاربران عضو آنلاين:   0
  کل كاربران آنلاين:   2175
 

سرویس‌های رشد:

فهرست:

وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران (رشد)