Pizzas não equivalentes


177
views
1
5 weeks ago by

Em uma pizzaria, cada pizza é dividida em n pedaços congruentes, e cada pedaço pode conter um dos m sabores disponíveis.

Utilizando ação de grupos, determine de quantas maneiras não equivalentes pode ser feita a escolha de uma pizza.

 

a) \(\frac{1}{n}\sum\limits_{i=1}^n\varphi(i)m^{i}\)

b) \(\frac{m^n}{n!}\)

c) \(\frac{1}{n}\sum\limits_{i|n}\varphi(i)m^{\frac{n}{i}}\)

d)  \(\frac{1}{2n}\sum\limits_{i=1}^n\varphi(i)m^{i}\)

onde \(\varphi( \cdot )\) é a função de Euler usual.

 

 

add commentfollow this post modified 5 weeks ago by Someone   • written 5 weeks ago by Luciano Renato  

4 Answers


2
5 weeks ago by

Se considerarmos a ação la do cíclico de ordem n gerado por (12...n) elemento de Sn ,então eu percebi que temos o seguinte padrão(ainda preciso provar ele,é APENAS uma ideia)
Pega o fix(g^i ) ,todo vetor que ta nesse conjunto ,tem a forma (a1....an) ,mas esses carinhas a1 ,a2...an tem uma disposição especial,eles aparecem repetidos de acordo com a ordem de g^i 
se a ordem de g^i é d ,então vc terá n/d repetições de termos,exemplo
A ordem de (12345)² é 3 ,então os vetores no fix((123456)²) são da forma (ababab) (3 repetições ab)
Sendo assim,pra cada divisor d da ordem n ,temos q^(n/d) elementos,mas nós temos exatamente phi(d) elementos de ordem d no grupo,isso implica que temos a soma de phi(d) . q^(n/d) elementos pra cada divisor d de n,tudo isso dividido por n,que é a ordem do grupo.
letra c)

add comment written 5 weeks ago by PulgaAtrásDaOrelha  
1
5 weeks ago by

Só tentando formalizar as ideais:

 


Vamos considerar o conjunto das pizzas com \(n\) pedaços e \(m\) sabores como sendo o \(\mathbb{F}_m^n\), ou seja, cada pizza é uma n-upla em que cada entrada pode assumir um valor de \(\{\overline{0},...,\overline{m-1}\}\). Vamos denotar uma pizza genérica por \((a_1,\ldots,a_n)\).

 


Considere o grupo \(G = \langle (1 2 \ldots n) \rangle \leq S_n\), por simplicidade denotemos \(g = (1 2 \ldots n)\), então \(G = \{g, g^2, \ldots, g^n\}\). Definimos então a ação de \(G\) sobre \(\mathbb{F}_m^n\) da seguinte forma:

 \[ g(a_1,\ldots,a_n) = (a_2,\ldots,a_n, a_1)\]

 
Dado um elemento qualquer \(g^i\in G\), com ordem \(o(g^i) = d\), como \(\langle g^i \rangle\) é um subgrupo de \(G\) de ordem \(d\), então, por Lagrange, \(d|n\).

 
Analisemos agora quantos elementos existem no conjunto \(Fix(g^i)\). Os elementos de \(Fix(g^i)\) são as n-uplas tais que \(g^i(a_1,\ldots,a_n) = (a_1,\ldots,a_n)\), agindo com \(g^i\) sucessivas vezes em ambos os lados da equação obtemos:

 


\[g^i(a_1,\ldots,a_n)  =  (a_1,\ldots,a_n)\]

\[g^{2i}(a_1,\ldots,a_n)  =  g^i(a_1,\ldots,a_n)\]

\[g^{3i}(a_1,\ldots,a_n)  =  g^{2i}(a_1,\ldots,a_n)\]

\[\vdots\]

\[g^{di}(a_1,\ldots,a_n)  =  g^{(d-1)i}(a_1,\ldots,a_n)\]

 Lembrando que \(g^{di} = e\)

 


Da primeira equação obtemos \(a_1 = a_{\overline{1+i}}\), da segunda obtemos \( a_{\overline{1+i}} = a_{\overline{1+2i}}\), e assim por diante, então enfim temos:

 


\[a_1 = a_{\overline{1+i}} = a_{\overline{1+2i}} =\ldots = a_{\overline{1+(d-1)i}}\]

 


Sabemos que todos os índices dos elementos dessa igualdade são diferentes, pois a ordem de \(g^i\) é \(d\). Então temos que esses \(d\) elementos da nossa n-upla precisam ser iguais para a n-upla estar em \(Fix(g^i)\). Podemos tomar agora um índice \(j\) diferente de todos os que aparecem na igualdade e repetir o processo, teremos então:

 


\[a_j = a_{\overline{j+i}} = a_{\overline{j+2i}} =\ldots = a_{\overline{j+(d-1)i}}\]

 


Pelo mesmo argumento todos esses índices são diferentes entre si, e além disso nenhum dos índices pode ser igual a qualquer dos índices da primeira igualdade, caso contrário continuaríamos agindo com \(g^i\) e nunca voltariamos para \(a_ j\), já que por hipótese ele é diferente de todos os índices da igualdade anterior.

 


Podemos repetir esse processo tomando um novo índice que não está em nenhuma das igualdades anteriores, até não termos mais índices para tomar, assim teremos um conjunto de \(n/d\) igualdades cada uma com \(d\) índices, então temos \(n/d\) graus de liberdade nas entradas das n-uplas, como cada entrada pode assumir \(m\) valores, temos que \(|Fix(g^i)| = m^{n/d}\).

 
Por fim, como existem \(\phi(d)\) elementos de ordem \(d\) em \(G\), temos que a soma das ordens de todos os conjuntos \(Fix\) será \(\sum_{d|n} \phi(d)m^{n/d}\), então aplicando o lema de burnside (sendo \(|G| = n\)) temos que o numero de pizzas não equivalentes é:

 
\[\frac{1}{n}\sum_{d|n} \phi(d)m^{n/d}\]

add comment modified 5 weeks ago by Someone   • written 5 weeks ago by Someone  

Eu raciocinei da mesma forma, mas cheguei a uma fórmula diferente.
Observe que (usando a mesma notação que vc) temos que \(d = n/mdc(i, n)\). Portanto teremos que
\[ |Fix(g^i)| = m^{mdc(i, n)} \]

Pelo Lema de Burnside (e pelo fato de \(G\) ser cíclico), teremos que o número de pizzas será:
\[ \frac{1}{n}\sum_{i=1}^{n} m^{mdc(i,n)} \]

Perdão se cometi algum erro em contas.

written 5 weeks ago by José Fernando Barbosa Boro  
1

Parece estar certo também, pois para cada valor possível de \(d = n/mdc(i,n)\), com \(1\leq i \leq n\), teremos \(\phi(d)\) elementos com essa ordem no grupo, alem disso notando que mdc(i,n) = n/d  teremos que

\[ \frac{1}{n}\sum_{d|n} \phi(d)m^{n/d} = \frac{1}{n}\sum_{i=1}^n m^{mdc(i,n)}\]

 

written 5 weeks ago by Someone  
0
5 weeks ago by

Só uma pergunta, as pizzas A e B são equivalentes se:

(a) "Rotacionando" A temos que A e B tem exatamente a mesma disposição de pedaços (ou seja, os pedaços estão fixos na pizza).

ou

(b) Reorganizando os pedaços de A podemos obter B (nesse caso os pedaços estão cortados e podemos trocar a posicão de quaisquer dois pedaços)

 

add comment written 5 weeks ago by Someone  
Só complementando, na letra (a) pode ser adicionado a reflexão também (estou considerando a ação do diedral)
written 5 weeks ago by Felipe César Freitas Monteiro  

É, eu devia ter definido o que era ser equivalente. Mas é essa ideia de rotação mesmo, como em (a).

written 5 weeks ago by Luciano Renato  
0
5 weeks ago by

Sua ideia está correta! Tente usar os seguintes fatos pra formalizar sua resposta (além de definir sua ação), aplicando Burnside:

Se G = <a> é cíclico de ordem n e d|n, então existe um único subgrupo H de G tal que |H| = d. A saber,  $H=$H=$a^{\frac{n}{d}}$and  >. 

Além disso, existem d elementos nesses subgrupos, porém apenas  $\phi\left(d\right)$ϕ(d)  deles têm ordem exatamente d.

 

add comment written 5 weeks ago by Luciano Renato  
Please log in to add an answer/comment or follow this question.

Share this question


Similar posts:
Search »