[obm-l] obm - U
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. __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.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 =
Re: [obm-l] preciso de ajuda
Tenho que fazer um trabalho de historia da matematica e não encontrei nada ainda. O problema é : Mostre usando o "metodo da exastão" que a area de um circuloé igual a area de um triangulo de base igual ao comprimento do circulo e altura igual ao raio do mesmo. Se alguem puder meda qualquer tipo de ajuda. Desde já agradeço.Yahoo! Mail - o melhor webmail do Brasil. Saiba mais!
Re: [obm-l] obm - U
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 =
[obm-l] Recadastramento --- obm-l
Esta lista está cheia de endereços quebrados e exige um recadastramento. Quem desejar *permanecer* na lista responda esta mensagem *para mim* (e não para a lista) ou envie uma mensagem para mim com Subject igual ao desta mensagem: Recadastramento --- obm-l Vou dar um tempo e mandar um segundo aviso quando estiver prestes a jogar fora a lista velha e botar no ar a nova. []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 =
[obm-l] pergunta!
a matemática é exata?se for, isso quer dizer que a partir do mundo preexistente podemosprovar a existência de Deus? (ou não?) através dela.?Yahoo! Mail - o melhor webmail do Brasil. Saiba mais!
Re: [obm-l] preciso de ajuda
Francisco: Tome um círculo e inscreva um, por exemplo, hexágono regular. Una os vértices desse hexágono ao centro do círculo, e note que isso determina seis triâgulos iguais, todos com um vértice no centro do círculo, e os outros dois vértices sobre o círculo. Repare que a área destes seis triângulos é menor que a área do círculo (uma vez que uma parte da área do círculo fica de fora). Repare que, diminuindo a base destes triângulos, é possível inserir mais triângulos dentro do círculo e, ao fazer isso, você aproxima a área dos triângulos da área do círculo. Ao tomar triângulos de base muito pequena (tanto quanto você queira), a base destes praticamente coincide com o círculo, e a área destes praticamente coincide com a área do círculo. Outro modo de pensar é imaginar que se preencha o círculo com circunferências de barbante (barbante é recurso pra idéia não ficar tão abstrata, combinado?!). Ponha uma circunferência após a outra até cobrir toda a área do círculo. Note que a ára de todas as circunferências é igual a área do círculo. Feito isso, faça um corte sobre o raio do círculo em qualquer ponto e estique nossos barbantes, obtendo um triângulo de base 2piR, altura R e área igual a área do círculo. Valeu?!! Abraço DANILO --- francisco de assis paulo lima [EMAIL PROTECTED] wrote: Tenho que fazer um trabalho de historia da matematica e não encontrei nada ainda. O problema é : Mostre usando o metodo da exastão que a area de um circulo é igual a area de um triangulo de base igual ao comprimento do circulo e altura igual ao raio do mesmo. Se alguem puder meda qualquer tipo de ajuda. Desde já agradeço . - Yahoo! Mail - o melhor webmail do Brasil. Saiba mais! __ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com = 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] pergunta! --- OFF TOPIC
Por favor, os objetivos da lista foram discutidos diversas vezes... soh uma dica, pense mais na sua pergunta... - Original Message - From: Marco Sales To: [EMAIL PROTECTED] Sent: Tuesday, October 21, 2003 11:55 AM Subject: [obm-l] pergunta! a matemática é exata?se for, isso quer dizer que a partir do mundo preexistente podemosprovar a existência de Deus? (ou não?) através dela.? Yahoo! Mail - o melhor webmail do Brasil. Saiba mais!
[obm-l] Problema 6 - OBM 3a. fase - Nível 2
Sei que a solução envolve conhecimento do princípio indutivo e da interpretação de gráficos, mas... Como resolver? PROBLEMA 6: Há N cidades na Tumbólia. Cada duas cidades desse país são ligadas por uma rodovia ou uma ferrovia, não existindo nenhum par de cidades ligadas por ambos meios. Um turista deseja viajar por toda Tumbólia, visitando cada cidade exatamente uma vez, e retornar a cidade onde ele começou sua jornada. Prove que é possível escolher a ordem na qual as cidades serão visitadas de modo que o turista mude o meio de transporte no máximo uma vez. Eu sinceramente não fazia a mínima noção de como resolver esse problema... No segundo dia de prova, resolvi as questões 4 e 5 em pouco tempo, mas empaquei nesta... =( Um abraço, Cesar Ryudi Kawakami = 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] 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 [EMAIL PROTECTED]
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
=
[obm-l] Eureka No.17
Caros(as) amigos da lista: Já está no site a Revista Eureka No. 17 Abraços, Nelly. = 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 =
[obm-l] Sobre a Revista Eureka
Quem for responsavel pela divulgaçao onde esta presente os artigos em separado da Revista Eureka, poderia pelo menos dar uma atualizadinha e por os artigos mais recentes...:) Yahoo! Mail - o melhor webmail do Brasil http://mail.yahoo.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 =
[obm-l] Sistema (IME)
x+y+z=a+b+1 xy+(x+y)z=a+b+ab xy=ab Determine os valores de a e b para q o sistema admita apenas solucoes reais e positivas para x e y. _ MSN Messenger: converse com os seus amigos online. http://messenger.msn.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 =
[obm-l] Sistemas lineares
Olá pessoal, gostaria de uma ajuda nessa questão. Discuta o sistema: (1)mx + y = 1 (2)x + y = 2 (3)x - y = m []´s NelsonYahoo! Mail - o melhor webmail do Brasil. Saiba mais!
[obm-l] Re: [obm-l] Problema 6 - OBM 3a. fase - Nível 2
Para N=2 e N=3 é simples ver que sempre é possível visitar todas as cidades mudando o transporte no máximo 1 vez. Agora suponha que isso seja verdade para todo 1 = k = N-1. Então esqueça uma cidade de Tumbólia e resolva o problema para as N-1 cidades restantes, sua solução deve ser um ciclo com no máximo 1 troca de transporte, se não houver troca de transporte, é muito simples ver que basta inserir a N'ésima cidade em qualquer posição do ciclo que o ciclo novo terá no máximo 1 troca. Suponha que há exatamente 1 troca de transporte e esta ocorra na cidade C[i], a cidade C[N] liga-se com C[i] ou de Ferrovia ou de Rodovia (F ou R), se a cidade do ciclo que liga-se a C[i] com o mesmo meio de transporte com o qual C[N] liga-se com C[i] é C[j], insira C[N] entre C[j] e C[i] e você tem um ciclo por todas as cidades só mudando o meio de transporte 1 vez! Basta ver que saímos de um ponto de origem, vamos até C[j] usando o mesmo meio de transporte, de C[j] para C[N] pode ou não ocorrer mudança de transporte, tanto faz, se não ocorrer, a mudança ocorre de C[N] para C[i], se ocorrer, temos certeza que o meio de transporte de C[N] até C[i] é o mesmo de C[i] até o ponto de origem. Fica bem mais fácil com desenhos! [ ]'s - Original Message - From: Cesar Ryudi Kawakami [EMAIL PROTECTED] To: obm-l [EMAIL PROTECTED] Sent: Tuesday, October 21, 2003 1:45 PM Subject: [obm-l] Problema 6 - OBM 3a. fase - Nível 2 Sei que a solução envolve conhecimento do princípio indutivo e da interpretação de gráficos, mas... Como resolver? PROBLEMA 6: Há N cidades na Tumbólia. Cada duas cidades desse país são ligadas por uma rodovia ou uma ferrovia, não existindo nenhum par de cidades ligadas por ambos meios. Um turista deseja viajar por toda Tumbólia, visitando cada cidade exatamente uma vez, e retornar a cidade onde ele começou sua jornada. Prove que é possível escolher a ordem na qual as cidades serão visitadas de modo que o turista mude o meio de transporte no máximo uma vez. Eu sinceramente não fazia a mínima noção de como resolver esse problema... No segundo dia de prova, resolvi as questões 4 e 5 em pouco tempo, mas empaquei nesta... =( Um abraço, Cesar Ryudi Kawakami = 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 =
[obm-l] Re: [obm-l] obm - U
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 [EMAIL PROTECTED]
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
Re: [obm-l] Re: [obm-l] Problema 6 - OBM 3a. fase - Nível 2
Não entendi direito com que tipo de hipótese foi trabalhada... Mais especificamente, não entendi como provar que tal suposição de que é possível mudar de meio de transporte apenas uma vez para todo 1 = k = N - 1... Haha, sou burro mesmo... =P Um abraço, Cesar Ryudi Kawakami At 19:35 21/10/2003, you wrote: Para N=2 e N=3 é simples ver que sempre é possível visitar todas as cidades mudando o transporte no máximo 1 vez. Agora suponha que isso seja verdade para todo 1 = k = N-1. Então esqueça uma cidade de Tumbólia e resolva o problema para as N-1 cidades restantes, sua solução deve ser um ciclo com no máximo 1 troca de transporte, se não houver troca de transporte, é muito simples ver que basta inserir a N'ésima cidade em qualquer posição do ciclo que o ciclo novo terá no máximo 1 troca. Suponha que há exatamente 1 troca de transporte e esta ocorra na cidade C[i], a cidade C[N] liga-se com C[i] ou de Ferrovia ou de Rodovia (F ou R), se a cidade do ciclo que liga-se a C[i] com o mesmo meio de transporte com o qual C[N] liga-se com C[i] é C[j], insira C[N] entre C[j] e C[i] e você tem um ciclo por todas as cidades só mudando o meio de transporte 1 vez! Basta ver que saímos de um ponto de origem, vamos até C[j] usando o mesmo meio de transporte, de C[j] para C[N] pode ou não ocorrer mudança de transporte, tanto faz, se não ocorrer, a mudança ocorre de C[N] para C[i], se ocorrer, temos certeza que o meio de transporte de C[N] até C[i] é o mesmo de C[i] até o ponto de origem. Fica bem mais fácil com desenhos! [ ]'s - Original Message - From: Cesar Ryudi Kawakami [EMAIL PROTECTED] To: obm-l [EMAIL PROTECTED] Sent: Tuesday, October 21, 2003 1:45 PM Subject: [obm-l] Problema 6 - OBM 3a. fase - Nível 2 Sei que a solução envolve conhecimento do princípio indutivo e da interpretação de gráficos, mas... Como resolver? PROBLEMA 6: Há N cidades na Tumbólia. Cada duas cidades desse país são ligadas por uma rodovia ou uma ferrovia, não existindo nenhum par de cidades ligadas por ambos meios. Um turista deseja viajar por toda Tumbólia, visitando cada cidade exatamente uma vez, e retornar a cidade onde ele começou sua jornada. Prove que é possível escolher a ordem na qual as cidades serão visitadas de modo que o turista mude o meio de transporte no máximo uma vez. Eu sinceramente não fazia a mínima noção de como resolver esse problema... No segundo dia de prova, resolvi as questões 4 e 5 em pouco tempo, mas empaquei nesta... =( Um abraço, Cesar Ryudi Kawakami = 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 = = 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] Sistemas lineares
On Tue, 21 Oct 2003 18:14:48 -0300 (ART), Nelson [EMAIL PROTECTED] wrote: Ol pessoal, gostaria de uma ajuda nessa questo. Discuta o sistema: (1) mx + y = 1 (2) x + y = 2 (3) x - y = m []s Nelson Some (2) e (3) para obter x = (2+m)/2 Substituia este valor de x em (2) para obter y = (2-m)/2 A fim de que (1) seja satisfeita, necessrio que m*(2+m)/2 + (2-m)/2 = 1 - 2m + m^2 + 2 - m = 2 - m^2 + m = 0 - m = 0 ou m = -1 Resumindo: (A) se m = 0 ento y = 1 e x = 1 soluo nica. (B) se m = -1 ento x = 1/2 e y = 3/2 soluo nica. (C) se m outro valor, as 3 equaes nunca sero satisfeitas simultaneamente, portanto o sistema no ter soluo. -- []s Felipe Pina = 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] Sistemas lineares
Somando (2) e (3), x = (2+m)/2. Subtraindo-as, y = (2-m)/2. O sistema eh possivel sse essas equacoes satisfazem (1). Substituindo: m(2+m) + (2-m) = 2 sse m^2 + m = 0 sse m=0 ou m=-1. Para m diferente disso, o sistema é impossível (pois não há solução). []'s - Original Message - From: Nelson To: [EMAIL PROTECTED] Sent: Tuesday, October 21, 2003 7:14 PM Subject: [obm-l] Sistemas lineares Olá pessoal, gostaria de uma ajuda nessa questão. Discuta o sistema: (1)mx + y = 1 (2)x + y = 2 (3)x - y = m []´s Nelson Yahoo! Mail - o melhor webmail do Brasil. Saiba mais!
