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

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

Новые блоги и статьи
Что такое HCL Notes и как с ним работать InfoMaster 10.01.2025 HCL Notes (ранее известный как IBM Notes и Lotus Notes) представляет собой комплексную платформу для совместной работы и обмена информацией в корпоративной среде. Это многофункциональное решение,. . .	Как работать с Git из Windows и Visual Studio InfoMaster 10.01.2025 Работа с Git в Windows Работа с Git в операционной системе Windows может быть осуществлена с помощью различных инструментов, каждый из которых обладает своими уникальными возможностями и. . .	Аналог оператора switch case в Python InfoMaster 10.01.2025 Оператор switch case используется в программировании для выбора одного из нескольких вариантов исполнения кода. Однако в языке Python этот оператор отсутствует. Понимание аналогов switch case в. . .	Отличия абстрактного класса от интерфейса InfoMaster 10.01.2025 В современной разработке программного обеспечения существуют два основных механизма реализации абстракции: абстрактные классы и интерфейсы. Эти инструменты, хотя и схожи в своей основной цели -. . .	Как работать в Git InfoMaster 10.01.2025 Git — это одна из наиболее популярных систем контроля версий, которая активно используется разработчиками по всему миру. Она позволяет эффективно управлять изменениями в коде, координировать работу. . .	Реализация передвижения персонажа в Unity3d на C# InfoMaster 10.01.2025 Реализация передвижения персонажа в Unity3D начинается с правильной настройки проекта. Этот этап критически важен для создания отзывчивого и плавного управления. Рассмотрим основные шаги для создания. . .
Docker: руководство для начинающих InfoMaster 10.01.2025 В современном мире разработки программного обеспечения контейнеризация стала неотъемлемой частью процесса создания и развертывания приложений. Docker, как ведущая платформа контейнеризации, произвела. . .	Книги и учебные ресурсы по C# InfoMaster 08.01.2025 Базовые учебники и руководства Одной из лучших книг для начинающих является "C# 10 и . NET 6 для начинающих" Эндрю Троелсена и Филиппа Джепикса . Книга последовательно раскрывает основные концепции. . .	Что такое NullReferenceException и как исправить? InfoMaster 08.01.2025 NullReferenceException - одно из самых распространенных исключений, с которым сталкиваются разработчики на C#. Это исключение возникает при попытке обратиться к членам объекта (методам, свойствам или. . .	Что такое Null Pointer Exception (NPE) и как это исправить? InfoMaster 08.01.2025 Null Pointer Exception (NPE) - это одно из самых распространенных исключений в Java, которое возникает при попытке использовать ссылку на объект, значение которой равно null. Это исключение относится. . .	Русский язык в консоли C++ InfoMaster 08.01.2025 При разработке программ на C++ одной из частых проблем, с которой сталкиваются русскоязычные программисты, является корректное отображение кириллицы в консольных приложениях. Эта проблема особенно. . .	Telegram бот на C# InfoMaster 08.01.2025 Разработка ботов для Telegram стала неотъемлемой частью современной экосистемы мессенджеров. C# предоставляет мощный и удобный инструментарий для создания разнообразных ботов, от простых. . .

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

@palva 4256 / 2952 / 688 Регистрация: 08.06.2007 Сообщений: 9,859 Записей в блоге: 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,859 Записей в блоге: 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

	27.04.2020, 11:35

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