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

 
 
 اتومبیل
اتومبیلمسابقه كامپيوتر
مسابقه شماره ۲۱۱

سوال
نقشه‌ی خیابان‌های شهری به شکل مقابل است.(خیابان‌های عمودی رو به بالا یک طرفه‌اند) می‌خواهیم اتومبیل‌های ۱ تا ۴ را به گاراژ‌هایی که در شکل نشان داده شده است ببریم , به طوری که از هر خیابان حداکثر یک اتومبیل عبور کند. کدام یک از دنباله‌های زیر ( از چپ به راست ) می‌تواند شماره‌های اتومبیل‌ها در گاراژهای ۱ تا ۴ باشد ؟


الف ) ۲ و ۴ و ۳  و ۱
ب )‌ ۲و  ۴و ۱ و۳
ج ) ۳ و ۴ و ۱ و ۲
د ) ۴ و ۱ و ۳ و ۲
ه‍ ) هیچ‌کدام


پاسخ
نقشه خیابان‌ها شامل ۱۲ خیابان عمودی و ۱۲ خیابان افقی است. بدیهی است که برای رسیدن به گاراژها هر کدام از اتومبیل‌ها سه خیابان عمودیی و در مجموع ۱۲ خیابان عمودی را طی می‌کنند. پس تمام ۱۲ خیابان عمودی توسط اتومبیل‌ها طی می‌شود. دو ستون اول را در نظر می‌گیریم. فرض می‌کنیم اتومبیل شماره ۱ از خیابان افقی از خیابان افقی شماره i (۴ ≥ i ≥ ۱) به سمت راست رفته و یکی از اتومبیل‌های دیگر از خیابان افقی شماره j (۴ ≥ j ≥ ۱) به سمت چپ برود. بدیهی است که j ≠ i. زیرا در غیر این‌صورت از این خیابان یک ماشین به سمت چپ و یک ماشین به سمت راست رفته است که مخالف فرض است.
اگر i < j , آنگاه در ستون اول خیابان عمودی بین سطر i و j توسط هیچ اتومبیلی طی نمی‌شود و اگر j < i , آنگاه در ستون اول خیابان عمودی بین سطر i و  j توسط دو اتومبیل طی می‌شود که مخالف فرض است. بدین ترتیب ثابت می‌شود که اتومبیل i فقط به گاراژ i می‌تواند برود

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

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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