Question

Пол у Васи в квартире состоит из 49 красных и белых плиток,
уложенных как попало.
Вася хочет, чтобы от каждой красной плитки можно было добраться
до любой другой красной, переходя каждый раз на соседнюю по
горизонтали или вертикали красную плитку, и чтобы от каждой
белой плитки можно было добраться до любой другой белой,
переходя каждый раз на соседнюю по горизонтали или вертикали
белую плитку.
Какое наименьшее число плиток он должен перекрасить?

Answer 1

Если пол у Васи состоит из 49 плиток, и он хочет соединить каждую красную плитку с каждой другой красной, а также каждую белую с каждой другой белой, то можно воспользоваться графовой моделью.

Представим каждую плитку как вершину графа, а связи между красными и белыми плитками как рёбра. В данном случае, для наилучшей связи, граф будет представлять из себя два полных подграфа - один для красных и один для белых плиток.

Наименьшее количество плиток, которые нужно перекрасить, будет равно числу рёбер между красными и белыми плитками.

Число красных вершин (плиток) = Число белых вершин (плиток) = 49 / 2 = 24 (так как 49 - нечетное).

Для каждой красной плитки нужно установить связь с каждой белой плиткой, что даст 24 * 24 = 576 рёбер между ними.

Таким образом, Васе нужно перекрасить 576 плиток.