terça-feira, 18 de outubro de 2011

Problema Count on Cantor

O problema Count on Cantor é baseado na famosa demonstração que o conjunto dos números racionais é enumerável feita pelo matemático Georg Cantor. A prova é baseada no processo de enumeração utilizando as diagonais.Inicialmente, escreveremos todos os números racionais na forma matricial da seguinte maneira:

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: [;N \rightarrow C;]. Note que algumas escolhas não são suficientes, por exemplo, se definirmos a seguinte a função:
f: [;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: [;N \rightarrow Q;], enumerando os elementos de Q utilizando a diagonal.


       
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

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
[;\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);]
  
[;\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;] 

[;2\sum_{i=1}^{n}i+n = n^2+2n;] 

[;2\sum_{i=1}^{n}i=n^2+n;]

[;\sum_{i=1}^{n}i=n(n+1)/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: