Закрасьте несколько клеток таблицы 6 × 6 так, чтобы в каждой строке было ровно три закрашенных клетки, а в каждом столбце либо одна, либо четыре.

У меня получилось где-то так:

a6, b6, c2, c3, c4, c6, d1, d3, d4, d5, e1, e2, e4, e5, f1, f2, f3, f5.

Существуют ли способы принципиально отличные от данного? Как подойти к решению аналитически, а не интуитивно?

Заранее спасибо!

задан 4 Май '14 2:10

10|600 символов нужно символов осталось
1

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

Но можно высказать следующие дополнительные соображения. Прежде всего, число $%k$% столбцов с четырьмя закрашенными клетками однозначно находится из уравнения $%4k+(6-k)=6\cdot3$%. Понятно, что $%k=4$%.

Далее можно построить двудольный граф, описывающий ситуацию из условия. У этого графа будет 6 вершин типа A (строки) и 6 вершин типа B (столбцы). Вершину типа A соединяем с вершиной типа B, если соответствующая клетка таблицы закрашена.

Из каждой вершины типа A выходит по три ребра, а в вершины типа B входит количество рёбер, равное 4, 4, 4, 4, 1, 1 соответственно. Теперь можно проанализировать, сколько имеется принципиально разных способов провести эти рёбра требуемым способом.

Можно начать с двух последних вершин типа B. Они подсоединены либо к одной вершине типа A (это Ваш случай), либо к разным (когда я строил свой пример, то у меня получилось именно так, что как бы и не лучше, и не хуже). Это уже говорит о том, что конфигурации могут быть разных типов. Можно проверить, что при том плане, который избрали Вы, конфигурация далее восстанавливается однозначно с точностью до симметрии.

ссылка

отвечен 4 Май '14 14:59

Спасибо преогромное!!!

(6 Май '14 0:07) Сардаана

Вещи такого рода можно спрашивать почаще: "эвристическую" составляющую обсуждать бывает весьма интересно.

(6 Май '14 0:10) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,131

задан
4 Май '14 2:10

показан
1662 раза

обновлен
6 Май '14 0:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru