1. Главная
  2. Библиотека
  3. Геометрия
  4. На космической станции установлено 160 компьютеров. Нек...
Разбор задачи

На космической станции установлено 160 компьютеров. Некоторые из них соединены кабелями. Каждый соединён хотя бы с одним. Каждый кабель соединяет ровно два компьютера. Половина компьютеров оказалась заражена вирусом. 80 компьютеров показали, что они

  • Предмет: Геометрия
  • Автор: Кэмп
  • #Дискретная математика
  • #Теория графов
На космической станции установлено 160 компьютеров. Некоторые из них соединены кабелями. Каждый соединён хотя бы с одним. Каждый кабель соединяет ровно два компьютера. Половина компьютеров оказалась заражена вирусом. 80 компьютеров показали, что они

Условие:

На космической станции установлено 160 компьютеров. Некоторые из них соединены кабелями. Каждый соединён хотя бы с одним. Каждый кабель соединяет ровно два компьютера. Половина компьютеров оказалась заражена вирусом. 80 компьютеров показали, что они соединены только с исправными компьютерами, 80 показали, что соединены только с заражёнными. При этом все исправные компьютеры дали верную информацию, а заражённые — ложную. Каково наименьшее возможное количество кабелей, соединяющих исправный компьютер с заражённым.

Решение:

1. Дано

  1. Общее количество компьютеров: N=160N = 160.
  2. Каждый компьютер соединён хотя бы с одним другим (нет изолированных вершин).
  3. Каждый кабель соединяет ровно два компьютера.
  4. Количество заражённых компьютеров (ZZ): NZ=1602=80N_Z = \frac{160}{2} = 80.
  5. Количество исправных компьютеров (II): NI=16080=80N_I = 160 - 80 = 80.
  6. Информация от компьютеров:
  • 80 компьютеров сообщили, что соединены только с исправными (назовем эту группу SIS_I).

  • 80 компьютеров сообщили, что соединены только с заражёнными (назовем эту группу SZS_Z).

  1. Правила отчётности:
  • Исправн...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое ключевое условие позволяет определить минимальное количество кабелей между исправными и заражёнными компьютерами?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет