Olá Bruno e demais colegasdesta lista ... OBM-L,
Não entendi o enunciado da questão que você postou. Mas, por coincidência, eu
estava justamente tratando de um problema no N-cubo unitário - N-cubo
unitário e o conjunto de todas as N-uplas (x1, ..., xn) nas quais xi=0 ou xi=1
para todo i=1, ..., N - cujas operações podem ser parafraseadas em termos de
operações com números binários da seguinte forma :
Seja B um número natural ímpar maior que 1 tal que sua representação na base 2
contem N dígitos. Tomarei por B* o número natural tal que B+B*=(2^N) - 1 . Note
que B* é necessariamente um natural par. Se IMAGINARMOS que cada dígito de B
está grafado num pequeno quadrado e que a direita do seu dígito menos
significativo (dígito mais a direita ) e a esquerda do seu dígito mais
significativo ( dígito mais a esquerda ) existem infinitos quadradinhos onde
grafamos zero, o binário B passa a pertencer a uma "fita de leitura de
comprimento infinito".
Representarei o dígito menos significativo de B por X1, o mais significativo
por Xn. Se p > n então Xp = 0
Considere o seguinte algoritmo :
1) i=02) i =i+13) Se Xi XOR Xi+1 = 1 VOLTE ao passo 2 4) J = 05) j = j +
16) Yj = 1 SE j =1 SENAO Yj = (Xi XOR Xi+1) AND Yj-1 + ( NOT (Xi XOR Xi+1)
) AND Xi7) Zj = (Xi XOR Xi+1) XOR Yj8 ) Faca i=i+19 ) Se i < N+2 VOLTE
ao passo 5
Neste algoritmo, XOR é a clássica e bem conhecida porta lógica, assim definida
: 0 XOR 0 = 1 XOR 1 = 0 e 1 XOR 0=0 XOR 1=1. Esta operação é associativa e
representa o "OU EXCLUSIVO". Partindo de um dos vertices do N-cubo cuja
coordenada mais a direita é um, vale dizer, em nossa notação, de um número
ímpar em binário, os Z's obtidos com o algoritmo acima constituem o NOVO
VÉRTICE que me interessa analisar. O novo vértice pertence a um M-cubo
unitário e eu consigo demonstrar que reiterando o algoritmo nós teremos que
necessariamente M < N em algum momento.
A questão não é trivial e o que eu preciso é obter o NOVO VÉRTICE em função de
B*
Um Abraço a todosPSR,11010100A35
From: collares.br...@hotmail.com
To: obm-l@mat.puc-rio.br
Subject: [obm-l] Sequências Binárias e Concatenação
Date: Tue, 5 Oct 2010 20:19:32 +0000
Seja A={01,100,101}, e B={0,1,11}. Decida se as sequências binárias abaixo são
geradas univocamente:
a) A*
b) B*
c) {00}*A*
Obs: A*=EUAUA²UA³U...
Grato
BRUNO MARQUES COLLARS
