المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۷:سوال ۴

سوال ۴

در شکل مقابل هر نقطه یک کامپیوتر و هر خط٬ یک سیم ارتباطی است که دو کامپیوتر را به هم متصل می‌کند.

یک «خرابی منظم» در سیستم هنگامی به وجود می‌آید که از هر کامپیوتر دقیقا یکی از سیم‌های ارتباطی قطع شده باشد. به چند حالت ممکن است خرابی منظم در این سیستم روی دهد؟

  1. ۶
  2. ۷
  3. ۸
  4. ۹
  5. ۱۰

پاسخ

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

مطابق شکل سیم‌ها را از ۱ تا ۱۲ شماره‌گذاری می‌کنیم دسته سیم‌هایی که می‌توانیم حذف کنیم تا به منظور فوق برسیم عبارت‌اند از:

$$(2,4,10,12)،(2,4,9,11)،(1,7,8,9)،(1,3,10,12)،(1,3,9,11)، \\ (5,6,7,8)،(4,6,7,12)،(3,5,6,11)،(2,5,8,10)$$

پس در مجموع ۹ حالت ممکن است.


ابزار صفحه