Re:[obm-l] Traco Zero
Oi pessoal, Aqui vai minha solucao. Lema 1: Se A eh uma matriz quadrada de ordem 2 que nao eh da forma A = a * I, onde I eh a matriz identidade e a eh um escalar diferente de zero, entao existe uma matrix X inversivel, tal que: (1/X) * A * X = [a' c'], ou seja X anula o elemento da posicao (2,2). [d' 0 ] Dem.: Seja A = [a c] [d b] Dividindo em 3 casos: 1) Se c for diferente de zero, vale: [a c] * [0 c] = [c 0 ] = [0 c] * [a+b cd-ab] [d b] [1 -a] [b cd-ab] [1 -a] [1 0 ] Como |0 c| = -c 0, basta tomar X = [0 c] |1 -a|[1 -a] 2) Se d for diferente de zero, vale: [a c] * [a 1] = [a^2+cd a] = [a 1] * [a+b 1] [d b] [d 0] [ad+bd d] [d 0] [cd-ab 0] Como |a 1| = -d 0, basta tomar X = [a 1] |d 0|[d 0] 3) Se c = d = 0 e a b, vale: [a 0] * [1 -1] = [a-a] = [1 -1] * [a+b -a] [0 b] [-b a] [-b^2 ab] [-b a] [b0] Como |1 -1| = a - b 0, basta tomar X = [1 -1] |-b a| [-b a] Lema 2: Se a_1, a_2, ..., a_n eh uma sequencia de numeros num corpo de caracteristica zero com a_1 + a_2 + ... + a_n = 0, entao existe uma permutacao p, tal que: existe r = 0 com: a_p(1) = a_p(2) = ... = a_p(r) = 0 e a_p(i) Somatorio (j i) a_p(j), para i r Dem.: Iremos provar por inducao sobre n. Base de inducao(n = 1): o lema 2 eh claramente verdadeiro. Passo indutivo: Se fosse a_1 = a_2 = ... = a_n, entao como o corpo eh de caracteristica zero, temos que a_1 = a_2 = ... = a_n = 0, logo o lema ja seria verdadeiro para a permutacao identidade. Se existissem i, j com a_i a_j, entao podemos supor que i = n - 1 e j = n (basta aplicar uma permutacao que troca o a_i com a_(n-1) e o a_j com o a_n), assim, sabemos que existe uma permutacao q tal que: existe r' = 0 com: b_p(1) = b_p(2) = ... = b_p(r') = 0 e b_p(i) Somatorio (j i) b_p(j), para i r', onde: b_1 = a_1, b_2 = a_2, ... b_(n - 2) = a_(n - 2) e b_(n - 1) = a_(n - 1) + a_n. Compondo a permutacao q (extendida) com a permutacao que troca a_i e a_j com a_(n-1) e a_n, temos a nossa permutacao p. Por inducao o lema 2 eh verdadeiro para todo n = 1. Lema 3: Se M = (m_(i,j)) eh uma matriz quadrada nxn tal que tr(M) = 0 sobre um corpo de caracteristica zero, entao existe X inversivel tal que: M = (1/X) * A * X, onde A eh uma matriz com diagonal principal nula. Obs.: tr(M) = tr(1/X * A * X) = tr(A). Dem.: * Se n = 1 o resultado eh trivial. * Se n = 2, o lema 2 eh consequencia imediata do lema 1. * Se n 2, utilizando o lema 2 podemos assumir que: Existe r = 0, tal que: m_(1,1) = m_(2,2) = ... = m_(r,r) = 0 e m_(i,i) Somatorio (j i) m_(j,j), para i r. (pois basta aplicar a matriz permutacao P correspondente a p, assim P * M * (1/P) satisfaz a hipotese acima) Se r = n, entao basta tomar X = I e acabou. Se r n, temos: Como m_(n,n) m_(n-1,n-1), vale (pela lema 1): X_n * M * (1/X_n) tem o elemento da posicao (n,n) igual a zero. Basta tomar: X_n = [I(n-2) 0], onde I(n-2) eh a matriz identidade de ordem n - 2 e [ 0P_n] P_n eh a matriz tal que (1/P_n) * [m_(n-1, n-1) m_(n-1,n)] * P_n eh uma matriz de [m_(n,n-1)m_(n,n) ] ordem 2x2 com o elemento da posicao (2,2) igual a zero (essa matriz P existe pelo lema 1) Como m_(n-2,n-2) m_(n-1,n-1) + m_(n,n), vale (pelo lema 1) X_(n-1) * X_n * M * (1/X_n) * (1/X_(n-1)) tem os elementos das posicoes (n,n) e (n-1,n-1) iguais a zero. Basta tomar: X_(n-1) = [I(n-3) 0 0 ], onde P_(n-1) eh a matriz que zera a posicao [ 0P_(n-1) 0 ] [ 0 0 I(1)] (n-1,n-1) de X_n * M * (1/X_n) Prosseguindo desta forma, teremos que X * M * (1/X) tem a diagonal principal nula, onde X = Produtorio (i r) de X_i Logo o lema 3 eh verdadeiro, tambem. Problema: Seja M uma matriz real quadrada, entao: * tr(M) = 0 = Existem A e B matrizes reais tais que M = AB - BA. Solucao: Claramente se M = AB - BA = tr(M) = 0, pois tr(AB) = tr(BA), tr(A + B) = tr(A) + tr(B) e tr(a * A) = a * tr(A), onde a eh um escalar. Se tr(M) = 0, entao, pelo lema 3 (como R tem caracteristica zero), existe X inversivel tal que: M = (1/X) * C * X, onde a diagonal principal de C eh nula (digamos que C = (c_(i,j))). Tomando A' = (a_(i,j)) com: a_(i,j) = i se i=j = 0 caso contrario e tomando B' = (b_(i,j)) com: b_(i,j) = c_(i,j)/(i-j) se ij = 0 caso contrario Vale: C = A'B' - B'A', logo se A = (1/X) * A' * X e B = (1/X) * B' * X, vale: M = AB - BA. []'s Humberto = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
RES: [obm-l] OBM 2004 - NIVEL 3
Tenho uma outra solução. Suponha, por absurdo, que exista uma distribuição dos algarismos com no máximo 3 algarismos distintos por linha (e por coluna). Para cada posição do tabuleiro, marque o número de posições na mesma linha como o mesmo algarismo. Se a primeira linha for: 0 0 0 2 2 2 5 5 5 5 Iremos marcar: 3 3 3 3 3 3 4 4 4 4 Já que existem 3 posições com o algarismo 0, 3 com o algarismo 2 e 4 com o algarismo 5. A soma dos números marcados de cada coluna deverá ser menor ou igual a 3 * 10 = 30, pois temos no máximo 3 algarismos em cada coluna. Mas isso é um absurdo, já que a soma dos números marcados de cada linha é pelo menos: 3^2 + 3^2 + 4^2 = 34, logo a soma de todos os números marcados é pelo menos 34 * 10 = 340, portanto uma coluna deverá ter soma maior ou igual a 34. Humberto -Mensagem original- De: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Em nome de Fabio Dias Moreira Enviada em: segunda-feira, 18 de outubro de 2004 18:09 Para: [EMAIL PROTECTED] Assunto: Re: [obm-l] OBM 2004 - NIVEL 3 Igor Castro said: É! me confundi... contei 5 alg diferentes umas 10 vezes na sétima linha :P mas enfim.. ok.. 4 alg diferentes sempre... essa era a resposta então? como provar que não tem um quadrado com 3? 2? [...] Para simplificar o argumento, eu vou dizer que uma _fila_ é uma linha ou coluna qualquer do tabuleiro. Lema: Se C é um conjunto de filas que contêm todas as ocorrências de um dado algarismo, então C tem pelo menos sete filas. Prova: Suponha que |C| = k. Suponha ainda que h dessas k filas são horizontais. Então as dez ocorrências do algarismo em questão devem estar contidas na interseções das h filas horizontais com as k-h filas verticais, donde h(k-h) = 10. Mas por MA-MG, h(k-h) = [(h+k-h)/2]^2 = k^2/4, logo k = sqrt(40) == k = 7. Marque todas as filas que contém algum algarismo zero, todas as que contém algum algarismo um, ... até o nove. Pelo Lema, pelo menos 70 filas foram marcadas; como o tabuleiro possui apenas 20 filas, o PCP implica que alguma fila foi marcada pelo menos quatro vezes, logo esta fila possui quatro algarismos distintos. Unindo esta demonstração ao tabuleiro que o Paulo José enviou para a lista, está demonstrado que o maior valor de n que satisfaz ao enunciado é n=4. []s, -- Fábio ctg \pi Dias Moreira = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Contando matrizes (problema em aberto)
Oi Domingos, Referência eletrônica eu não sei, mas existe um livro do Knuth que tem tudo isso e mais um pouco. Vou procurar algumas referências aqui na biblioteca do Impa, ai eu te passo. Abracos, Humberto Silva Naves --- Domingos Jr. [EMAIL PROTECTED] escreveu: Oi Bruno, Bruno?! hehehehe, é Domingos :-) Achei legal a sua solução, mas esse problema é conhecido! O problema é contar o número de semistandard tableau's (não sei como é a expressão em português) de forma m x n com entradas no máximo (p - n), cuja resposta é igual a função de Schur: s_lambda_(1, 1, ..., 1), onde lambda é a forma mxn. parece interessante, mas não consegui achar boas referências online sobre isso... você tem alguma? aliás, você sabe se essa função é implementada no Mathematica? PS: Eu sabia que esse problema é conhecido porque recentemente li o livro Proofs and Confirmations de David M. Bressoud e lá tem tudo isso, inclusive a identidade de Jacobi-Trudi, que me permitiu concluir: s_lambda_(1, 1, 1, ..., 1) = det M. (As soluções do livro são maneiras!) infelizmente, parece que não temos esse livro no IME.USP... Abraços, Humberto Silva Naves [ ]'s Domingos. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = __ Conheça a nova central de informações anti-spam do Yahoo! Mail: http://www.yahoo.com.br/antispam = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Contando matrizes (problema em aberto)
Oi Bruno,
Achei legal a sua solução, mas esse problema é conhecido! O problema é contar o
número de semistandard tableau's (não sei como é a expressão em português)
de forma m x n com entradas no máximo (p - n), cuja resposta é igual a função
de Schur:
s_lambda_(1, 1, ..., 1), onde lambda é a forma mxn.
Ou de outra forma:
A resposta é o determinante da matriz m x m abaixo:
M = (Comb (p + n + i - j, p)) (i, j variam de 1 até m)
Obs.: Comb (a, b) = a! / (b! * (a - b)!)
PS: Eu sabia que esse problema é conhecido porque recentemente li o livro
Proofs and Confirmations de David M. Bressoud e lá tem tudo isso, inclusive
a identidade de Jacobi-Trudi, que me permitiu concluir:
s_lambda_(1, 1, 1, ..., 1) = det M. (As soluções do livro são maneiras!)
Abraços,
Humberto Silva Naves
--- Domingos Jr. [EMAIL PROTECTED] escreveu: O problema era:
Quantas matrizes A, m x n, com elementos de {1, 2, .., p} existem tais que
A(i,j) A(i+1,j) e A(i,j) A(i,j+1)?
Acho que encontrei a solução! Quem quiser dar uma olhada e comentar:
http://www.linux.ime.usp.br/~domingos/contar_matrizes.pdf
[ ]'s
Domingos.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
__
Conheça a nova central de informações anti-spam do Yahoo! Mail:
http://www.yahoo.com.br/antispam
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
