المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۴:سوالات ۱۶ تا ۱۹

سوالات ۱۶ تا ۱۹

ده نفر با شماره‌های ٫۱۰…۱٫۲٫ در صف یک بانک قرار دارند که سه باجه برای انجام امور متقاضیان دارد. در ابتدا همه‌ی باجه‌ها خالی هستند. با شروع از فرد شماره‌ی ۱ ٬ هرکس به اولین باجه‌ی خالی می‌رود و هر گاه کار کسی در باجه‌ای تمام شد٬ بلافاصله نفر اول صف جایگزین او می‌شود. علاوه بر این٬ کار هر نفر حداقل یک ثانیه طول می‌کشد و هیچ‌ دو نفری دقیقا هم‌زمان باجه‌ها را ترک نمی‌کنند. پس از اتمام کار نفر دهم این فرآیند پایان می‌یابد. در این فرآیند دو نفر را «هم‌زمان» گوییم اگر لحظه‌ای وجود داشته باشد که در آن هر دو در حال انجام کار در باجه‌ها باشند. «وزن» یک زوج را برابر با قدرمطلق تفاضل شماره‌های این دو نفر فرض می‌کنیم.

با توجه به توضیحات بالا به ۴ سوال زیر پاسخ دهید:

سوال ۱۶

اگر {۲٫۶} و {۳٫۷} دو زوج هم‌زمان باشند٬ چند تا از زوج‌های زیر نمی‌توانند هم‌زمان باشند؟

{۷٫۱}٫{۹٫۶}٫{۷٫۴}٫{۴٫۳}٫{۸٫۲}٫{۵٫۱}

  1. ۴
  2. ۱
  3. ۳
  4. ۲
  5. ۵

پاسخ

گزینه (۳) درست است.

چون $\{2,6\}$ و $\{3,7\}$ دو زوج هم‌زمان هستند، زمانی وجود دارد که $2,3,6$ در باجه‌ها قرار دارند. در این صورت زوج‌های $\{1,7\}$ و $\{4,7\}$ و $\{1,5\}$ نمی‌توانند هم‌زمان باشند. زوج‌های دیگر را نیز به راحتی می‌توان مشاهده کرد که می‌توانند هم‌زمان باشند.

سوال ۱۷

کم‌ترین و بیش‌ترین مقدار ممکن برای تعداد زوج‌های هم‌زمان به ترتیب چند است؟

  1. ۱۷٫۱۷
  2. ۲۴٫۱۰
  3. ۲۴٫۱۹
  4. ۲۴٫۱۷
  5. ۱۹٫۱۰

پاسخ

گزینه (۱) درست است.

با توجه به شرایطی که در مسئله گفته شده، هر نفر که وارد یک باجه می‌شود، دو زوج هم‌زمان ایجاد می‌شوند و در ابتدا نیز $1,2,3$ سه زوج هم‌زمان تشکیل می‌دهند. پس مستقل از ترتیب ورود و خروج افراد تعداد زوج‌های هم‌زمان برابر است با: $3+7\times2=17$.

سوال ۱۸

کم‌ترین و بیش‌ترین مقدار ممکن برای مجموع وزن زوج‌های همزمان به ترتیب چند است؟

  1. ۸۱٫۲۵
  2. ۸۰٫۲۵
  3. ۸۱٫۲۳
  4. ۸۰٫۲۴
  5. ۸۱٫۲۴

پاسخ

گزینه (۱) درست است.

کم‌ترین مجموع زمانی رخ می‌دهد که در آن ترتیب خروج افراد از باجه‌ها صعودی باشد، در این صورت با اضافه شدن هر نفر سه واحد به مجموع اضافه می‌شود و در ابتدا نیز که $1,2,3$ در باجه‌ها هستند، مجموع برابر ۴ است. پس در کل کم‌ترین مجموع برابر است با: $4+7\times3=25$.

بیش‌ترین مجموع نیز در حالتی رخ می‌دهد که درهر مرحله فردی از باجه خارج شود که بزرگ‌ترین شماره را دارد. در این صورت هنگامی که فرد $i$ ام وارد می‌شود، مقدار $i-1+i-2$ به مجموع اضافه می‌شود، در این صورت مجموع کلی برابر می‌شود با: $\textstyle \sum_{i=1}^9 i+\textstyle \sum_{j=1}^8 j=45+36=81$.

سوال ۱۹

اگر {۲٫۵} و {۴٫۸} و {۶٫۹} سه زوج هم‌زمان باشند٬ این افراد به چند ترتیب مختلف می‌توانند در باجه‌ها قرار گیرند؟ (دو ترتیب مختلف محسوب می‌شوند٬ اگر و فقط اگر زوجی وجود داشته باشد که در یکی هم‌زمان باشند و در دیگری هم‌زمان نباشند.)

  1. ۱۶
  2. ۱۴۴
  3. ۷۲
  4. ۲۴
  5. صفر

پاسخ

گزینه (۴) درست است.

زوج‌های $\{2,5\}،\{1,3\}$ و $\{4,8\}$ سه را در نظر بگیرید. هر کدام از این زوج‌ها برای ترتیب خروج از باجه ۲ حالت دارند که این دو حالات تاثیری بر ترتیب ورود و خروج بقیه افراد ندارند. از طرفی هنگامی که نفر دهم می‌خواهد وارد شود، ۳ حالت برای نفری که از باجه خارج می‌شود می‌توان در نظر گرفت. پس در کل $2\times 2\times 2 \times 3$ برای ترتیب قرار گرفتن افراد در باجه‌ها داریم.


ابزار صفحه