Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Para quais n's posso rearranjar {0, 0, 1, 1, ..., n-1, n-1} como pares de Langford?

+6 votos
65 visitas
perguntada Mai 28 em Ciência da Computação por Pablo Castro (286 pontos)  

Este é o exercício 2 da página 36 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms (Donald E. Knuth):

For which \(n\) can \( \{0, 0, 1, 1, ..., n-1, n-1\} \) be arranged as Langford pairs?

Importante: antes de iniciar a questão, é interessante ver a resolução deste exercício com a implementação do algoritmo para encontrar as sequências de Langford para determinado n.

Compartilhe

1 Resposta

+6 votos
respondida Mai 29 por Pablo Castro (286 pontos)  

Primeiramente, lembremos que um par de Langford \(L(2,n)\) são todas as sequências geradas com os elementos \(\{1, 2, ..., n\}\) que atendam aos seguintes requisitos:
1. cada elemento \(k \in \{1, 2, ..., n\} \) deve aparecer duas vezes;
2. Deve haver \(k\) elementos diferentes de \(k\) entre a sua primeira e segunda aparição.
Ou seja, temos \(2n\) elementos em cada par de Langford.

Agora vamos ao exercício. Com ajuda da implementação do exercício anterior, iremos encontrar para quais \(n\)'s conseguimos gerar os pares de Langford.

def langford(n, seq):
n1 = n - 1
for i in range(len(seq) - n - 1):
    j = i + n + 1
    if not (seq[i] or seq[j]):
        seq[i] = seq[j] = n
        if not (n1 == 0):
            yield from langford(n1, seq)
        else:
            yield seq[:]
        seq[i] = seq[j] = 0 


if __name__ == '__main__':
    my_nlist = []
    for i in list(range(13)): 
        # solutions retorna a quantidade de pares de Langford
        # gerados por langford(n, seq)
        solutions = sum(1 for _ in langford(i, [0]*2*i)) 
        if solutions != 0:
            my_nlist.append(i)
        else:
            pass
    print(my_nlist)

O output é:

[3, 4, 7, 8, 11, 12] 

Note que, por ser um infinito, não conseguimos verificar para todo \(n \in \mathbb{N}\). Porém, o output nos revela um padrão: conseguimos pares de Langford para \(n\)'s múltiplos de 4 e para o natural imediatamente anterior. Ou seja, todo \(n\) tal que \(n \% 4\) = 0 ou \(n \% 4 = 3\) conseguimos rearranjá-los como pares de Langford. Isso pode ser mostrado matematicamente.

Seja \(a_k\) a posição onde o elemento \(k\) aparece pela primeira vez e \(b_k\) a posição que aparece pela segunda vez. Sabemos que \(b_k = a_k + k + 1\). Somando todas as posições temos:

\[ \begin{eqnarray} \sum_k a_k + \sum_k b_k = & 1 + 2 + ... + 2n \\ \sum_k a_k + \sum_k (a_k + k + 1) = & 1 + 2 + ... + 2n \\ 2 \sum_k a_k + \sum_k k + n = & 1 + 2 + ... + 2n \\ 2 \sum_k a_k + \frac{n(n+1)}{2} + n = & n(2n+1) \end{eqnarray} \]

Rearranjando, temos:

\[ \sum_k a_k = \frac{3n^2 -n}{4} \tag{1} \]

Sabemos que o LHS da equação precisa ser um número inteiro, logo o RHS também deve ser. Para confirmamos o padrão visto acima, então (1) precisa ser (i) múltiplo de 4 ou, (ii) ao dividir por 4, ter resto 3. A primeira afirmação é direta, já que a expressão está sendo dividida por 4. Vamos analisar a segunda afirmação.

Considere \( \frac{n}{4} = z + \frac{3}{4} \) para algum \(z\) inteiro, assim garantimos que o resto ao dividir por 4 seja 3. A partir daí também temos que \( \frac{n}{2} = 2z + \frac{3}{2} \). Vamos substituir esses valores em (1):

\[ \begin{eqnarray} \sum_k a_k = \frac{3n^2 - n}{4} = & 3(\frac{n}{2})^2 - \frac{n}{4} \\ = & 3(2z + \frac{3}{2})^2 - (z + \frac{3}{4}) \\ = & 3(4z^2 + 6z + \frac{9}{4}) - z - \frac{3}{4} \\ = &12z^2 + 17z + 6 \end{eqnarray} \]

Que é um número inteiro, já que \(z\) é inteiro. Isso explica o padrão observado no nosso output.

comentou Jun 7 por Adriana Molinari (111 pontos)  
Diferentemente do exercício ao qual a resolução faz referência, este exercício pede que os pares também contenham os elementos {0, 0}. Porém isso não altera o resultado, já que {0,0} sempre devem aparecer juntos (nenhum outro elemento entre eles). Além disso, só podem aparecer no início ou no final da sequência, de modo a não alterar o número de elementos entre os outros k.
...