2014 dxdy logo

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

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




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


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

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


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

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


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

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


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

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


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

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

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


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

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


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

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

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

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

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

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


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

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


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

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


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

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


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

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

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


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

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

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



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

Сейчас этот форум просматривают: Shadow


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

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