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.