Сколькими способами можно составить такую мозаику (с точностью до поворотов и осевых симметрий квадрата)? (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

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

Новые блоги и статьи Все статьи Все блоги /
Сайт компании Red-Star-Soft переехал на новый хостинг! Etyuhibosecyu 06.03.2025 Как и советовал Rius, я покинул хостинг от "Ru-Center" и перенес сайт red-star-soft. com на хостинг с более позитивными отзывами (спойлер: найти его было далеко не просто) (чтобы прочитать текст,. . .	Альтернативная сериализация в Java: сравнение Kryo, Protobuf и Avro Jamaican 06.03.2025 Сериализация — один из краеугольных процессов в Java-разработке. Превращение объектов в поток байтов для хранения или передачи по сети с последующим восстановлением звучит просто, но реализация этого. . .	Битва Java-кешей: Сравниваем Ehcache, Caffeine и Hazelcast Jamaican 06.03.2025 Производительность — вечный Святой Грааль для Java-разработчиков. Мы оптимизируем алгоритмы, настраиваем JVM, распараллеливаем процессы, но неизменно приходим к одному и тому же средству ускорения —. . .	Параметры подтверждения сообщения Kafka Jamaican 06.03.2025 Среди распределённых систем и высоконагруженных приложений Apache Kafka занимает особое место. Эта платформа потоковой обработки данных давно стала стандартом де-факто для организаций, которым. . .	Оптимизация времени запуска Spring Boot Jamaican 06.03.2025 Вы когда-нибудь сидели, барабаня пальцами по столу, пока ваше Spring Boot приложение медленно поднимается? Этот момент, когда вы успеваете сходить за кофе, пообщаться с коллегами и вернуться, а. . .
Деплой Kubernetes в Java: масштабирование Spring Boot приложений Jamaican 06.03.2025 Когда ваше Spring Boot приложение внезапно получает всплеск трафика или требует плавного обновления без простоя — традиционные методы деплоя часто пасуют. Именно здесь на сцену выходит Kubernetes —. . .	Бессерверные приложения Java: сравнение AWS Lambda и Azure Functions Jamaican 06.03.2025 Что такое "бессерверные приложения" и почему они так привлекательны? Вопреки названию, серверы никуда не исчезли — просто теперь управление инфраструктурой перекладывается на плечи облачного. . .	Безопасность микросервисов с OAuth2 и OpenID Connect Jamaican 06.03.2025 С ростом популярности микросервисов растут и проблемы, связанные с их безопасностью. В отличие от монолитных приложений, где безопасность можно было обеспечить централизованно, микросервисная. . .	Структурное логирование в Spring Boot Jamaican 06.03.2025 Представьте, что вы управляете сотней микросервисов в продакшн-среде. Внезапно один из сервисов начинает давать сбои, и вам нужно срочно выяснить причину. Вы открываете логи и видите бесконечные. . .	Предотвращение XSS, CSRF и SQL-инъекций в JavaScript bytestream 05.03.2025 В эпоху цифровизации безопасность веб-приложений становится не просто рекомендацией, а жизненной необходимостью. Если вы разрабатываете приложения на JavaScript, вам наверняка знакома эта. . .

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

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

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

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

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

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

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

@riv94 66 / 66 / 29 Регистрация: 13.02.2011 Сообщений: 392
	15.05.2014, 15:21 [ТС]	8
	Верное решение: 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	9
	Здравствуйте! Подскажите, пожалуйста, почему $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 / 919 Регистрация: 19.11.2012 Сообщений: 6,196
	27.04.2020, 06:28	10
	Сообщение от Aprenta Почему именно 24? Не 24, а 2*4²¹. 1

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