Закрасьте несколько клеток таблицы 6 × 6 так, чтобы в каждой строке было ровно три закрашенных клетки, а в каждом столбце либо одна, либо четыре. У меня получилось где-то так: a6, b6, c2, c3, c4, c6, d1, d3, d4, d5, e1, e2, e4, e5, f1, f2, f3, f5. Существуют ли способы принципиально отличные от данного? Как подойти к решению аналитически, а не интуитивно? Заранее спасибо! задан 4 Май '14 2:10 Сардаана |
Вообще-то здесь достаточно решения, найденного подбором. Если его оформить в виде таблицы, то проверка всех условий осуществляется мгновенно. Но можно высказать следующие дополнительные соображения. Прежде всего, число $%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 falcao Спасибо преогромное!!!
(6 Май '14 0:07)
Сардаана
Вещи такого рода можно спрашивать почаще: "эвристическую" составляющую обсуждать бывает весьма интересно.
(6 Май '14 0:10)
falcao
|