[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Re: [obm-l] obm - U

To: obm-l@xxxxxxxxxxxxxx
Subject: [obm-l] Re: [obm-l] obm - U
From: yurigomes@xxxxxxxxxxxxxx
Date: Tue, 21 Oct 2003 20:06:21 -0200
In-Reply-To: <004101c397fd$543a68e0$0301a8c0@stabel>
Reply-To: obm-l@xxxxxxxxxxxxxx
Sender: owner-obm-l@xxxxxxxxxxxxxxxxxxxxx

 Vc pode fazer essa desigualdade por Cauchy: observe
  (SOMA{(sr(p_i^3))^2}).(SOMA{((sr(p_i))^2} >=
   (SOMA{sr(p_i^3).sr(p_i})^2  
  Mas o segundo fator do lado esquerdo é igual a SOMA(p_i)=1, e o resultado
segue.
  Outra maneira seria observar que 
   SOMA{p_i^3) = SOMA{p_i^3).SOMA{p_i) = SOMA(p_i^4) + SOMA(i != j){p_i^3.p_j).

  Desenvolvendo o lado direito da desigualdade que vc quer mostrar e cancelando
soma(p_i^4), vc vai querer que  
   SOMA(i != j){p_i^3.p_j) >=  2.SOMA(i < j){p_i^2.p_j^2)
  Por média, p_i^3.p_j + p_i.p_j^3 >= 2p_i^2.p_j^2. Aih basta somar em i,j.
  Ateh mais, 
  Yuri 

-- Mensagem original --

>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
>=========================================================================
>

[]'s, Yuri
ICQ: 64992515


------------------------------------------
Use o melhor sistema de busca da Internet
Radar UOL - http://www.radaruol.com.br



=========================================================================
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
=========================================================================
References:
- Re: [obm-l] obm - U
  - From: Eduardo Casagrande Stabel
Prev by Date: [obm-l] Re: [obm-l] Problema 6 - OBM 3a. fase - Nível 2
Next by Date: Re: [obm-l] Re: [obm-l] Problema 6 - OBM 3a. fase - Nível 2
Prev by thread: Re: [obm-l] obm - U
Next by thread: [obm-l] Recadastramento --- obm-l
Index(es):
- Date
- Thread