مسابقه‌ی تصادفی

 
 
 ميزگرد (مسابقه‌ي شماره‌ي 48)
ميزگرد (مسابقه‌ي شماره‌ي 48)مسابقه كامپيوتر
اصل لانه‌ي كبوتري ... سؤال همراه با جواب

ميزگرد






اشاره

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



چكيده
 اهداف آموزشي
اهداف آموزشي در حوزه‌ي شناختي - دانش
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش روش‌ها يا روش‌شناسي»
اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
    - «فهميدن» > «كاربستن»
    - «فهميدن» > «تركيب» > «استنتاج مجموعه‌اي از روابط انتزاعي»

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





سؤال
الف - 15 صندلي يكسان دور يك ميزگرد قرار گرفته‌اند؛ بر روي ميزگرد نام كارت‌هايي براي 15 نفر مشخص است. افراد متوجه اين كارت‌ها نمي‌شوند مگر آن‌كه پشت ميز بنشينند و ناگهان متوجه بشوند كه هيچ‌كس جلوي كارت خود ننشسته است.

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

ب – مثالي از يك آرايش بزنيد كه تنها يكي از 15 نفر به‌طور صحيح نشسته باشد و براي هيچ دوراني از ميز بيش از يك‌نفر در جاي صحيح خود قرار نگرفته باشد.





 

جواب

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

قسمت ب – براي بررسي وضعيتي كه هيچ فردي در مقابل نام كارت خود قرار نگرفته باشد از دو روش مي‌توانيم به مسأله بپردازيم:

راه هندسي
مجبوريم نشان دهيم وقتي افراد و كارت‌ها در وضعيت صحيح قرار نگرفته‌اند دقيقاً تنها يك نفر در هر يك از 15 دوران روي صندلي صحيح پشت ميز قرار مي‌گيرد. اما اين يك مفهوم استاندارد درباره‌ي تقارن يك چند ضلعي منظم است كه متشكل از  دوران و بازتاب
است:

- دوران‌ها نظم رؤوس را حفظ مي‌كند
- در حالي كه بازتاب اين نظم را برهم مي‌زنند.

زماني كه  عددي «فرد» باشد هر بازتاب يك رأس (مثلاً: رأس ) را تثبيت كرده و موقعيت رأس مذكور را در فاصله‌ي  از سمت راست تا سمت چپ رأس  تغيير مي‌دهد.

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

 راه جبري
در راه جبري مي‌توانيم فرض كنيم:




(رابطه‌ي 1)

كه در آن  و  اعداد كم‌تر از 15 هستند؛ هم‌چنين  داراي هر دو ويژگي بوده و به‌همراه  نسبت به عدد 15 «اول» محسوب مي‌شوند.  بايد نسبت به 15 «اول» باشد به‌گونه‌اي كه رابطه‌ي  براي دقيقاً يك مقدار  صادق بوده و مقدار  هم اهميتي ندارد.

 احتمالاً داراي مقادير ذيل است:




(رابطه‌ي 2)

اين مقادير تنها مقادير ممكن براي  است تا نسبت به 15 بتواند «اول» باشد.

از آن‌جايي كه عدد 14 همان  است اين مقدار، جوابي عمومي براي مسأله نيز محسوب مي‌شود يعني وضعيتي كه نام كارت‌ها مخالف نام افراد باشد.

دو جواب ديگر اين مسأله اين است كه كارت  در جلوي فرد  گذاشته شود و يا كارت  در جلوي فرد  (كه معادل است با نشستن فرد  در جلوي كارت ).



 جواب كلي‌تر
اكنون مسأله را براي زماني حل مي‌كنيم كه تعداد افراد ‌نفر باشند:

زماني كه  نفر دور ميز نشسته باشند به‌گونه‌اي كه چگونگي دوران ميز اهميتي نداشته باشد دقيقاً يكي از افراد جلوي كارت صحيح خواهد نشست:

 

زماني كه  عددي «فرد» باشد  هميشه يك جواب مسأله خواهد بود. علت آن است كه  و  نسبت به هر عدد «فرد»  اول هستند.

 

 واضح است كه وقتي  عددي «زوج» باشد راه‌حلي براي رابطه‌ي وجود ندارد به‌خاطر اين‌كه  يا  يا «زوج» بوده و بنابراين نسبت به  «اول» نيستند.

وقتي عددي «زوج» باشد هرگز آرايشي از  در مورد كارت‌ها وجود ندارد به‌گونه‌اي كه از هر  از عدد صفر تا ، تنها عدد  (در بين اعداد صفر تا ) در رابطه‌ي  صدق مي‌كند.

شرايطي كه در آن براي هر عدد ، رابطه‌ي  تنها با عدد  برقرار باشد جايگشت‌هاي  و  از  خواهد بود.

اكنون  را به‌شكل ذيل تعريف مي‌كنيم:






(رابطه‌ي 3)

توجه كنيم كه داريم:





(رابطه‌ي 4)

علت آن است كه عبارت‌هاي داخل «براكت‌ها» جمع اعداد صحيح از صفر تا ‌هستند.

اما از آن‌جايي كه لازم است  جايگشتي از اعداد صحيح از صفر تا  باشد بايد ‌معادل جمع آن اعداد صحيح باشد به‌عبارت ديگر:





(رابطه‌ي 5)

از آن‌جايي كه  عددي «زوج» است براي بعضي از مقادير  داريم:




(رابطه‌ي 6)

از آن‌جايي كه  داريم:





(رابطه‌ي 7)

اين با رابطه‌ي 4 - كه در آن ‌است - در تناقض مي‌باشد. نتيجه مي‌گيريم كه تعداد افراد  نمي‌تواند «زوج» باشد.

1386/10/13لينک مستقيم

فرستنده :
علیرضا شفائی HyperLink HyperLink 1386/11/8
مـتـن : با سلام و خسته نباشید

قسمت الف: تابلوئه!
لم: در هر حالت از چیدمان افراد و میز مربوطه ی آنها میشه برای هر نفر با چرخاندن میز یک حالتی را به وجود آورد که آن فرد جلوی شماره خودش نشسته باشد!
اثبات» با توجه به اینکه میدونیم شماره تمام افراد روی میز هست با یک حرکت نمادین انقدر میز را میچرخانیم تا شماره اش بیاد جلوش!

حالا میریم سر مسئله . 15 نفر داریم . برای هر کدوم میشه از لم بالا استفاده کرد و در 15 حالت مختلف برای یک نفر یک حالت درست بوجود آورد.
از آنجایی که خوده میز 15 حالت بیشتر نداره و اینکه در یکی از این 15 حالت هیچکدوم در جای خودشون نیستن. 14 حالت خالی میمونه که طبق اصل لانه ی کبوتری
(Pigeonhole principle) (انگلیسیش خیلی باحاله!) در یکی از حالات دو نفر هستن که در جای صحیح نشستن!

اینم یک نمونه که در قسمت ب گفتید:
http://ashafaei.parsaspace.com/ans1.jpg


در مورد اون مسئله ای که گفته بودم بعد از پست کاربر را به یک صفحه دیگر بفرسته این بود که وقتی همین صفحه دوباره میاد مرورگر(اینجا فایر فاکس) متن تایپ شده را دوباره در کادرهای خالی قرار میده . اینطوری و با عنایت به سیستم پیشرفته مخابرات و اینترنت ایران و البته تجربه های قبلی کاربر تصور میکنه پست نشده!و ... فکر کنم با این که یک چیز چند بار پست شده زیاد برخورد کرده باشید.
پاسـخ :ايميل فرستنده: a.shafaei@gmail.com
تاريخ ارسال: 1386/10/17


عليرضا جان!
جواب قسمت اول سؤال رو به‌خوبي مطرح كردي. افرين بر شما.
اما در مورد قسمت دوم پيشنهاد مي‌كنم حتما جواب سؤال رو ببيني.
عليرضا جان!
به‌لطف خدا، به خوبي با سؤال‌ها پيش مي‌آي و ما از اين‌كه جواب سؤال‌ها رو با شجاعت مطرح مي‌كني خيلي خوشحاليم . برات آرزوي موفقيت مي‌كنيم.
ضمناً درگير شدن با مسائل علمي انصافا باحال‌ترين چيزيه كه مي‌شه تصور كرد. علتش هم اينه كه توسط قادر مطلق - كه زيباترين و باحال‌ترين موجوده - به‌زيبايي طراحي شده.
از نكته‌هاي فني‌اي هم كه متذكر شدي واقعاً تشكر مي‌كنيم. بله بعضا جواب‌هاي دوگانه برامون ارسال مي‌شه كه حالا موضوع رو به مسؤولين فني انتقال مي‌ديم.
باز هم از تو برادر بزرگوار تشكر مي‌كنيم.

فرستنده :
آناهیتا HyperLink HyperLink 1386/11/8
مـتـن : روی الف فکر نکردمD:
ولی ب :
اگه همه به ترتیب و در جهت مخالف ترتیب اعدادشان بنشینند در حالت اول فقط یک نفر در جای صحیح نشسته و با هر چرخش هم فقط یکی در جای صحیح خود خواهد نشست.
پاسـخ :ايميل فرستنده: machereana@gmail.com
تاريخ ارسال: 1386/10/20

آناهيتا جان!
اين قسمت از راه‌حلت كاملا صحيحه و به تو به‌خاطر اون تبريك مي گم ولي بقيه‌ي مسأله رو هم ثابت كن.
اشناءالله موفق باشي!

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2355
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2355