المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۳۵

سوال ۳۵

چهار شهر با جاده‌هایی مانند شکل مقابل به هم وصل هستند. فاصله‌ی یک شهر تا یک شهر دیگر٬ به صورت عددی برحسب کیلومتر بر روی جاده‌ای که آن دو شهر را به هم وصل می‌کند نوشته شده است. می‌خواهیم تعدادی ایستگاه آتش‌نشانی روی جاده‌ها و یا در شهر‌ها ایجاد کنیم٬ به طوری که برای هر شهر حداقل یک ایستگاه آتش‌نشانی در فاصله‌ی حداکثر ۶ کیلومتری آن باشد.

کدام یک از گزینه‌های زیر در مورد کم‌ترین تعداد ایستگاه‌های آتش‌نشانی و محل آن‌ها درست است؟

  1. ۲ ایستگاه بر روی جاده های $AD$ و $BC$
  2. ۲ ایستگاه بر روی جاده های $AD$ و $AC$
  3. ۲ ایستگاه بر روی جاده های $BD$ و $DC$
  4. ۳ ایستگاه بر روی جاده های $BD$ و $AB$ و $AC$
  5. گزینه‌های ۱ و ۲

پاسخ

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

یکی از سه حالت زیر می‌تواند جواب باشد:

  1. ۲ایستگاه بر روی جاده‌های $Ab$ و $DC$
  2. ۲ ایستگاه بر روی جاده‌های $AD$ و $BC$
  3. ۲ ایستگاه بر روی جاده‌های $AC$ و $BD$

ابزار صفحه