Question

У кожнiй клiтинцi дошки 4x4 йе лампи.Двi лампи на цiй дошцi називають сусiднiми,якщо вони розташованi в клiтинах зi спiльною стороною.Спочатку вмикають декiлька ламп,згодом щохвилини вмикають кожну лампу,що майе щонайменше двi сусiднi лампи,що свiтять.Яку мiнiмальну кiлькiсть ламп треба увiмкнути спочатку,щоб в певний момент часу усi лампи свiтились? А:3 Б:4 В:5 Г:6 Д:7

Answer 1

Минимум 4, так как диагональ доски составляет 4 клетки. Располагаем  4 лампы по диагоналям, и постепенно двигаемся к углам в угловом порядке, так будут заняты все клетки.

Answer 2

Задача цікава! Давай розберемося.

Спростимо завдання. Представимо кожну лампу як вершину графа, а з'єднання між лампами, якщо вони сусідні, - як ребро графа. Тепер завдання стає задачею про знаходження максимального незалежного множини (МНМ) у графі. Максимальне незалежне множина - це такий набір вершин, що жодні дві вершини не з'єднані ребром.

Для початку ввімкнемо кілька ламп. Згідно умови, кожну хвилину ми вмикаємо кожну лампу, яка має щонайменше дві сусідні лампи, які світять. Це означає, що ми будемо вмикати лампи, які є частиною графа з вершинами ступеня не менше 2.

Тепер розглянемо варіанти:

А) Якщо вмикається одна лампа, вона не має сусідів, отже, це не максимальна незалежна множина.

Б) Якщо вмикаються дві лампи, і вони сусідні, то це теж не максимальна незалежна множина.

В) Якщо вмикаються три лампи, і вони утворюють трикутник (три вершини, кожна з'єднана з іншими двома), то це максимальна незалежна множина. Отже, відповідь - 3 лампи.

Отже, правильний варіант - А: 3 лампи.