Question

Чи можна зафарбувати деякі клітинки квадрата розміром 9 * 9Tak щоб у кожної клітинки було рівно два зафарбовані сусіди? (Клітинки назива- ються сусідніми, якщо вони мають спільну сто- рону).

Answer 1

Ответ:

Так, це можливо.

Один можливий спосіб зафарбування такий:

1 0 1 0 1 0 1 0 1

0 1 1 0 1 1 0 1 0

1 1 0 1 0 1 0 1 1

0 0 1 1 1 0 1 1 0

1 1 0 1 0 1 0 1 1

0 1 1 0 1 1 0 1 0

1 0 1 0 1 0 1 0 1

0 1 1 0 1 1 0 1 0

1 0 1 0 1 0 1 0 1

У цій матриці кожна клітина має два зафарбовані сусіди, і всі сусідні клітини спільно мають одну сторону.

Існує кілька різних способів зробити це, і це можна зробити, використовуючи теорію графів та матриці суміжності, де кожна клітина буде представлена як вершина, а сусідні клітини будуть з'єднані ребрами.