Re: Cardinalidade
On Thu, Dec 27, 2001 at 02:07:52PM -0200, Vinicius José Fortuna wrote: > Ué, eu sempre entendi que a cardinalidade de um conjunto fosse o número de > elemento do mesmo. > > Se dois conjuntos possuem infinitos elementos, eu achava que a > cardinalidade fosse a mesma. Alguém tem um conceito mais preciso de > cardinalidade? Cantor. :-) Cantor começou uma revolução na matemática ao descobrir que uns infinitos são maiores do que outros. Dois conjuntos A e B têm o mesmo cardinal (segundo Cantor) se existir uma bijeção entre A e B. O cardinal de A é menor do que o de B se existir uma função injetora de A para B mas não existir uma bijeção. Cantor demostrou que |N| = |Z| = |Q| = |A| < |R| = |C| onde estes são os conjuntos de números naturais, inteiros, racionais, algébricos, reais e complexos. Em particular, isto demonstrava a existência de números transcendentes (não algébricos), novidade na época. Tudo isto está em Naïve Set Theory de Halmos (e em um milhão de outros lugares). []s, N.
Re: Cardinalidade
On Thu, Dec 27, 2001 at 03:23:32PM +, Rogerio Fajardo wrote:
>
> Olá, colegas da lista,
>
> Dados dois conjuntos, A e C, infinitos, com cardinalidade de C maior que
> de A, é sempre possível achar um conjunto B tal que AxB tem a mesma
> cardinalidade de C?
Sim, basta tomar B = C.
Para cardinais infinitos x e y vale
x + y = x y = max{x,y}
Isto usa o axioma da escolha. Está demonstrado no livro Set Theory, de Jech.
Dou abaixo um esboço da demonstração.
Como você bem observou, basta provar que sempre temos |A^2| = |A|.
Podemos supor A bem ordenado, isto é, com uma ordem onde todo subconjunto
não vazio tem mínimo (o axioma da escolha garante que todo conjunto admite
uma boa ordem). Podemos ainda supor que para todo x em A o conjunto
{y in A | y < x} tem cardinalidade menor do que A. Caso contrário
procuraríamos x0, o menor x tq este conjunto tem a mesma cardinalidade de A,
e passaríamos a trabalhar com A' = {y in A | y < x0}.
Considere agora a seguinte ordem em AxA:
(x,y) < (x',y') <==> max{x,y} < max{x',y'}
ou
max{x,y} = max{x',y'} e x < x'
ou
max{x,y} = max{x',y'} e x = x' e y < y'.
Não é difícil agora verificar os seguintes fatos sobre AxA:
* AxA é bem ordenado pela relação de ordem definida acima.
* Para todo z in AxA, |{w in AxA | w < z}| < |A|.
Estes fatos são suficientes para demostrar que A e AxA não apenas
têm a mesma cardinalidade mas que existe uma bijeção estritamente
crescente entre A e AxA (com respeito, é claro, às boas ordens acima).
[]s, N.
Re: Domino
E ae, Carlos. Tudo certo? Aqui vai uma solução, por construção: Primeiro, temos um lado múltiplo de 3 e ímpar, portanto congruente a 3 módulo 6. Portanto, temos que ver tabuleiros do tipo (6a+3) x (2b+1), com a>=0 e b>=1. Quando um lado é 3, vemos que as linhas de baixo só podem ser cobertas com blocos: AAB ABB ou ABB AAB Continuando a preencher, chegaremos a uma linha 3 x 1. Ou seja, não é possível montar nenhum tabuleiro 3 x (2b+1). Isso resolve os casos a=0 e b=1. Também temos que podemos cobrir qualquer retângulo (3n) x (2m). Com isso, vemos que podemos cobrir qualquer retângulo 6 x (2b+1), onde b>=1. Basta juntar uma peça 6 x 3 com várias 6 x 2. Ilustrando: CCDDEE CFDGEH FFGGHH AABCCD \ repetido b-1 vezes ABBCDD / Faltam os casos (6a+3) x (2b+1), com a>0 e b>1. O caso 9 x 5 (a=1, b=2) é coberto dessa forma: AABBCDDEE ARBGCCDEH RRKGGTTHH OKKSNTUPP OOSSNNUUP (foi mal se aparecer tudo desalinhado. não encontrei outra forma de mostrar) Com ele, podemos montar qualquer outro, pois basta adicionar b-2 retângulos 9 x 2 na parte de baixo e a-1 retângulos 6 x (2b+1) à direita. Daniel M. Yamamoto - Original Message - From: Carlos Stein Naves de Brito <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Friday, December 21, 2001 11:47 PM Subject: Domino > Probleminha: > Em que casos um tabuleiro mxn(m,n impares) pode ser coberto por triminos que > sao tres quadradinhos que formam um bumerangue. >
Re: Domino
Mas ajudou sim, David! Com os casos que voce citou em maos, podemos atacar agora o caso m x n com m e n impares, m divisivel por 3. Se m=3 entao pode-se mostrar que eh impossivel preencher o tabuleiro; voce pode fazer por inducao, analisando as 3 possibilidades de cobrir um dos cantos, observando como cobrir o canto "proximo adjacente" e reduzir 3 x n para 3 x (n-2); note que 3 x 1 certamente nao dah. Analogamente, se n=3 tambem nao dah para cobrir o tabuleiro. Assim, suponha m,n>=5, impares, e m divisivel por 3, isto eh, m=6a+9 e n=2b+5 com a,b>=0. Entao: i) O retangulo 6a x n voce jah mostrou como fazer, certo? ii) O outro pedaco eh 9 x 2b+5. O pedaco 9 x 2b voce tambem jah mostrou como fazer, neh? iii) Entao soh falta cobrir o pedaco 9 x 5, o que pode ser feito por tentativa e erro com 15 triminos... Tente voce mesmo, eh rapido achar uma configuracao que presta. Aqui estah uma achada rapidinho: 1 1 2 2 3 3 4 5 5 1 6 6 2 7 3 4 4 5 8 8 6 7 7 9 9 a a 8 b c d d 9 e a f b b c c d e e f f (esse pedaco aqui em cima soh fica diretinho se voce estiver usando uma fonte de largura fixa, mas acho que deu para entender, neh?) Pronto, feito! Qualquer tabuleiro pode ser coberto, desde que um dos lados seja divisivel por 3, mas nenhum deles seja 3. Abraco, Ralph - Original Message - From: "David Daniel Turchick" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Thursday, December 27, 2001 1:09 PM Subject: Re: Domino Ops! Você pediu justamente m e n ímpares! Às vezes é bom ler o enunciado direito antes de tentar resolver... Obrigado, Bruno, por me avisar da minha besteira, e desculpa aí ao pessoal da lista! -Mensagem original- De: David Daniel Turchick <[EMAIL PROTECTED]> Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Data: Quinta-feira, 27 de Dezembro de 2001 12:10 Assunto: Re: Domino Olha, tentar, eu tentei, mas aposto que onde eu cheguei vários chegaram... Mostrei que é necessário que m ou n sejam múltiplos de 3: a área do tabuleiro deve ser múltipla da área do triminó, e 3 é primo), e para fixar as idéias, impus que fosse o m=3a. É suficiente que n seja par: se n=2b, divida o tabuleiro em b faixas mX2 e preencha cada faixa com a retângulos 3X2, que podem claramente ser "triminomizados". É suficiente n ímpar >1 e m par: seja a=2c, então m=6c, e seja n=2b+1, então dividimos o tabuleiro em b-1 faixas mX2 (com as quais você já sabe o que fazer) e 1 faixa mX3, a qual você preenche com 3c retângulos 2X3. Então o que falta é o caso m e n ímpares. Espero ter ajudado (mas aposto que não ajudei!). David -Mensagem original- De: Carlos Stein Naves de Brito <[EMAIL PROTECTED]> Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Data: Quinta-feira, 27 de Dezembro de 2001 00:54 Assunto: Domino Please, alguem tenta pra mim... Obrigado! Em que casos um tabuleiro mxn(m,n impares) pode ser coberto por triminos que sao tres quadradinhos que formam um bumerangue.
Re: Cardinalidade
Ué, eu sempre entendi que a cardinalidade de um conjunto fosse o número de elemento do mesmo. Se dois conjuntos possuem infinitos elementos, eu achava que a cardinalidade fosse a mesma. Alguém tem um conceito mais preciso de cardinalidade? Obrigado Vinicius Fortuna [ Indo para a Semana Olímpica :-) ] On Thu, 27 Dec 2001, Rogerio Fajardo wrote: > > Olá, colegas da lista, > > Dados dois conjuntos, A e C, infinitos, com cardinalidade de C maior que > de A, é sempre possível achar um conjunto B tal que AxB tem a mesma > cardinalidade de C? > Todo conjunto infinito A tem a mesma cardinalidade de AxA (como ocorre com > N e com R)? Se isso vale, já temos a resposta para a pergunta de cima > (considerando B=C e que card(A) > Rogério > > > _ > MSN Photos is the easiest way to share and print your photos: > http://photos.msn.com/support/worldwide.aspx >
Cardinalidade
Olá, colegas da lista, Dados dois conjuntos, A e C, infinitos, com cardinalidade de C maior que de A, é sempre possível achar um conjunto B tal que AxB tem a mesma cardinalidade de C? Todo conjunto infinito A tem a mesma cardinalidade de AxA (como ocorre com N e com R)? Se isso vale, já temos a resposta para a pergunta de cima (considerando B=C e que card(A)http://photos.msn.com/support/worldwide.aspx
Re: Domino
Ops! Você pediu justamente m e n ímpares! Às vezes é bom ler o enunciado direito antes de tentar resolver... Obrigado, Bruno, por me avisar da minha besteira, e desculpa aí ao pessoal da lista! -Mensagem original- De: David Daniel Turchick <[EMAIL PROTECTED]> Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Data: Quinta-feira, 27 de Dezembro de 2001 12:10 Assunto: Re: Domino Olha, tentar, eu tentei, mas aposto que onde eu cheguei vários chegaram... Mostrei que é necessário que m ou n sejam múltiplos de 3: a área do tabuleiro deve ser múltipla da área do triminó, e 3 é primo), e para fixar as idéias, impus que fosse o m=3a. É suficiente que n seja par: se n=2b, divida o tabuleiro em b faixas mX2 e preencha cada faixa com a retângulos 3X2, que podem claramente ser "triminomizados". É suficiente n ímpar >1 e m par: seja a=2c, então m=6c, e seja n=2b+1, então dividimos o tabuleiro em b-1 faixas mX2 (com as quais você já sabe o que fazer) e 1 faixa mX3, a qual você preenche com 3c retângulos 2X3. Então o que falta é o caso m e n ímpares. Espero ter ajudado (mas aposto que não ajudei!). David -Mensagem original- De: Carlos Stein Naves de Brito <[EMAIL PROTECTED]> Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Data: Quinta-feira, 27 de Dezembro de 2001 00:54 Assunto: Domino Please, alguem tenta pra mim... Obrigado! Em que casos um tabuleiro mxn(m,n impares) pode ser coberto por triminos que sao tres quadradinhos que formam um bumerangue.
Re: Domino
Olha, tentar, eu tentei, mas aposto que onde eu cheguei vários chegaram... Mostrei que é necessário que m ou n sejam múltiplos de 3: a área do tabuleiro deve ser múltipla da área do triminó, e 3 é primo), e para fixar as idéias, impus que fosse o m=3a. É suficiente que n seja par: se n=2b, divida o tabuleiro em b faixas mX2 e preencha cada faixa com a retângulos 3X2, que podem claramente ser "triminomizados". É suficiente n ímpar >1 e m par: seja a=2c, então m=6c, e seja n=2b+1, então dividimos o tabuleiro em b-1 faixas mX2 (com as quais você já sabe o que fazer) e 1 faixa mX3, a qual você preenche com 3c retângulos 2X3. Então o que falta é o caso m e n ímpares. Espero ter ajudado (mas aposto que não ajudei!). David -Mensagem original- De: Carlos Stein Naves de Brito <[EMAIL PROTECTED]> Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Data: Quinta-feira, 27 de Dezembro de 2001 00:54 Assunto: Domino Please, alguem tenta pra mim... Obrigado! Em que casos um tabuleiro mxn(m,n impares) pode ser coberto por triminos que sao tres quadradinhos que formam um bumerangue.
