[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] obm - U
Oi Nicolau!
E quanto ao problema quatro? Eu chamei de 0 < p_i < 1 a probabilidade de
sair a face i num lançamento, tendo-se SOMA{p_i} = 1. Eu desenvolvi um pouco
o problema e mostrei que ele era equivalente a demonstrar a desigualdades
SOMA{p_i^3} >= SOMA{p_i^2}^2 com igualdade sse todos p_i = 1/6. Não consegui
demonstrar esta desigualdade. Quando vale este primeiro passo? ;) Como se
demonstra esta desigualdade?
Para quem não fez a prova, o enunciado era
QUESTÃO 4. Um dado é lançado três vezes e o resultado das faces é a, b e c.
Provar que P(a=c | a=b) >= P(a=c | a <> b) e que vale a igualdade se e
somente se o dado é honesto, ou seja, a probabilidade de cada face é 1/6.
Abraço, Duda.
From: "Nicolau C. Saldanha" <nicolau@sucuri.mat.puc-rio.br>
> On Tue, Oct 21, 2003 at 08:58:16AM -0200, marcio.lis wrote:
> > Alguem poderia me informar alguma coisa sobre o q o
> > pessoal andou fazendo na obm U informações sobre as
> > soluções tbm seriam interessantes.Gostaria de saber se
> > no 3 oa cardinalidade de xp=(p^2+2p+2)^2 e se no caso
> > 2x2 ficap^2+2p+2.
>
> O problema 3, nível U, é de minha autoria.
> Repetindo o enunciado, devemos contar as matrizes quadradas A
> de tamanho 4x4 com coeficientes em Z/(p) que satisfazem A^2 = I (p > 2).
>
> Uma matriz A em K^(nxn), onde K é um corpo qq,
> satisfaz A^2 = I se e somente se K^n pode ser decomposto
> em dois subespaços U e V com interseção zero e soma K^n
> tais que A restrito a U (resp V) é a identidade (menos a id).
>
> Estes dois subespaços são os autoespaços associados aos autovalores 1
e -1.
> Como o polinômio mínimo não tem raiz dupla, A é semisimples
(diagonalizável).
>
> O importante é notar que há uma bijeção natural entre matrizes
> satisfazendo A^2 = I e pares de subespaços U e V como acima.
> Neste ponto dá para contar na marra ou dá para saber ou criar
> um pouco mais de teoria.
>
> Na marra, você contaria para cada valor da dimensão de U.
> Temos 2 soluções triviais com dim U = 0 e dim U = 4 (-I e I).
> No caso dim U = 1, primeiro escolhemos U: há (p^4 - 1) geradores
> possíveis para U mas precisamos identificar vetores que são múltiplos
> constantes um do outro, ou seja, precisamos dividir por (p - 1)
> para concluir que há (p^3 + p^2 + p + 1) subespaços de dimensão 1.
> Escolha um subespaço complementar V_0 fixo qq:
> um espaço complementar V pode ser identificado com o gráfico
> de uma transformação linear de V_0 em U,
> ou seja, para cada U há (p^3) espaços complementares V.
> O caso dim U = 3 é análogo.
> Até aqui somamos 2 p^6 + 2 p^5 + 2 p^4 + 2 p^3 + 2 e falta o caso dim U =
2.
>
> Para escolher um subespaço U de dim 2, vamos primeiro escolher uma base.
> Temos (p^4 - 1) escolhas para o primeiro vetor e (p^4 - p) escolhas
> para o segundo. Por outro lado, dado um subespaço de dim 2,
> quantas bases ele tem? Agora temos (p^2 - 1) escolhas para o primeiro
> vetor e (p^2 - p) escolhas para o segundo. Assim, o número de subespaços U
é
> ((p^4 - 1)(p^4 - p))/((p^2 - 1)(p^2 - p)) = p^4 + p^3 + 2p^2 + p + 1.
> Novamente, para cada U escolha um complementar V_0 fixo qq:
> um espaço complementar V pode ser identificado com o gráfico
> de uma transformação linear de V_0 em U,
> ou seja, para cada U há (p^4) espaços complementares V.
> Ou seja, o caso dim U = 2 contribui com p^8 + p^7 + 2 p^6 + p^5 + p^4
> e a resposta final do problema é
>
> p^8 + p^7 + 4 p^6 + 3 p^5 + 3 p^4 + 2 p^3 + 2
>
> Para resolver o caso geral (em vez do caso 4x4),
> ajuda muito saber contar subespaços de dimensão b de F_q^a,
> onde q é uma potência de primo, F_q é o corpo finito de q elementos,
> e a e b são inteiros não negativos. Este problema é tão importante
> que a resposta tem nome, e escreve-se assim:
>
> ( a )
> ( )
> ( b )q
>
> ou seja, o símbolo de binomial com um q embaixo; eu vou escrever
binom(a,b;q).
> Lendo o que eu escrevi acima não é muito difícil concluir que
>
> (q^a - 1)(q^(a-1) - 1)(q^(a-2) - 1)...(q - 1)
> binom(a,b;q) = ----------------------------------------------------------
> (q^b - 1)(q^(b-1) - 1)...(q - 1) (q^(a-b) - 1)...(q - 1)
>
> Não é muito difícil provar que isto é um polinômio em q com coeficientes
> inteiros não negativos. A notação talvez fique menos misteriosa observando
> que binom(a,b;1) = binom(a,b). Há outras interpretações para binom(a,b;q),
> o meu livrinho do colóquio (matemática quântica) pode servir como
referência.
>
> Voltando ao problema da OBM, a resposta do problema para matrizes nxn
> com coeficientes em F_q é
>
> somatório_k q^(k(n-k)) binom(n,k;q).
>
> Em particular, se n = 2 temos
>
> 1 + q (q+1) + 1 = q^2 + q + 2.
>
> No caso q = 2^k o início do problema quebra pois (x^2 - 1) = (x - 1)^2
> em característica 2, ou seja, a matriz deixa de ser diagonalizável.
> O problema fica totalmente diferente.
>
> []s, N.
> =========================================================================
> 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
=========================================================================