2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Раскраска флагов
Сообщение20.05.2018, 05:28 
Аватара пользователя


07/01/15
1145
Бородатая задача. Есть $q$ красок различных цветов. Сколькими способами можно покрасить полосатый флаг, имеющий $n$ полос одинаковой ширины?

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 10:55 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Если требуется, чтобы все полосы были разного цвета, то ответ очевиден. Предполагается, наверное, что полосы могут быть и одноцветными? И даже соседние? И даже все?

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 10:59 
Аватара пользователя


07/01/15
1145
Да, различные полосы могут быть одноцветными. Кроме того, флаг можно перевертывать, т. е. флаги с "палиндромальными" раскрасками считаются одинаковыми.

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 11:08 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Это что, у Индонезии и Польши одинаковые флаги? А сколько ругани было по поводу перепута бесикра и красиба :-)

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 12:41 
Аватара пользователя


07/01/15
1145
gris в сообщении #1313609 писал(а):
Это что, у Индонезии и Польши одинаковые флаги?

Будем считать, что флаги негосударственные.

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 13:02 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Извините за занудство, но в задаче основная трудность это понять требования к флагам. Вот могут ли быть соседние полосы одного цвета? Вы написали, что любая полоса может быть любого цвета. Тогда решение тоже очевидно. Впрочем, как и когда соседние полосы обязательно разного цвета. Остаётся учесть симметричные флаги. Это тоже сделать нетрудно, поанализировав верхнюю половинку флага. Учесть ещё чётность количества полос.

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 13:55 
Аватара пользователя


07/01/15
1145
gris в сообщении #1313635 писал(а):
Вы написали, что любая полоса может быть любого цвета. Тогда решение тоже очевидно. Впрочем, как и когда соседние полосы обязательно разного цвета. Остаётся учесть симметричные флаги. Это тоже сделать нетрудно, поанализировав верхнюю половинку флага. Учесть ещё чётность количества полос.

Да, задача нетрудная. Я изначально задумывал топик так, чтобы он был про миниатюру, не более.

gris в сообщении #1313635 писал(а):
Извините за занудство, но в задаче основная трудность это понять требования к флагам.

У меня сразу возникли аллюзии ко всем тем топикам dxdy, где люди на нескольких страницах выясняли, о чем же идет речь. И ведь они иногда достигали этой цели! Надеюсь, этот топик не будет исключением)

P.S. На самом деле, я надеялся, что кто-то представит теоретико-групповое решение задачи. Учитывая, что граждане dxdy весьма любят палить из пушек по воробьям.)

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 15:02 
Аватара пользователя


07/01/15
1145
P. P. S. И да, решение, которое я подразумевал, я постараюсь выложить в ближайшее время.

 Профиль  
                  
 
 Re: Покраска флагов
Сообщение20.05.2018, 15:10 
Аватара пользователя


14/12/17
1471
деревня Инет-Кельмында
То есть было бы $q^n$, если бы не условие что перевернутые флаги считать как один.

 Профиль  
                  
 
 Re: Раскраска флагов
Сообщение20.05.2018, 15:14 
Заслуженный участник


09/05/12
25179
 i  Тема переименована по просьбе ее автора.

 Профиль  
                  
 
 Re: Раскраска флагов
Сообщение20.05.2018, 17:06 
Аватара пользователя


07/01/15
1145
eugensk в сообщении #1313664 писал(а):
То есть было бы $q^n$, если бы не условие что перевернутые флаги считать как один.

Да, если бы перевернутые не считать как один, то было бы так.

 Профиль  
                  
 
 Re: Раскраска флагов
Сообщение20.05.2018, 17:23 
Заслуженный участник
Аватара пользователя


13/08/08
14430
SomePupil, предлагаю теоретико-числовую интерпретацию задачи: сколько существует неотрицательных целых чисел длины(или как там у них? ) не больше $n$ в $q$-ричной позиционной системе? А сколько из них палиндромов с учётом ведущих нулей. Первый ответ уже дали. Попробую определить количество палиндромов.
Пусть $n=2k$. Существует $q^k$ различных верхних половинок флагов и столько же отражённых палиндромов. Пусть $n=2k+1$. Средняя полоса не входит ни в одну половинку и может быть окрашена в любой цвет. То есть будет $q^{k+1}$ палиндромов. Палиндром не образует пары. А каждый непалиндром имеет перевёрнутую пару. Объединяя, получим итоговую формулу. $N=q^n - \frac12(q^n-q^{\lceil {n/2}\rceil})=\frac12(q^n+q^{\lceil {n/2}\rceil})$
Проверим. $q=1;n=n: N=1$ Верно. Один цвет — один флаг.
$q=2;n=2: N=3$ Верно. $q=q;n=1: N=q$ Верно.

 Профиль  
                  
 
 Re: Раскраска флагов
Сообщение21.05.2018, 02:05 
Аватара пользователя


07/01/15
1145
Пусть $(s_1, s_2, \ldots, s_n),\; s_i \in \{1, 2, \ldots, n\}$ обозначают раскраски. Введем группу $G = \{e, f\}$ из тождественного элемента и флипа, и пусть эта группа действует на раскраски таким образом: $f(s_1, s_2, \ldots, s_{n-1}, s_n) = (s_n, s_{n-1}, \ldots, s_2, s_1).$ Различные раскраски в точности соответствуют орбитам этого действия. Количество орбит-раскрасок равно $$C = \frac1{|G|}\sum_{g\in G}S(g),$$
где $S(g) -$ количество элементов-раскрасок, которые $g$ переводит в себя, $|G| = 2 -$ кол-во элементов в группе. Тождественный элемент $e$ переводит все раскраски в себя $S(e) = q^n.$ Флип же переводит в себя только палиндромальные раскраски, поэтому $S(f) = q^{\lceil \frac{n}2\rceil}.$ Следовательно, $$C = \frac12 \left(q^n + {q^{\lceil\frac{n}{2}\rceil}\right),$$
что совпадает с ответом gris.
Теги: лемма Бернсайда, действия групп, их орбиты.

 Профиль  
                  
 
 Re: Раскраска флагов
Сообщение21.05.2018, 12:26 
Заслуженный участник
Аватара пользователя


13/08/08
14430
SomePupil, выкатили Ваше орудие? Только сначала чисто комбинаторным сачком отловили воробьёв, рассадили их по двум мешкам, затолкали в групповую пушку и выстрелили не по воробьям, а воробьями. Чисто по-Китайски :-)
На самом деле получилась симпатичная иллюстрация к Лемме Бёрнсайда. Изменим немного требования к флагам: соседние полосы разноцветны. Тоже легко посчитать ингредиенты формулы. С необходимостью использовать ровно $k$ цветов и т.п. Тут чуть сложнее. А можно считать одинаковыми флаги с циклической перестановкой цветов (то есть ожерелья).
В общем, задача Ваша действительно показывает необыкновенную красоту приложений теории групп.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group