Сколькими способами можно составить такую мозаику (с точностью до поворотов и осевых симметрий квадрата)? (1)

@riv94 · Регистрация: 13.02.2011

Author24 — интернет-сервис помощи студентам

Здравствуйте, форумчане

Столкнулся впервые с такой вот задачкой из темы "Задачи на раскраски", "Лемма Бернсайда"..

Условие:
Каждая сторона квадрата разбита на 9 равных частей и через точки деления проведены отрезки, параллельные сторонам квадрата. В получившиеся клеточки вставляют цветные стекла 4 различных цветов. Сколькими способами можно составить такую мозаику (с точностью до поворотов и осевых симметрий квадрата)?

Собственно, в чем проблема) На лекции нам, как это обычно бывает, разобрали до такой степени элементарнейшие задачи и примеры, что я даже не знаю, с какой стороны подступиться к данной задаче...
На паре мы разобрали на примере квадрата, разбитого на 8-мь частей, где все считается элементарным перебором. Но с этой задачей так не прокатит. А посему, надеюсь на Вашу помощь и конструктивные предложения по решению данной задачи.. А еще лучше было бы посмотреть на примеры решения идентичных задач, которые я не смог найти на просторах интернета.
Заранее огроменное спасибо всем, кто откликнется!

@palva · 18.04.2014, 20:39

А разве раздел Лемма Бернсайда это не подсказка?
Сколько всего раскрасок? (Множество X)
Составляют ли повороты и симметрии квадрата группу? (G)
Сколько элементов в G?
Осуществляет ли G действие на X?
Сколько неподвижных точек у каждого элемента из G?
Применяйте лемму Бернсайда.

@riv94 · 19.04.2014, 23:03 **[ТС]**

Я изучил теоретический материал по Лемме Бернсайда и посмотрел пару задач.. Подскажите пожалуйста, как мне для моей задачи определить циклический тип перестановки?) Ведь, насколько я понял, все остальные перестановки будут считатьсяна базе нее..
И еще такой вопрос.. Как спрогнозировать примерно количество возможных циклических перестановок?

@palva · 19.04.2014, 23:19

riv94, Мне непонятны ваши вопросы. В задаче перестановки не фигурируют.

@Alex5 · 20.04.2014, 14:07

Сообщение от riv94

Подскажите пожалуйста, как мне для моей задачи определить циклический тип перестановки

Квадрат состоит из 81 клеточки. Если повернуть квадрат на 90^o, какой перестановке клеточек это соответсвует?

@kabenyuk · 21.04.2014, 16:47

Непростые предстоят вам вычисления. Квадрат имеет 8 движений, совмещающих его с собой. Для каждого движения необходимо вычислить число мозаик, не изменяющихся при этом движении. Скажем, если это поворот на 90, то все такие мозаики получаются из мозаики левого верхнего 5х5 квадратика, а значит самосовмещающихся мозаик при повороте ровно 4^{25} и т.д. для каждого из 8-ми движений. Складываете эти числа и делите на 8. По-моему так.

@riv94 · 25.04.2014, 19:27 **[ТС]**

kabenyuk, я решил эту задачу! Жду проверки... Если решение окажется верным, то непременно поделюсь в теме

@riv94 · 15.05.2014, 15:21 **[ТС]**

Верное решение:
1)
Пронумеруем квадратики
2)
I=81 квадратик
С=4 цвета
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{X}^{e}=\left|X \right|={\left|X \right|}^{\left|I \right|}={4}^{81}$
3)
Рассмотрим повороты:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{\pi /2}: (1,9,81,73)(10,8,72,74)...(31,33,51,49)41$
Всего 21 цикл
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{\pi}: (1,81)(2,80)...(31,51)41$
Всего 41 цикл
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{3\pi/2}: (1,73,81,8)...(31,49,51,33)41$
Всего 21 цикл
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{2\pi}: 1,2,3...81$
Всего 81 цикл
4)
Рассмотрим симметрии:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{m1}:(1,9),(2,8)...(73,81),5,14,23,32,41,50,59,68,77$
Всего 45 циклов
Аналогично составляются последовательности циклов и относительно других осей симметрии!
5)
Считаем стабилизаторы
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left|{Stab}_{x}({R}_{\pi /2}) \right|=\left|{Stab}_{x}({R}_{3\pi /2}) \right|={4}^{21}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left|{Stab}_{x}({R}_{\pi}) \right|={4}^{41}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left|{Stab}_{x}({R}_{2\pi}) \right|={4}^{81}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left|{Stab}_{x}({S}_{m1}) \right|=\left|{Stab}_{x}({S}_{m2}) \right|=\left|{Stab}_{x}({S}_{l1}) \right|=\left|{Stab}_{x}({S}_{l2}) \right|={4}^{45}$
6)
По Лемме Бернсайда
$https://www.cyberforum.ru/cgi-bin/latex.cgi?N=\frac{1}{\left|G \right|}*\left|{Stab}_{x}(g) \right|=\frac{1}{8}({4}^{81}+{4}^{41}+2{4}^{21}+4*{4}^{45})$

@Aprenta · 27.04.2020, 01:22

Здравствуйте! Подскажите, пожалуйста, почему $https://www.cyberforum.ru/cgi-bin/latex.cgi?{24}^{21}$ ? Почему именно 24? $https://www.cyberforum.ru/cgi-bin/latex.cgi?4*{4}^{45}$ - это т.к. 4 оси симметрии - так?

@kabenyuk · 27.04.2020, 06:28

Сообщение от Aprenta

Почему именно 24?

Не 24, а 2*4²¹.

@Aprenta · 27.04.2020, 11:35

Вот я тоже так думала) Спасибо большое!

Новые блоги и статьи Все статьи Все блоги /
Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .

@riv94 66 / 66 / 29 Регистрация: 13.02.2011 Сообщений: 392

	Сколькими способами можно составить такую мозаику (с точностью до поворотов и осевых симметрий квадрата)? (1) 18.04.2014, 19:57. Показов 4548. Ответов 10 Метки нет (Все метки) Здравствуйте, форумчане Столкнулся впервые с такой вот задачкой из темы "Задачи на раскраски", "Лемма Бернсайда".. Условие: Каждая сторона квадрата разбита на 9 равных частей и через точки деления проведены отрезки, параллельные сторонам квадрата. В получившиеся клеточки вставляют цветные стекла 4 различных цветов. Сколькими способами можно составить такую мозаику (с точностью до поворотов и осевых симметрий квадрата)? Собственно, в чем проблема) На лекции нам, как это обычно бывает, разобрали до такой степени элементарнейшие задачи и примеры, что я даже не знаю, с какой стороны подступиться к данной задаче... На паре мы разобрали на примере квадрата, разбитого на 8-мь частей, где все считается элементарным перебором. Но с этой задачей так не прокатит. А посему, надеюсь на Вашу помощь и конструктивные предложения по решению данной задачи.. А еще лучше было бы посмотреть на примеры решения идентичных задач, которые я не смог найти на просторах интернета. Заранее огроменное спасибо всем, кто откликнется! 0

@palva 4256 / 2952 / 688 Регистрация: 08.06.2007 Сообщений: 9,862 Записей в блоге: 4
	18.04.2014, 20:39
	А разве раздел Лемма Бернсайда это не подсказка? Сколько всего раскрасок? (Множество X) Составляют ли повороты и симметрии квадрата группу? (G) Сколько элементов в G? Осуществляет ли G действие на X? Сколько неподвижных точек у каждого элемента из G? Применяйте лемму Бернсайда. 0

@riv94 66 / 66 / 29 Регистрация: 13.02.2011 Сообщений: 392
	19.04.2014, 23:03 [ТС]
	Я изучил теоретический материал по Лемме Бернсайда и посмотрел пару задач.. Подскажите пожалуйста, как мне для моей задачи определить циклический тип перестановки?) Ведь, насколько я понял, все остальные перестановки будут считатьсяна базе нее.. И еще такой вопрос.. Как спрогнозировать примерно количество возможных циклических перестановок? 0

@palva 4256 / 2952 / 688 Регистрация: 08.06.2007 Сообщений: 9,862 Записей в блоге: 4
	19.04.2014, 23:19
	riv94, Мне непонятны ваши вопросы. В задаче перестановки не фигурируют. 0

@Alex5 1130 / 789 / 232 Регистрация: 12.04.2010 Сообщений: 2,012
	20.04.2014, 14:07
	Сообщение от riv94 Подскажите пожалуйста, как мне для моей задачи определить циклический тип перестановки Квадрат состоит из 81 клеточки. Если повернуть квадрат на 90^o, какой перестановке клеточек это соответсвует? 0

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	21.04.2014, 16:47
	Непростые предстоят вам вычисления. Квадрат имеет 8 движений, совмещающих его с собой. Для каждого движения необходимо вычислить число мозаик, не изменяющихся при этом движении. Скажем, если это поворот на 90, то все такие мозаики получаются из мозаики левого верхнего 5х5 квадратика, а значит самосовмещающихся мозаик при повороте ровно 4^{25} и т.д. для каждого из 8-ми движений. Складываете эти числа и делите на 8. По-моему так. 1

@riv94 66 / 66 / 29 Регистрация: 13.02.2011 Сообщений: 392
	25.04.2014, 19:27 [ТС]
	kabenyuk, я решил эту задачу! Жду проверки... Если решение окажется верным, то непременно поделюсь в теме 0

@riv94 66 / 66 / 29 Регистрация: 13.02.2011 Сообщений: 392
	15.05.2014, 15:21 [ТС]
	Верное решение: 1) Пронумеруем квадратики 2) I=81 квадратик С=4 цвета $https://www.cyberforum.ru/cgi-bin/latex.cgi?{X}^{e}=\left\|X \right\|={\left\|X \right\|}^{\left\|I \right\|}={4}^{81}$ 3) Рассмотрим повороты: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{\pi /2}: (1,9,81,73)(10,8,72,74)...(31,33,51,49)41$ Всего 21 цикл $https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{\pi}: (1,81)(2,80)...(31,51)41$ Всего 41 цикл $https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{3\pi/2}: (1,73,81,8)...(31,49,51,33)41$ Всего 21 цикл $https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{2\pi}: 1,2,3...81$ Всего 81 цикл 4) Рассмотрим симметрии: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{m1}:(1,9),(2,8)...(73,81),5,14,23,32,41,50,59,68,77$ Всего 45 циклов Аналогично составляются последовательности циклов и относительно других осей симметрии! 5) Считаем стабилизаторы $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\|{Stab}_{x}({R}_{\pi /2}) \right\|=\left\|{Stab}_{x}({R}_{3\pi /2}) \right\|={4}^{21}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\|{Stab}_{x}({R}_{\pi}) \right\|={4}^{41}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\|{Stab}_{x}({R}_{2\pi}) \right\|={4}^{81}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\|{Stab}_{x}({S}_{m1}) \right\|=\left\|{Stab}_{x}({S}_{m2}) \right\|=\left\|{Stab}_{x}({S}_{l1}) \right\|=\left\|{Stab}_{x}({S}_{l2}) \right\|={4}^{45}$ 6) По Лемме Бернсайда $https://www.cyberforum.ru/cgi-bin/latex.cgi?N=\frac{1}{\left\|G \right\|}\left\|{Stab}_{x}(g) \right\|=\frac{1}{8}({4}^{81}+{4}^{41}+2{4}^{21}+4{4}^{45})$ Миниатюры 1

@Aprenta 0 / 0 / 0 Регистрация: 27.04.2020 Сообщений: 2
	27.04.2020, 01:22
	Здравствуйте! Подскажите, пожалуйста, почему $https://www.cyberforum.ru/cgi-bin/latex.cgi?{24}^{21}$ ? Почему именно 24? $https://www.cyberforum.ru/cgi-bin/latex.cgi?4*{4}^{45}$ - это т.к. 4 оси симметрии - так? 0

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	27.04.2020, 06:28
	Сообщение от Aprenta Почему именно 24? Не 24, а 2*4²¹. 1

@Aprenta 0 / 0 / 0 Регистрация: 27.04.2020 Сообщений: 2
	27.04.2020, 11:35
	Вот я тоже так думала) Спасибо большое! 0