Сколькими способами можно раскрасить клетки квадратной таблицы
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.
Комментарии от администратора Комментарии от администратора №1.
Ответ. $2^<2020>-2.$
Решение. Пусть $b$ обозначает черный цвет, а $w$ — белый. Назовем строку чередующейся, если ее раскраска имеет вид «$bwbw\ldots$» или «$wbwb\ldots$», в противном случае раскраску назовем обычной.
Заметим, что в обычной раскраске строки существуют две соседние по стороне клетки одного цвета.
Раскрасим 1-ю строку. Число способов сделать это равно $2^<2019>.$ Из них две раскраски являются чередующимися, а остальные $<(2^<2019>-2)>$ — обычными.
i) Раскрасим 1-ю строку так, чтобы она была чередующейся (это можно сделать двумя способами). Тогда легко заметить, что и 2-я строка также должна быть чередующейся, так как в противном случае в каком-то квадрате $2 \times 2$ будут три клетки одного цвета. Причем эта строка может начинаться как с белой клетки, так и с черной. Следовательно, 2-ю, 3-ю, $\ldots,$ 2019-ю строки можно раскрасить двумя способами, а всю таблицу $2^<2019>$ способами.
ii) Пусть 1-я строка является обычной. В этой строке есть блок из двух соседних клеток одного цвета. Без ограничения общности, пусть это блок «$bb$». Тогда во 2-ой строке под данными клетками должен быть блок «$ww$». Если у нас встречается блок «$bbw$», тогда во 2-ой строке под этим блоком должен быть блок «$wwb$». Следовательно, вторая строка получается из первой строки изменением цвета всех его клеток на противоположный, то есть вторая строка определяется однозначно и она также не является чередующимися. Повторяя этот процесс, получим, что цвета всех клеток таблицы определяются однозначно. Так как раскрасить 1-ю строку можно $2^<2019>-2$ способами, то и все оставшиеся клетки можно раскрасить $2^<2019>-2$ способами.
В итоге получим, что требуемое количество раскрасок равно $$2^<2019>+(2^<2019>-2)=2^<2020>-2.$$
Источник
Сколькими способами можно раскрасить клетки квадратной таблицы
а) Поставим сначала чёрную ладью. Это можно сделать 8 · 8 = 64 способами. Чтобы белая ладья её не била, надо поставить её в другие горизонталь и вертикаль, то есть свободных для неё горизонталей будет 8 — 1 = 7, и вертикалей тоже 8 — 1 = 7. То есть, поставить белую ладью при уже поставленной чёрной можно 7 · 7 = 49 способами. Так как на каждый из 64 способов поставить чёрную ладью будет 49 способов поставить белую, то всего способов поставить обе будет 64 · 49 = 3136.
б) Поставим сначала чёрного короля. Сколько способов тогда останется для постановки белого? Рассмотрим разные случаи:
Если чёрный король стоит в углу доски, то белого нельзя ставить на 4 клетки, то есть можно поставить на одну из 8·8 — 4 = 60 клеток. Углов в доске 4, то есть таких случаев, когда чёрный король стоит в углу, а белый его не бьёт, 4 · 60 = 240.
Дальше, если чёрный король стоит с краю доски (не в углу), то белого нельзя ставить на 6 клеток, то есть можно ставить на 64 — 6 = 58 клеток. На каждой из 4 сторон доски есть 8 — 2 = 6 клеток, где чёрный король будет стоять с краю, но не в углу, то есть всего таких вариантов растановки обоих королей будет 4 · 6 · 58 = 1392.
Наконец, если чёрный король стоит на внутренней клетке доски (они образуют квадрат со стороной 8 — 2 = 6, поэтому внутренних клеток будет 6 · 6 = 36), то белого можно поставить на одну из 64 — 9 = 55 клеток. Всего вариантов расстановки, где чёрный король стоит на внутренней клетке, будет 36 · 55 = 1980.
Итак, всего подходящих вариантов будет 240 + 1392 + 1980 = (200 + 40) + (1400 — 8) + (2000 — 20) = 1600 + 2000 + (40 — 20 — 8) = 3600 + 12 = 3612
Источник
комбинаторика — Раскраска таблицы
Каждую клетку квадратной таблицы 2×2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы? В книге «Ленинградские математические кружки» предлагается решение $%2^4=16$% для случая без рассмотрения поворотов доски. Как решать такие задачи в общем случае (варьировать размер доски и количество цветов) с учетом поворотов доски? Если я не ошибся, то для двух цветов и таблицы 2×2 будет всего 6 вариантов:
задан 19 Дек ’17 19:30
aid78
2.0k ● 2 ● 18
95% принятых
@aid78: для доски 2×2 с учётом поворотов всё классифицируется по количеству. В общем случае, если учитываются повороты, или повороты с отражениями, имеется общая техника, основанная на применении леммы Бернсайда. Анализируется каждый из видов симметрий (их обычно немного), и для него подсчитывается количество вариантов, инвариантных относительно данного преобразования. Потом эти данные подставляются в готовую формулу. На форуме такие задачи бывали.
Если дадите какой-то более или менее сложный случай, и уточните вид симметрий, то можно будет разобрать.
@falcao Например, случай таблицы 3х3 и 3 цвета без подсказки я, скорее всего, не осилю. Возможно, я действительно, плохо искал на форуме, буду благодарен за ссылку.
1 ответ
Одно из обсуждений было здесь.
Случай раскраски 3×3 в три цвета разобрать можно. Отражения учитывать не будем, принимая во внимание только повороты. Вычисляем мощности множеств неподвижных точек для каждого из элементов. Для тождественного отображения имеем все таблицы, их будет 3^9. Для центральной симметрии имеется 5 клеток, раскрашиваемых свободно. Это 3^5 вариантов. Для поворота на 90 градусов будет 3^3 вариантов (для центра, углов, и полей сбоку). Для поворота на -90 градусов то же самое. Средняя величина равна (3^9+3^5+3^3+3^3)/4=4995. Это и есть количество не эквивалентных раскрасок.
Для сравнения: если квадрат 2×2, а цветов 2, то по такой же формуле имеем (2^4+2^2+2^1+2^1)/4=6.
Если отражения разрешены, то принцип тот же самый, хотя там чуть побольше случаев. Но это также быстро вычисляется, и для 3×3 с тремя цветами будет 2862 раскраски.
Источник
Покраска квадрата 8х8 разными цветами.
Сколько способов покрасить шахматную доску с помощью 8 разными цветами так, чтобы:
Ближайшие клетки не были покрашены одним и тем же цветом. В горизонтальной линии были задействованы все 8 цветов.
Вот одна из идей, которые приходят в голову:
Первую полоску мы можем покрасить 8! способами, тогда вторую доску мы можем покрасить X способами, значит всего способов будет 8!*X^7. Тогда как найти, сколькими способами можно покрасить следующую доску? Если цвет №1 будет в крайней клетки, то такой же цвет можно разместить в 6 клетках следующей полосы. А если не в крайней, то в 5 клетках.
Раскрасить 4 треугольника 3-мя разными цветами
Добрый вечер, форумчане!:) Помогите, пожалуйста, найти решение.:) Дан квадрат, разделенный.
Составить программу, которая рисует три квадрата разными цветами
Составить программу, которая рисует три квадрата разными цветами (линии квадратов) и закрашивает.
Как сделать разные тексты разными цветами. Не несколько слов, а разные тексты разными цветами
Этот способ анимации идеально подходит для: анимации трансформаций объекта, анимации.
Вывод разными цветами
Как в java можно вывести ответ разными цветами?? Задача:Вывести разными цветами на экране.
Pruff, Вы на правильном пути.
X — количество перестановок на 8 элементах, не оставляющих на месте ни одного элемента. А эта тема недавно обсуждалась на форуме
Источник
комбинаторика — Сколько существует таких раскрасок?
Каждую клетку доски $%3\times 3$% раскрашивают в один из трёх цветов, причём клетки, имеющие общую сторону, не должны быть одного цвета. К тому же, все три цвета использовать совсем не обязательно. Сколько существует таких раскрасок?
задан 3 Мар 15:32
В задачах на число способов раскраски указывается — считать ли раскраски, полученные при поворотах/симметриях, различными
@spades: здесь не было сказано, поэтому раскраски различны по умолчанию. Но при наличии ограничений получается своя задача, также представляющая интерес. Можно будет потом заодно прикинуть, какие там ответы.
1 ответ
Рассмотрим раскраску четырёх клеток, соседних с центральной. Там присутствует один цвет или два. Разбираем случаи.
1) Все рассмотренные клетки одного цвета. Его выбираем 3 способами. Каждую из оставшихся 5 клеток независимо раскрашиваем в один из двух цветов. Итого 3 * 2^5 = 96.
2) Три рассмотренные клетки одного цвета, одна — другого. Тут 3 способа выбрать цвет, повторяющийся трижды, и 2 способа выбрать оставшийся. Также 4 способа выбрать место для клетки одного цвета. Далее центр раскрашивается однозначно, две угловые клетки тоже, и две угловые — в 2 цвета каждая. Итого 3 * 2 * 4 * 2^2 = 96.
3) Две рассмотренные клетки одного цвета, две другого.
а) Одноцветные клетки идут напротив. Здесь 3 способа выбора горизонтальных, 2 для вертикальных. Остальное однозначно. Это 6 способов.
б) Одноцветные клетки идут по диагоналям. Тут 2 способа выбрать направление диагонали, 3 способа выбора цвета верхней диагонали, 2 для нижней. Два угла раскрашены однозначно, как и центр, два угла — 2 способами каждый. Итого 2 * 3 * 2 *2^2 = 48.
Источник
