|
Caros colegas da lista:
O problema original foi proposto pelo
Dirichlet e modificado pelo Alexandre A. da Rocha:
N células são dispostas em círculo. Você coloca
fichas nas células da seguinte forma:
Coloca a 1a. ficha na célula 1.
Pula 1 célula e coloca a 2a. ficha na célula
3.
Pula 2 células e coloca a 3a. ficha na célula
6.
E assim por diante...
Dado N, em que passo você estará colocando a 2a.
ficha numa célula pela 1a. vez?
Pra começar, imagine um no. grande de células.
Os primeiros passos seriam os
seguintes:
Passo Célula
1
1
2
3
3
6
4 10
5 15
6 21
Repare que no k-ésimo passo você estará colocando a
ficha na célula k*(k+1)/2.
Isso é fácil de se provar por indução:
Chame de c(m) = célula onde a ficha é colocada no
m-ésimo passo.
c(1) = 1
Suponha que c(k) = k*(k+1)/2
c(k+1) = c(k) + (k+1) = k*(k+1)/2 + (k+1) =
(k+1)*(k+2)/2
-----
Agora, suponha que existem N
células.
Faça a seguinte correspondência:
Célula(1) <==> 1, N + 1, 2N + 1, 3N + 1,
...
Célula(2) <==> 2, N + 2, 2N + 2, 3N + 2,
...
...
Célula(N) <==> N, 2N, 3N, ...
Ou seja, cada número natural corresponde a uma
célula e dois números naturais x e y correspondem à mesma célula se e somente se
x = y (mod N).
Agora o problema é achar o menor valor inteiro
positivo de k para o qual existe um p, com 1 <= p <= k - 1 e tal
que c(k) = c(p) (mod N) ==>
k*(k+1)/2 = p*(p+1)/2 (mod N)
==>
k^2 + k = p^2 + p (mod N) ==>
k^2 - p^2 = p - k (mod N) ==>
(k - p)*(k + p) = p - k (mod N) ==>
(k - p)*(k + p + 1) = 0 (mod N)
Se N é primo com (k - p) ou N é primo com (k + p +
1) a análise fica mais fácil.
O caso em que N não é primo com nenhum dos dois é
mais complicado.
CASO 1: mdc(k - p,N)
= 1
Então vale k + p + 1 = 0 (mod
N).
Assim, o menor k é tal que:
k + p = N - 1 e 1 <= p <= k-1
==>
N é par ==> k = N/2 e p =
(N-2)/2
mdc(k - p,N) = (1,N) = 1 ==> OK
N é ímpar ==> k = (N+1)/2 e p =
(N-3)/2
mdc(k - p,N) = mdc(2,N) = 1 ==> OK
CASO 2: mdc(k + p + 1,N) = 1
Nesse caso, k - p = 0 (mod N).
k - p não pode ser 0, pois p <= k-1.
Assim, vamos tentar k - p = N
Aqui temos uma série de casos a considerar:
Caso 2.1:
N = 1 ou N = 2 (mod 3)
k = N+1 e p = 1 ==>
mdc(k+p+1,N) = mdc(N+3,N) = mdc(N,3) =
1 ==> OK
Caso 2.2:
N = 0 (mod 3) e N = 1, 2, 3 ou 4 (mod 5) ==>
k = N+2 e p = 2 ==>
mdc(k+p+1, N) = mdc(N+5,N) = mdc(N,5) = 1 ==> OK
Caso 2.3:
N = 0 (mod 3*5) e N <> 0 (mod 7)
k = N+3 e p = 3 ==>
mdc(k+p+1,N) = mdc(N+7,N) = mdc(N,7) = 1 ==> OK
Caso 2.4:
N = 0 (mod 3*5*7) e N <> 0 (mod 11)
k = N+5 e p = 5 ==>
mdc(k+p+1,N) = mdc(N+11,N) = mdc(N,11) = 1 ==> OK
E por aí vai, um primo de cada vez....
Finalmente, temos o
CASO 3: mdc(k - p,N) > 1 e mdc(k + p
+ 1,N) > 1.
Mas aí eu acho que a análise fica excessivamente
complicada (além disso, o meu saco acabou...)
Um abraço,
Claudio.
|