MO640 - Soluções - Sobre a aula de 2007-04-16

Liste as 41 permutações fáceis de tamanho n = 5.

Solução:

De acordo com a seção 3.3 de (Fortuna 2005):

Definição: Uma permutação π é considerada fácil se, e somente se,

(1)	d_p(π) = (b_p(π) - 1)/2

Isto implica em um número ímpar de pontos de quebra de prefixo.

E pelo Teorema 3.9: Uma permutação π é fácil se, e somente se, já está ordenada ou existe uma transposição de prefixo τ tal que

(2)	b_p(πτ) = b_p(π) - 2 e π τ é fácil

τ retirará portanto dois pontos de quebra de prefixo.

Na tabela ao lado, as permutações à esquerda originam as correspondentes à direita.
Um ponto indica quebra de prefixo
As cores e o sublinhado indicam os trechos onde a transposição foi aplicada.

A estratégia é partir da identidade (permutação fácil) e aplicar uma permutação que acrescente dois pontos de quebra de prefixo.
Os locais onde a permutação será "cortada" não podem conter um ponto de quebra, excetuando-se o primeiro, caso contrário não são criados dois novos pontos de quebra.

Identidade	d=1	d=2
0.1 2 3 4 5	0.2.1.3 4 5	0.4.2.1.3.5
		0.4 5.2.1.3.
		0.5.2.1.3 4.
	0.2 3.1.4 5	0.5.2 3.1.4.
		0.3.1.4 5.2.
		0.3.1.4.2.5
	0.2 3 4.1.5	0.3.2.4.1.5
		0.4.1.5.2 3.
		0.3 4.1.5.2.
	0.2 3 4 5.1.	0.3.2.4 5.1.
		0.4.2 3.5.1.
		0.3 4.2.5.1.
	0.3.1 2.4 5	0.2.4.3.1.5
		0.5.3.1 2.4.
		0.2.4 5.3.1.
	0.3 4.1 2.5	0.4.1.3.2.5
		0.2.5.3 4.1.
		0.4.1 2.5.3.
	0.3 4 5.1 2.	0.4.3.5.1 2.
		0.5.1.3 4.2.
		0.4 5.1.3.2.
	0.4.1 2 3.5	0.2.4.1.3.5
		0.2 3.5.4.1.
		0.3.5.4.1 2.
	0.4 5.1 2 3.	0.5.1 2.4.3.
		0.5.1.4.2 3.
		0.2.4 5.1.3.
	0.5.1 2 3 4.	0.2.5.1.3 4.
		0.2 3.5.1.4.
		0.3.5.1 2.4.

Mostre que a Conjectura 3.15, da página 43 da dissertação de Fortuna (2005) é equivalente à seguinte afirmação: para toda permutação π, temos:
d_p(π) ≤ ⌈ n/4 + (b_p(π) - 1)/2 ⌉.

Solução:

Conjectura 3.15: Para toda permutação π de comprimento n existe uma permutação fácil π', tal que

(3) b_p(π') = b_p(π) - k

e

(4) d_p(π,π') ≤ ⌈ n/4 + k/2 ⌉

Partindo da afirmação:

Tomamos π' como sendo a identidade: π' = ι

Por (3), temos então que k = b_p(π) - b_p(π') = b_p(π) - 1 e

a distância d_p(π) = d_p(π,ι) = d_p(π,π'). Donde

d_p(π,π') ≤ ⌈ n/4 + (b_p(π) - 1)/2 ⌉ = ⌈ n/4 + k/2 ⌉

d_p(π,π') ≤ ⌈ n/4 + k/2 ⌉

Partindo agora da conjectura:

Pela desigualdade triangular, temos que: d_p(π) - d_p(π') ≤ d_p(π,π'). Usando a conjectura e o fato de π' ser fácil,

d_p(π) ≤ ⌈ n/4 + k/2 ⌉ + (b_p(π') - 1)/2

Como a distância é um número inteiro e definida por (1), o termo (b_p(π') - 1)/2 pode entrar na função teto.

d_p(π) ≤ ⌈ n/4 + k/2 + (b_p(π') - 1)/2 ⌉ = ⌈ n/4 + (k + b_p(π) - k - 1)/2 ⌉

Simplificamos e obtemos:

d_p(π) ≤ ⌈ n/4 + b_p(π) - 1)/2 ⌉

MO640 Home

(3)	b_p(π') = b_p(π) - k
e
(4)	d_p(π,π') ≤ ⌈ n/4 + k/2 ⌉