1/1
|
1/2
|
1/3
|
1/4
|
1/5
|
1/6
|
1/7
|
...
|
2/1
|
2/2
|
2/3
|
2/4
|
2/5
|
2/6
|
2/7
|
...
|
3/1
|
3/2
|
3/3
|
3/4
|
3/5
|
3/6
|
3/7
|
...
|
4/1
|
4/2
|
4/3
|
4/4
|
4/5
|
4/6
|
4/7
|
...
|
5/1
|
5/2
|
5/3
|
5/4
|
5/5
|
5/6
|
5/7
|
...
|
.
|
.
|
.
|
.
|
.
|
.
|
.
| |
.
|
.
|
.
|
.
|
.
|
.
|
.
| |
.
|
.
|
.
|
.
|
.
|
.
|
.
|
Para mostrar que um conjunto C é contável ou o conjunto é finito ou existe uma bijeção f:
f: ![[;N \rightarrow Q;]](http://thewe.net/tex/N%20%5Crightarrow%20Q "N \rightarrow Q")
f(i) = 1/i
As frações com numerador 2, por exemplo, não pertenceriam a imagem de f. Podemos definir uma bijeção f:
O mesmo processo de enumeração por diagonais pode ser aplicado para mostrar que o produto cartesiano N x N é enumerável. Ainda mais, este processo pode ser generalizado para mostrar que o produto cartesiano de dois conjuntos enumeráveis A e B é enumerável.
O problema pede para você descobrir qual é o termo dada à sua posição na enumeração.
Podemos observar que na k-ésima diagonal temos k frações m/n cuja soma do numerador e denominador é uma constante m+n=k+1. O número de frações até a k-ésima diagonal é:
S(k) = 1+2+...+k = k(k+1)/2
![[;\sum_{i=1}^{n} a_{i+1}-a_{i} = a_{2}-a_{1}+a_{3}-a{2}+...+a_{n+1}-a{n} = a_{n+1}-a_{1};]](http://thewe.net/tex/%5Csum_%7Bi=1%7D%5E%7Bn%7D%20a_%7Bi+1%7D-a_%7Bi%7D%20=%20a_%7B2%7D-a_%7B1%7D+a_%7B3%7D-a%7B2%7D+...+a_%7Bn+1%7D-a%7Bn%7D%20=%20a_%7Bn+1%7D-a_%7B1%7D "\sum_{i=1}^{n} a_{i+1}-a_{i} = a_{2}-a_{1}+a_{3}-a{2}+...+a_{n+1}-a{n} = a_{n+1}-a_{1}")
![[;(i+1)^2-i^2 = i^2+2i+1-i^2=2i+1(2);]](http://thewe.net/tex/%28i+1%29%5E2-i%5E2%20=%20i%5E2+2i+1-i%5E2=2i+1%282%29 "(i+1)^2-i^2 = i^2+2i+1-i^2=2i+1(2)")
![[;\sum_{i=1}^{n}(i+1)^2 -i^2 = (n+1)^2-1^2=n^2+2n+1-1=n^2+2n;]](http://thewe.net/tex/%5Csum_%7Bi=1%7D%5E%7Bn%7D%28i+1%29%5E2%20-i%5E2%20=%20%28n+1%29%5E2-1%5E2=n%5E2+2n+1-1=n%5E2+2n "\sum_{i=1}^{n}(i+1)^2 -i^2 = (n+1)^2-1^2=n^2+2n+1-1=n^2+2n")
![[;\sum_{i=1}^{n}( (i+1)^2-i^2)=\sum_{i=1}^{n}(2i+1)=\sum_{i=1}^{n}(2i )+ n= 2\sum_{i=1}^{n}(i) + n;]](http://thewe.net/tex/%5Csum_%7Bi=1%7D%5E%7Bn%7D%28%20%28i+1%29%5E2-i%5E2%29=%5Csum_%7Bi=1%7D%5E%7Bn%7D%282i+1%29=%5Csum_%7Bi=1%7D%5E%7Bn%7D%282i%20%29+%20n=%202%5Csum_%7Bi=1%7D%5E%7Bn%7D%28i%29%20+%20n "\sum_{i=1}^{n}( (i+1)^2-i^2)=\sum_{i=1}^{n}(2i+1)=\sum_{i=1}^{n}(2i )+ n= 2\sum_{i=1}^{n}(i) + n")
![[;2\sum_{i=1}^{n}i+n = n^2+2n;]](http://thewe.net/tex/2%5Csum_%7Bi=1%7D%5E%7Bn%7Di+n%20=%20n%5E2+2n "2\sum_{i=1}^{n}i+n = n^2+2n")
![[;2\sum_{i=1}^{n}i=n^2+n;]](http://thewe.net/tex/2%5Csum_%7Bi=1%7D%5E%7Bn%7Di=n%5E2+n "2\sum_{i=1}^{n}i=n^2+n")
![[;\sum_{i=1}^{n}i=n(n+1)/2;]](http://thewe.net/tex/%5Csum_%7Bi=1%7D%5E%7Bn%7Di=n%28n+1%29/2 "\sum_{i=1}^{n}i=n(n+1)/2")
A fórmula S(k) pode ser desenvolvida utilizando vários métodos. Vamos desenvolver este somatório de duas maneiras.
Método 1
S = 1+2 +...+k (Somatório na ordem normal)
+S = k+(k-1)+...+1 (Somatório na ordem inversa)
2S = (k+1)k (Somando as k parcelas na mesma posição, obtemos (k+1))
S = (k+1)k/2
Método 2
A fórmula também pode ser desenvolvida utilizando a expressão (i-1)i - i(i+1).
Para descobrir qual é a diagonal que um termo t está localizada, podemos fazer o seguinte algoritmo:
d=1;
s=1;
while( s < t ){
d++;
s = s + d;
}
s=s-d;
A posição do termo na diagonal depende se a diagonal é par ou ímpar. Se a diagonal é par então o numerador começa com o numerador 1 e o denominador d. Se a diagonal é ímpar então o numerador começa com o numerador d e o denominador 1.
if((d%2)==0){
num=1+t-s-1;
den=d+s-t+1;
}else{
num=d+s-t+1;
den=1+t-s-1;
}
Nenhum comentário:
Postar um comentário