RE: [obm-l] Problema interessante
Tome uma partição QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n
elementos cada. Ponha os elementos de A em ordem crescente a_1...a_n e os
de B em ordem decrescente b_1...b_n. Prove que:
|a_1-b_1| + ... + |a_n-b_n| = n^2
Acabei esquecendo de mandar a resposta, mas aqui vai ela, espero que em
tempo
Vamos chamar os conjuntos:
x = {1 a n} e y={n+1 a 2n}
Vamos supor que o conjunto A é formado de tal forma que possua m elementos
de Y e n-m elementos de X. Logo, o conjunto B é obrigatoriamente formado por
m elementos de x e n-m elementos de Y.
Então podemos considerar que:
RESULTADO = |a_1-b_1| + ... + |a_n-b_n| = (a1 - b1) + (a2 - b2) + ... + (am
- bm) - ((am+1 - bm+1) + ... +(an - bn))=
soma a (1 a m) - soma b(1 a m) - soma a(m+1 a n) + soma b(m+1 a n)
Se voltarmos a suposição inicial, soma a (1 a m) + soma b(m+1 a n) é a soma
dos elementos do conjunto Y, e soma b(1 a m) + soma a(m+1 a n) é a soma dos
elementos de X.
Logo, temos que:
RESULTADO = soma(n+1 a 2n) - soma(1 a n) = n*n + soma(1 a n) - soma(1 a n)
=n^2
-Original Message-
From: Cláudio (Prática) [mailto:[EMAIL PROTECTED]
Sent: Monday, February 24, 2003 2:48 PM
To: [EMAIL PROTECTED]
Subject: [obm-l] Problema interessante
Taí um resultado inesperado (pelo menos pra mim):
Tome uma partição QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n
elementos cada. Ponha os elementos de A em ordem crescente a_1...a_n e os
de B em ordem decrescente b_1...b_n. Prove que:
|a_1-b_1| + ... + |a_n-b_n| = n^2.
Um abraço,
Claudio.
=
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
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] Teorema Fundamental da Algebra
Saudacoes! A prova era assim: pensa que seu polinomio e' P(z)=z^n+a1.z^(n-1)+...+an. Se z=R.cis(t),P(z)=R^n(cis(nt)+o(1)), onde o(1) e' uma coisa pequena, que tende a 0 quando R tende a infinito. Mas isso mostra que a imagem de um circulo grande por P(z) da' n voltas em torno de 0 (a origem) no sentido anti-horario. Por outro lado, se P(0) nao e' 0, entao a imagem de um circulo pequeno centrado em 0 por P esta' pertinho de P(0) e logo nao da' volta nenhuma em torno da origem. Se P(z) nunca e' 0, entao o numero de voltas que a imagem por P de um circulo de centro em 0 e raio R da' em torno de 0 e' sempre inteiro e e' uma funcao continua de R, donde e' constante, absurdo pois varia entre 0 (para R pequeno) e n (para R grande). Portanto em algum momento as imagens desses circulos devem passar por 0 (a unica coisa que pode fazer mudar o numero de voltas), e logo existe c com P(c)=0. Abracos, Gugu Nota:cis(t):=cos(t)+i.sen(t). Ola Gugu,tudo bem?Voce poderia me passar a tal demonstraçao do Teorema Fundamental da Algebra que voce tinha dado na Semana Olimpica?Estou muito interessado em ve-la.O Shine tinha me falado numa demonstraçao bem legal. Vou reproduzir uns trechos que a minha fraca memoria ainda retem.Aproveito e respondo algo aos caras da lista.Ha tempos que eles perguntam disso!! Pegue o polinomio P(x).Ce quer um z complexo tal que P(z)=0.Seja z=r*cis T=x+yi. Substitua a segunda forma na equaçao e voce obtem as curvas Re(x,y)=0 e Im(x,y)=0,com P(x+yi)=Re(x,y)+i*Im(x,y). Mostrando que Re e Im se cortam,acabou.Para tal trabalhe com um disco de raio gigante centrado na origem e mostre que os caras se cortam dentro dele. Melhor que isso:Que tal colocar isto na Eureka? -THE WOOD IS EATING -NO PROBLEM,TEA WITH ME THAT I BOOK YOUR FACE. - Busca Yahoo! O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra. --0-1906017552-1046193829=:98234 Content-Type: text/html; charset=iso-8859-1 Content-Transfer-Encoding: 8bit POla Gugu,tudo bem?Voce poderia me passar a tal demonstraçao do Teorema Fundamental da Algebra que voce tinha dado na Semana Olimpica?Estou muito interessado em ve-la.O Shine tinha me falado numa demonstraçao bem legal.Vou reproduzir uns trechos que a minha fraca memoria ainda retem.Aproveito e respondo algo aos caras da lista.Ha tempos que eles perguntam disso!!/P PPegue o polinomio P(x).Ce quer umnbsp;z complexo tal que P(z)=0.Seja z=r*cis T=x+yi./P PSubstitua a segunda forma na equaçao e voce obtem as curvas /P PRe(x,y)=0 e Im(x,y)=0,com P(x+yi)=Re(x,y)+i*Im(x,y)./P PMostrando que Re e Im se cortam,acabou.Para tal trabalhe com um disco de raio gigante centrado na origem e mostre que os caras se cortam dentro dele./P PMelhor que isso:Que tal colocar isto na Eureka?/PBRBRPFONT face=Arial Black-THE WOOD IS EATING/FONT/P PFONT face=Arial Black-NO PROBLEM,TEA WITH ME THAT I BOOK YOUR FACE./FONT/Ppbrhr size=1ba href=http://br.busca.yahoo.com/;Busca Yahoo! /a/bbr O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra. --0-1906017552-1046193829=:98234-- = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Problema interessante
Oi, JG:
Legal! Usa a mesma idéia básica que a minha, mas você chega lá por uma rota
diferente.
Acho que essa idéia de particionar o conjunto {1,2,...,2n} de duas forma
distintas pode ser usada em várias ocasiões.
É uma técnica boa de se ter no repertório.
Um abraço,
Claudio.
- Original Message -
From: João Gilberto Ponciano Pereira [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Thursday, February 27, 2003 10:50 AM
Subject: RE: [obm-l] Problema interessante
Tome uma partição QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n
elementos cada. Ponha os elementos de A em ordem crescente a_1...a_n e
os
de B em ordem decrescente b_1...b_n. Prove que:
|a_1-b_1| + ... + |a_n-b_n| = n^2
Acabei esquecendo de mandar a resposta, mas aqui vai ela, espero que em
tempo
Vamos chamar os conjuntos:
x = {1 a n} e y={n+1 a 2n}
Vamos supor que o conjunto A é formado de tal forma que possua m elementos
de Y e n-m elementos de X. Logo, o conjunto B é obrigatoriamente formado
por
m elementos de x e n-m elementos de Y.
Então podemos considerar que:
RESULTADO = |a_1-b_1| + ... + |a_n-b_n| = (a1 - b1) + (a2 - b2) + ... +
(am
- bm) - ((am+1 - bm+1) + ... +(an - bn))=
soma a (1 a m) - soma b(1 a m) - soma a(m+1 a n) + soma b(m+1 a n)
Se voltarmos a suposição inicial, soma a (1 a m) + soma b(m+1 a n) é a
soma
dos elementos do conjunto Y, e soma b(1 a m) + soma a(m+1 a n) é a soma
dos
elementos de X.
Logo, temos que:
RESULTADO = soma(n+1 a 2n) - soma(1 a n) = n*n + soma(1 a n) - soma(1 a n)
=n^2
-Original Message-
From: Cláudio (Prática) [mailto:[EMAIL PROTECTED]
Sent: Monday, February 24, 2003 2:48 PM
To: [EMAIL PROTECTED]
Subject: [obm-l] Problema interessante
Taí um resultado inesperado (pelo menos pra mim):
Tome uma partição QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n
elementos cada. Ponha os elementos de A em ordem crescente a_1...a_n e
os
de B em ordem decrescente b_1...b_n. Prove que:
|a_1-b_1| + ... + |a_n-b_n| = n^2.
Um abraço,
Claudio.
=
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
O administrador desta lista é [EMAIL PROTECTED]
=
=
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
O administrador desta lista é [EMAIL PROTECTED]
=
Re: [obm-l] Problema interessante
Essa tecnica e muito boa de se aplicar em problemas!!!Tem o da Eureka 8 que o Humberto resolveu,a Cone Sul e talvez um da IMO.
Cláudio_(Prática) [EMAIL PROTECTED] wrote:
Oi, JG:Legal! Usa a mesma idéia básica que a minha, mas você chega lá por uma rotadiferente.Acho que essa idéia de particionar o conjunto {1,2,...,2n} de duas formadistintas pode ser usada em várias ocasiões.É uma técnica boa de se ter no repertório.Um abraço,Claudio.- Original Message -From: "João Gilberto Ponciano Pereira" <[EMAIL PROTECTED]>To: <[EMAIL PROTECTED]>>Sent: Thursday, February 27, 2003 10:50 AMSubject: RE: [obm-l] Problema interessante "Tome uma partição QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n elementos cada. Ponha os elementos de A em ordem crescente a_1...os de B em ordem decrescente b_1...b_n. Prove que: |a_1-b_1| + ... + |a_n-b_n| = n^2" Acabei esquecendo de mandar a resposta, mas aqui vai ela, espero que em tempo Vamos chamar os conjuntos: x = {1 a n} e y={n+1 a 2n} Vamos supor que o conjunto A é formado de tal forma que possua m elementos de Y e n-m elementos de X. Logo, o conjunto B é obrigatoriamente formadopor m elementos de x e n-m elementos de Y. Então podemos considerar que: RESULTADO = |a_1-b_1| + ... + |a_n-b_n| = (a1 - b1) + (a2 - b2) + ... +(am - bm) - ((am+1 - bm+1) + ... +(an - bn))= soma a (1 a m) - soma b(1 a m) - soma a(m+1 a n) + soma b(m+1 a n) Se voltarmos a suposição inicial, soma a (1 a m) + soma b(m+1 a n) é asoma dos elementos do conjunto Y, e soma b(1 a m) + soma a(m+1 a n) é a somados elementos de X. Logo, temos que: RESULTADO = soma(n+1 a 2n) - soma(1 a n) = n*n + soma(1 a n) - soma(1 a n) =n^2 -Original Message- From: Cláudio (Prática) [mailto:[EMAIL PROTECTED] Sent: Monday, February 24, 2003 2:48 PM To: [EMAIL PROTECTED] Subject: [obm-l] Problema interessante Taí um resultado inesperado (pelo menos pra mim): Tome uma partição QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n elementos cada. Ponha os elementos de A em ordem crescente a_1...os de B em ordem decrescente b_1...b_n. Prove que: |a_1-b_1| + ... + |a_n-b_n| = n^2. Um abraço, Claudio. = 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 O administrador desta lista é <[EMAIL PROTECTED]> ==Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.htmlO administrador desta lista é <[EMAIL PROTECTED]>=Busca Yahoo!
O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra.
[obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] Dúvida de vestibular
Este é um problema interessante! Mas acho que faltou dizer que as cidades em questão fazem parte do mesmo país, ou seja, a cidade A pertence a um país C se existe pelo menos uma estrada que vá de A para alguma cidade pertencente a C. Acho que a solução é mais ou menos assim: A pegadinha é provar que se existe um caminho que vai de Cn para Cm, então existe o caminho de volta de Cm para Cn. Prova: seja Pi o peso do número de estradas da cidade Ci, que é o número de estradas que entram mais o número de estradas que saem. Supondo que o viajante pega o carro de Cm e vai para Cn passando por algumas cidades. Como ele saiu de Cm, o peso Pm será 1. Para as outras cidades, o peso é 2i, pois ele chegou e saiu. Para Cn, o peso é 2i+1, pois ele chegou. Veja que as cidades devem ter Pi par, pois o número de estradas que chegam é o mesmo das que saem. Logo, o ciclo de volta sempre terminará em Cm. Suponha agora um país com 2 cidades A e B. Se A chega a B, temos que B chega a A, e o número de mapas é igual. Acrescentando uma cidade C no país, ela será ligada em A, sem perda de generalidade. Ora, se A chega em C e B chega em A, então B chega em C e, pela volta, C chega em B. Logo, por indução, vc consegue chegar em qualquer cidade de um determinado país com N cidades, o número de mapas possíveis é N-1. -Original Message- From: Nicolau C. Saldanha [mailto:[EMAIL PROTECTED] Sent: Thursday, February 27, 2003 1:41 PM To: [EMAIL PROTECTED] Subject: [obm-l] Re: [obm-l] Re: [obm-l] Dúvida de vestibular Eu [ainda] não sei resolver o problema do Okakome mas... On Wed, Feb 26, 2003 at 04:39:33PM -0300, Domingos Jr. wrote: Oi Pessoal, Estava estudando análise combinatória por uma apostila de um curso pré-vestibular, e encontrei o seguinte problema, que achei interessante, mas minha solução foi muito longa, e não sei se está certa, porque tinha muitos casos. Se estivesse num vestibular, o que faria? Num país, as estradas ligam duas cidades e são de mão única (pode haver mais de uma estrada entre duas cidades). O número de estradas que partem de cada cidade é igual ao número de estradas que chegam nessa cidade. Um mapa da cidade C é um conjunto de rotas que: 1) levam C a cada uma das outras cidades do país, sem passar por uma cidade mais de uma vez. 2) Se uma rota parte de C a D passando por E, então a rota que vai de C a E coincide com o começo da rota de C a D. Prove que o número de mapas da cidade C é igual ao número de mapas de qualquer outra cidade. Acho que esse enunciado não está completo: - se existe uma cidade com nenhuma estrada partindo ou chegando possui um número de rotas 0 e não vai ser igual as demais, até aí é um caso idiota que pode ser excluído do problema. Neste caso não existe nenhum mapa pois é impossível ligar C a X, a cidade sem estradas. O problema fica correto pois o número de mapas é sempre 0. - se existem conjuntos de cidades disjuntos ou seja cidades de um conjunto A não possuem rota nenhuma para as cidades do conjunto B e vice-versa: C1 --- C2 ( 1 estrada de C1 - C2 e outra de C2 - C1 ) C3 == C4 ( 2 estradas de C3 - C4 e duas de C4 - C3 ) neste caso temos que o número de rotas de N(C1) = N(C2) = 1, mas N(C3) = N(C4) = 2. Também neste caso o número de mapas é sempre 0. além disso, há um trecho que eu considero confuso: 2) Se uma rota parte de C a D passando por E, então a rota que vai de C a E coincide com o começo da rota de C a D nessa situação parece que a rota de C a E deve ser única, mas podem haver outras rotas de C até E sem que uma cidade seja visitada mais de uma vez... mesmo que sempre fossem escolhidos os caminhos que passem por menos cidades isso poderia ocorrer já que é permitido haver mais de uma estrada ligando duas cidades. Acho que ajuda considerar o caso em que todas as estradas são de mão dupla: neste caso um mapa nada mais é do que uma árvore maximal e o problema fica trivial. []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 O administrador desta lista é [EMAIL PROTECTED] = = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Problemas em Aberto
Title: Help
Caros colegas da lista:
Muitas vezes um problema proposto na lista,
nenhuma soluo dada nos dias seguintes e logo o problema cai no esquecimento.
Assim, resolvi fazer uma compilao (temo que incompleta) daqueles
problemasda listaque ficaram sem soluo.
1. Seja
A = | A1 |
| A2 |
uma matriz m x n com A1 n x n no singular e A2 uma
matriz (m-n) x n arbitrria
A+ a pseudo-inversa de A, definida como A+ =
(A' * A)^(-1) * A'
prove que ||A+|| = ||(A1)^(-1)||
OBS: A norma aqui induzida:
||A|| = sup||Ax||
||x|| = 1
*
2. possvel que um polinmio de coeficientes
inteiros P(X) irredutvel se fatore em Z/(n) para todo n natural
?
*
3. A e B so cantos opostos de um tabuleiro n x n,
dividido em n^2 quadradinhos por linhas paralelas a seus lados. Em cada
quadradinho traada sua diagonal paralela a AB, tal que o tabuleiro
fica dividido em 2n^2 tringulinhos. O tabuleiro tem (n + 1)^2 pontos que
so vrtices dos quadrinhos e um qrande nmero de segmentos, cada qual
medindo 1 ou sqrt2. Uma pea move-se de A at B atravs dos segmentos. Ela
nunca passa duas vezes pelo mesmo segmento e seu caminho inclui exatamente
dois lados de cada tringulinho. Para qual n isto possvel?
*
4.
A) As medidas dosngulos agudos de um
tringulo pitagrico (tringulo retngulo cujos lados tm medida inteira) no
so inteiras (quando expressos em graus).
B) Se os lados de um tringulo tm medida inteira e
um de seus ngulostem medida inteira, ento esse ngulo mede 60, 90 ou 120
graus.
C) Se um tringulo tem os trs lados e os trs
ngulos com medida inteiraento ele equiltero.
*
5. Nos festejos juninos, 20 casais de danarinos
so colocados em crculo de tal maneira que um homem e uma mulher formando um
par esto situados diametralmente opostos. Durante a dana, dois danarinos
adjacentes trocam de lugar enquanto todos os outros permanecem na mesma posio.
Essa mudana repetida com pares adjacentes at que, na posio final, os dois
danarinos de cada par estejam novamente diametralmente opostos, mas na posio
contrria da inicial. Ento o nmero mnimo de mudanas, de dois danarinos
adjacentes, para acontecer isso :
(a) 20! (b) 400 (c) 10! (d)
19! (e) 20
*
6. D um exemplo de uma sequncia (Xn) de nmeros
reais tal que:
lim ( Xn / n^t )= 0 para todo t
0
e
lim ( [log(n)]^k / Xn )= 0 para todo k
0*
7. Um tringulo tem lados com medida inteira e rea
racional. Prove que uma de suas alturas tem medida inteira e que o p desta
altura est a uma distncia inteira dos vrtices do tringulo.
*
8. Um polgono convexo possui 2n lados.
Prove que o polgono contm no mnimo n diagonais que no
so paralelas a qualquer de seus lados.
*
9. SejaK um inteiro = 2.
infinito
Seja S = SOMATRIO 1 / K^(n^2) =
1/K + 1/K^4 + 1/K^9 + 1/K^16 + ...
n
= 1
Prove que S irracional.
*
10. Um mgico tem cem cartes numerados de 1 a
100.Coloca-os em trs caixas, uma vermelha, uma branca euma azul, de
modo que cada caixa contm pelo menos umcarto.Uma pessoa da platia
escolhe duas das trs caixas,seleciona um carto de cada caixa e anuncia a
soma dosnmeros dos dois cartes que escolheu. Ao saber estasoma, o
mgico identifica a caixa da qual no seretirou nenhum carto.Descreva
todas as maneiras de se colocar todos oscartes nas caixas de modo de que
este truque semprefuncione? (Duas maneiras consideram-se diferentes
sepelo menos um carto colocado numa caixa diferente).
Uma formulao equivalente deste problema
:
Determine todas as parties do
conjunto:
{1, 2, ..., 100}
em trs subconjuntos V, B e A, de forma
que:
V+B, V+A e B+A sejam disjuntos
(V+B = {x + y tais que x pertence a V e y pertence
a B}, idem para os outros dois conjuntos-soma)
Por enquanto s foram encontradas duas
solues:
V = {1, 4, 7, ..., 100} = {3k + 1}
B = {2, 5, 8, ..., 98} = {3k + 2}
A = {3, 6, 9, ..., 99} = {3k}
(alm das outras 5 permutaes de V, B e
A}
e
V = {1}
B = {100}
A = {2, 3, ..., 99}
(tambm j se provou que esta a nica partio -
a menos de permutaes dos conjuntos - que tem dois conjuntos
unitrios)
[obm-l] Problemas em Aberto III
Title: Help
Mais problemas no resolvidos da
lista:
21) (CHINA) 10 pessoas chegaram a uma livraria.
Sabe-se que :A) Todos as pessoas compraram livros de 3 disciplinasB)
Para quaisquer duas pessoas existe ao menos uma disciplina sobre a qual
ambas compraram livros.Enumerando-se as disciplinas sobre as quais
ha livros na livraria, seja M(i) o numero de pessoas que compraram livros da
disciplina "i". Qual e o menor valor positivo possivel para o MAXIMO de
{M(1), M(2), ... } ?
**
22) Trssobre Divises do Plano
22.1) Vrios retngulos so desenhados numa
superfcie plana, de modo que os cruzamentos entre suas linhas produzem 18.769
reas distintas no subdividas. Qual o nmero mnimo de desenhos de retngulos
necessrio para formar o padro descrito?
22.2) Vrios segmentos retos so traados numa
superfcie plana, de modo que os cruzamentos entre suas linhas produzem 1.597
reas distintas no subdividas. Qual o nmero mnimo de traos necessrio para
formar o padro descrito?
22.3) So desenhados 1 + 10^1.234.567.890 tringulos
numa superfcie plana. Qual o nmero mximo de reas distintas no subdividas
que podem ser formadas pela interseco desses tringulos?
OBS: no se deve considerar a regio
exterior aos poligonos
**
23) Trs de Recorrncia:
23.1) Uma planta tal que cada uma de suas
sementes produz um ano apos ter sido plantada , 21 novas sementes e
apartir da , 44 novas sementes a cada ano .Se plantarmos hoje uma
semente e se , toda vez que uma semente for produzida ela for
imediatamente plantada , qtas sementes sero produzidas daqui a n
anos?23.2) o salario de carmelino no mes n sn=a +bn.Sua renda
mensal formada pelo salrio e pelos juros de suas aplicaes
financeiras.Ele poupa anualmente 1/p de sua renda e investe sua poupana a
juros mensais de taxa i.determine a renda de carmelino no mes
i.23.3) 5 times de igual fora disputaro todo o ano um torneio.Uma
taa ser ganha pelo time que vencer 3 vezes consecutivas.Qual a
probabilidade da taa ser ganha nos n primeiros torneios?
*
24) Prove que a soma dos comprimentos dos lados de
um poliedro convexo qualquer maior que 3 vezes a maior distancia entre
dois vertices do poliedro.
25) Um aliengena move-se na superfcie de um
planeta com velocidade no superior a U. Uma espaonave que procura pelo
aliengena move-se com velocidade V. Prove que a espaonave sempre
poder encontrar o alingena se V 10U.
26) Ache todos os pares (x,y) de inteiros
positivostais quez=( 9*x^2 + 50*x*y + 9*y^2)^1/2 seja tambm um nmero
inteiro.
27) Considere um poligono convexo de N lados.
Determine, em funo de N, de quantas maneiras distintas e possivel dividir
este poligono em areas triangulares usando-se tao somente as diagonais deste
poligono.NOTA : Imagine que o poligono esta fixo, nao podendo girar ou
transladar.SUGESTAO : IMAGINE uma divisao valida ! Entao e possivel
imaginar o poligono como um "quebra-cabeca" no qual cada peca e um triangulo
... Dado que de cada vertice partem N-3 diagnais, considere sobre tal
configurcao o efeito de se tracar outras diagonais.
***
[obm-l] Recursivas primitivas.
Caros colegas, --- A) Seja J : N^2 - N tal que J(x,y) = 1/2(( x + y )^2 + 3x + y). Mostre que: a) J é bijetiva; b) J e inv(J) são recursivas primitivas. --- B) Seja a bijeção P : N^2 - N tal que P(m,n) = (2n + 1)*2^m inv(P)(x) = (P1(x), P2(x)) onde P1(x) = exprim(x + 1, 1) e P2(x) = 1/2((x+1)/2^(P1(x)) - 1). Mostre que P, inv(P), P1 e P2 são recursivas primitivas. --- Obs: 1) inv(M) é a inversa de M. 2) Def.: Uma função f: N^(n) - N é dita ser recursiva primitiva (RP) se ela é obtida das funções iniciais por um número finito de aplicações da composição ou recursão. A classe RP é a menor classe que contém as funções iniciais e é fechada sobre composição e recursão. 3) exprim(x,y) é o y-ésimo primo na fatoração de x, para x, y 0 --- Edilon R. -- Nur 1x anmelden und automatisch bis zu 1200 Produktproben und Gutscheine erhalten! http://www.probenking.de/index.cfm?pp_ID=314925 = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Recursivas Primitivas
Oi Edilon,
A)a) Temos: J(x, y) = 1/2 * (x + y) * (x + y + 1) + x;
Vamos provar que J é bijetora:
1) J é sobrejetora: Dado a = 0 seja m o maior natural
tal que 1/2 * m * (m + 1) = a.
Como a - 1/2 * m * (m + 1) é certamente menor que m +
1, já que:
0 + 1 + 2 + 3 + 4 + ... + m = 1/2 * m * (m + 1)
Seja x = a - 1/2 * m * (m + 1) e y = m - x, temos J(x,
y) = a
2) J é injetora: Suponha que J(x0, y0) = J(x1, y1). Se
x0 + y0 x1 + y1, certamente
J(x0, y0) J(x1, y1), pois 1/2 * (x0 + y0) * (x0 + y0
+ 1) - 1/2 * (x1 + y1) * (x1 + y1 + 1) x1 + y1
Logo x0 + y0 = x1 + y1 e fica fácil ver que x0 = x1,
portanto (x0, y0) = (x1, y1)
b) J é claramente recursiva primitiva, pois:
f(a, b) = a + b é r.p.
f(a, b) = a * b é r.p.
f(n) = 1 + 2 + 3 + ... + n é r.p., logo J é r.p.
Para provar que inv (J) é r.p., basta provar que: f é
r.p., onde:
f: N - N, definida por
f(m) := n, onde n é o maior natural tal que 1/2 * n
* (n + 1) = m
Como a função g(a, b) = min {1, a - b} é r.p. é fácil
compor e usar uma recursão para provar que f é r.p.
B) A função h(a, b) = (a + 1) ^ b é r.p., logo P é
claramente r.p.
A função f(n) = n (mod 2) é r.p. e
g(n) = n/2 se n é par e g(n) = 0 se n é ímpar são r.p.
a partir daí é fácil retirar a maior potência de dois
que divide um número e fica fácil provar que a inversa
de P é r.p.
Obs.: Definição precisa de r.p.:
Uma função é dita recursiva primitiva (r.p.) se é
formada pelas seguintes regras:
1) f = c, onde c é uma constante, é r.p. (função
identicamente constante)
2) f(n1, n2, ..., nk) = ni é r.p.
3) f(n) = n + 1 é r.p.
4) Se f, g1, g2, ..., gk são recursivas primitivas
f(g1, g2, ..., gk) é r.p.
5) Se f(0, n2, ..., nk) é r.p. e g(m, n1, n2, ...,
nk) é r.p. e
f(n + 1, n2, ..., nk) = g(f(n, n2, ..., nk), n,
n2, ..., nk) então f é r.p.
Exercício Legal: Prove que a função p(n) = n-ésimo
primo é r.p.
Abraços,
OKAKAMO KOKOBONGO
___
Busca Yahoo!
O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra.
http://br.busca.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
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] Sistemas de eq. lineares
Olá Pessoal, Como resolver estas questões ? Observem que elas são bem parecidas apesar de uma ser formulada pelos professores da FUVEST e outra da CESGRANRIO. (FUVEST) A equação matricial (a11=1, a12=5, a21=2, a22= -1) * (a11=x, a21=y) = lambda* (a11=x, a21=y) admite mais de uma solução se e somente se lambda for igual a: resp: +/ - raiz (11) (CESGRANRIO) Sejam lambda[1] e lambda[2] os valores distintos de lambda para que a equação (a11=2,a12=3, a21=3, a22=2)*(a11=x[1], a21=x[2] ) = lambda*(a11=x[1], a21=x[2] ) admita a solução (a11=x[1], a21=x[2] ) (a11=0, a21=0). Então lambda[1] + lambda[2] é: resp: 4
[obm-l] xadrez e sistemas de equações
Olá pessoal, Estava estudando sistemas de equações lineares e pensei na seguinte relação: Se existem sistemas possíveis (determinado e indeterminado) e impossíveis, como poderiamos classificar um sistema criado a partir do jogo de xadrez onde temos uma matriz quadrada 8 X 8, sendo que m= [1;8] e n=[A;H] (usei barras para indicar intervalos fechados). Pergunta: É possível provar que existe um algoritmo para a seguinte situação: Um jogador que inicie um jogo de xadrez conhecendo este algoritmo sempre saia vitorioso, mesmo que o outro jogador tbém conheça o algoritmo! Para ser mais claro eu só gostaria de saber se existe tal algoritmo mesmo que ninguém o tenha descoberto nestes milhares de anos. Pois se for possível e alguém descobrisse seria uma das maiores descobertas da matemática pois vários matemáticos brilhantes passaram por este planeta e muitos deles gostavam de xadrez, mas nem um descobriu tal algoritmo. Acho que a humanidade deva esperar uma evolução da capacidade cognitiva do ser humano pela seleção natural para tal façanha :-) Obs: Eu espero que não exista, pois se for descoberto, jogos de tabuleiro como xadrez, dama etc... perderiam a graça, pois o algoritmo seria amplamente divulgado.
[obm-l] Re: [obm-l] Problemas em Aberto
Tu de novo Claudio!!!Esse ultimo e da IMO da Coreia e a soluçao do Fabricio(que
fez a prova alias)e muito legal.Tente uma induçao e pense primeiro que asw
caixas sao iguais depois faça vezes tres.
Vou supor que esta coisa de tres angulos e dita em graus.
Talvez saia com SLC:a^2=b^2+c^2-2bc*cos A.
A tarefa e achar os t tais que cos t e racional se t e expresso em graus.
Talvez saia usando complexos.Me lembro de uma prova de que arccos 3/5 e
irracional se dito em graus que usava uns fatos do artigo do Ed na Eureka
6.As Eurekas ce ve na Internet.
-- Mensagem original --
HelpCaros colegas da lista:
Muitas vezes um problema é proposto na lista, nenhuma solução é dada nos
dias seguintes e logo o problema cai no esquecimento. Assim, resolvi fazer
uma compilação (temo que incompleta) daqueles problemas da lista que ficaram
sem solução.
1. Seja
A = | A1 |
| A2 |
uma matriz m x n com A1 n x n não singular e A2 uma matriz (m-n) x n arbitrária
A+ é a pseudo-inversa de A, definida como
A+ = (A' * A)^(-1) * A'
prove que ||A+|| = ||(A1)^(-1)||
OBS: A norma aqui é induzida:
||A|| = sup ||Ax||
||x|| = 1
*
2. É possível que um polinômio de coeficientes inteiros P(X) irredutível
se fatore em Z/(n) para todo n natural ?
*
3. A e B são cantos opostos de um tabuleiro n x n, dividido em n^2
quadradinhos por linhas paralelas a seus lados. Em cada quadradinho é
traçada sua diagonal paralela a AB, tal que o tabuleiro fica dividido
em
2n^2 triângulinhos. O tabuleiro tem (n + 1)^2 pontos que são vértices dos
quadrinhos e um qrande número de segmentos, cada qual medindo 1 ou sqrt2.
Uma peça move-se de A até B através dos segmentos. Ela nunca passa duas
vezes pelo mesmo segmento e seu caminho inclui exatamente dois lados de
cada
triângulinho. Para qual n isto é possível?
*
4.
A) As medidas dos ângulos agudos de um triângulo pitagórico (triângulo
retângulo
cujos lados têm medida inteira) não são inteiras (quando expressos em graus).
B) Se os lados de um triângulo têm medida inteira e um de seus ângulos
tem
medida inteira, então esse ângulo mede 60, 90 ou 120 graus.
C) Se um triângulo tem os três lados e os três ângulos com medida inteira
então ele é equilátero.
*
5. Nos festejos juninos, 20 casais de dançarinos são colocados em círculo
de tal maneira que um homem e uma mulher formando um par estão situados
diametralmente
opostos. Durante a dança, dois dançarinos adjacentes trocam de lugar enquanto
todos os outros permanecem na mesma posição. Essa mudança é repetida com
pares adjacentes até que, na posição final, os dois dançarinos de cada
par
estejam novamente diametralmente opostos, mas na posição contrária da inicial.
Então o número mínimo de mudanças, de dois dançarinos adjacentes, para
acontecer
isso é:
(a) 20! (b) 400 (c) 10! (d) 19! (e) 20
*
6. Dê um exemplo de uma sequência (Xn) de números reais tal que:
lim ( Xn / n^t ) = 0 para todo t 0
e
lim ( [log(n)]^k / Xn ) = 0 para todo k 0
*
7. Um triângulo tem lados com medida inteira e área racional. Prove que
uma
de suas alturas tem medida inteira e que o pé desta altura está a uma distância
inteira dos vértices do triângulo.
*
8. Um polígono convexo possui 2n lados. Prove que o polígono contém no
mínimo n diagonais que não são paralelas a qualquer de seus lados.
*
9. Seja K um inteiro = 2.
infinito
Seja S = SOMATÓRIO 1 / K^(n^2) = 1/K + 1/K^4 + 1/K^9 + 1/K^16 + ...
n = 1
Prove que S é irracional.
*
10. Um mágico tem cem cartões numerados de 1 a 100.
Coloca-os em três caixas, uma vermelha, uma branca e
uma azul, de modo que cada caixa contém pelo menos um
cartão.
Uma pessoa da platéia escolhe duas das três caixas,
seleciona um cartão de cada caixa e anuncia a soma dos
números dos dois cartões que escolheu. Ao saber esta
soma, o mágico identifica a caixa da qual não se
retirou nenhum cartão.
Descreva todas as maneiras de se colocar todos os
cartões nas caixas de modo de que este truque sempre
funcione? (Duas maneiras consideram-se diferentes se
pelo menos um cartão é colocado numa caixa diferente).
Uma formulação equivalente deste problema é:
Determine todas as partições do conjunto:
{1, 2, ..., 100}
em três subconjuntos V, B e A, de forma que:
V+B, V+A e B+A sejam disjuntos
(V+B = {x + y tais que x pertence a V e y pertence a B}, idem para os outros
dois conjuntos-soma )
Por enquanto só foram encontradas duas soluções:
V = {1, 4, 7, ..., 100} = {3k + 1}
B = {2, 5, 8, ..., 98} = {3k + 2}
A = {3, 6, 9, ..., 99} = {3k}
(além das outras 5 permutações de V, B e A}
e
V = {1}
B = {100}
A = {2, 3, ..., 99}
(também já se provou que esta é a única partição - a menos de permutações
dos conjuntos - que tem dois conjuntos unitários)
TEA WITH ME THAT I BOOK YOUR FACE
--
Use o melhor sistema de busca da Internet
Radar UOL -
[obm-l] Re: [obm-l] Problemas em Aberto II
Esse da via ferrea e classico!!Voce pode usar recursao para provar que
isto e o n-esimo numero de Catalan.
Para tal escolha um trem x e conte de quantos modos voce arruma os trens
antes e depois sem violar as regras.Definida a recursao resolva-a.Esse esta
num livro do Knuth.
Tomei a liberdade de corrigi-lo.
-- Mensagem original --
HelpContinuando a compilação de problemas não resolvidos da lista:
11. Dado um corredor com 1 metro de largura, que faz uma curva de 90
graus
e
continua com a mesma largura, qual a figura plana de maior área possível
que pode fazer
essa curva? Observe que o formato dessa area pode ser qualquer e, obviamente,
ela é suposta rigida.
(Acho que este problema ainda está em aberto - e não só aqui na lista.
De
qualquer forma)
**
12. Dada a sequencia a[n+1]= 2a[1]*a[n] - a[n-1] definida para todo n=1
tal que a[0]=100 e a[100]= 0.
a) Mostre que | a[1] |=1.
b) Determine a[2003].
**
13. X, Y e Z são reais positivos e satisfazem o sistema abaixo,
X^2 + XY + (Y^2)/3 = 25
(Y^2)/3 + Z^2 = 9
Z^2 + ZX + X^2 = 16
Encontre o valor de ( XY + 2YZ + 3ZX ).
SUGESTÃO : Você nao precisa, necessariamente, resolver o sistema ...
**
14. De quantas formas podemos colocar N rainhas em um
tabuleiro NxN tal que nenhuma rainha possa enxergar
outra?
obs: uma rainha enxerga outra se ambas estiverem na
mesma coluna, linha ou diagonal.
(Este problema também está em aberto. Talvez valha a pena tentar com Torres
e Bispos ao invés de Rainhas)
***
15.
_ _ _ _ _ _ _ 1 2 ... n _
_|_| |_|_| |_|_|_|_|_|_|_
B \_\ /_/ A
\_|_/
|_|
|_|
|_| C
|o|
Imagine que o 'desenho' acima é uma linha férrea,
aonde o segmento B é extensão do segmento A e o
segmento C se conecta com ambos segmentos.
Os numeros no segmento A representam n vagões
_soltos_ e enumerados.
Os vagoes podem se mover de A - B, A - C e C - B,
mas nunca de C - A nem B - A nem B - C..
De quantas formas eh possivel reagrupar os vagões no
segmento B?
(há espaço suficiente para n vagões tanto em A,
quanto em B e em C)
16. Seja f uma função contínua em [a,b] e diferenciável em (a,b).
A) É possível que, apesar de existir, f' seja descontínua em todo ponto
de
(a,b).
B) Em caso afirmativo, será que a condição f(a) f(b) é suficiente para
garantir que exista um sub-intervalo [c,d] (a = c d = b) onde f é crescente?
**
17. a, b, c, d são números reais não-negativos tais que:
ab+ac+ad+bc+bd+cd+abc+abd+acd+bcd=2.
Mostre que:
3(a+b+c+d)=4(ab+ac+ad+bc+bd+cd).
*
18. Numa loteria sao sorteados 7 numeros escolhidos aleatoriamente de
{1,2,3,...,48,49}.
Cada cartao de apostas deve ser preenchido com exatamente 7 numeros. Uma
pessoa pode pode apostar quantos cartoes desejar sem pagar nada, desde
que
quaisquer dois cartoes de sua aposta tenham, NO MAXIMO, uma dezena em comum.
O primeiro premio e dado a pessoa que acertar o maior numero de triplos.
A) Exiba uma aposta gratuita que tenha a maxima probabibilidade de ganhar
o primeiro premio.
B) Qual o valor da probabilidade acima ?
***
19. Suponha que os números da forma 2^x * 3^y (x, y: inteiros não negativos)
são colocados em ordem crescente. Prove que existem termos consecutivos
-
digamos 2^a * 3^b e 2^c * 3^d - tais que
|2^a * 3^b - 2^c * 3^d| torna-se arbitrariamente grande.Generalize
*
20. Duas de Análise Real:
A) Prove que se f:{a, b) - R é contínua em c em (a,b) e lim x- c
f'(x) = L, então f'(c) = L. A partir daí, conclua que derivadas jamais
apresentam descontinuidades do tipo salto. Conclua também que se f' é
monotônica em um intervalo I, então f'é contínua em I.
B) Suponhamos que f seja diferenciável em R e seja k0. Mostre que:
B.1) se k0, então lim x - infinito f'(x) + k f(x) = L, L em R, implica
que lim x- infinito f('x) = 0 e lim x- infinito f(x) = L/k
B.2) se k0, então lim x- infinito f'(x) + k f(x) = L, L em R, só é
possível se lim x- e^(kx) f(x) = 0, caso em que temos também lim x-
infinito f('x) = 0 e lim x- infinito f(x) = L/k
sugestão : defina h(x) = e^(kx) f(x) g(x) = e^(kx) . Logo, f(x) =
h(x)/g(x). Use L'Hopital.
**
TEA WITH ME THAT I BOOK YOUR FACE
--
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
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] Sobre as minhas origens...
Oi Nicolau, Vou dar um outro enunciado, para finalizar qualquer dúvida que ainda reste sobre este problema: Seja G um grafo orientado conexo, com um circuito euleriano (o grau de entrada é igual ao grau de saída em cada vértice do grafo). Prove que para cada vértice o número de árvores orientadas enraizadas nesse vérticie é sempre o mesmo. Sobre o meu nome, eu não sei a origem precisa, mas estão relacionados com a origem do pai da minha mãe, de uma antiga tribo do Zimbabwe, e o meu pai ser japonês. Abraços, OKAKAMO (MATSUBASHI) KOKOBONGO. ___ Busca Yahoo! O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra. http://br.busca.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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] origem do meu nome
Mas porque o interesse particular no meu nome. Existem tantos outros nomes estranhos na lista, por exemplo, porque o prática de Cláudio_(Prática)? Abraços, OKAKAMO KOKOBONGO. ___ Busca Yahoo! O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra. http://br.busca.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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Bem vindo OKAKAMO
Caros colegas,
Em primeiro lugar, gostaria de aproveitar a ocasiao para saudar o grande
Okakamo Kokobongo, que chegou para abrilhantar sobremaneira as discussoes
desta lista!
Sobre a solucao abaixo eu tenho minhas duvidas: ao fixar uma variavel
diminuimos o numero de variaveis mas nao necessariamente o grau do
polinomio, e podemos perder a condicao de o grau total ser menor que o
numero de variaveis.
Eu faria o 1 assim:nosso numero de solucoes modulo q e' a soma sobre
todos os (x_1,...,x_n) em (Z/qZ)^n de 1-P(x_1,...,x_n)^(q-1), pelo pequeno
teorema de Fermat, mas a soma de cada monomio da expressao acima (digamos
c.x1^i1.x2^i2.xn^in) e' o mod q, pois e' c vezes o produto dos S(i_j),
onde S(i_j) e' a soma para x em Z/qZ de x^(i_j), que e' sempre 0 se
0=i_jq-1 (no caso i_j0, multiplique todos os x por a onde a e' um cara
invertivel tal que a^(i_j) nao e' 1 mod q; o caso i_j=0 e' trivial) , e por
outro lado algum dos i_j deve ser menor que q-1, pois o grau total e' menor
que n(q-1).
O 2 eu consegui fazer usando mais algebra do que eu gostaria (e e' claro
que precisa supor P monico). Se a e' uma raiz de P entao a^(1/q) pertence a
K:=Q(a) ou [Q(a^(1/q):Q(a)]=q, e no segundo caso P(x^q) e' claramente
irredutivel, pois Q[a^(1/q):Q]=q.n. No primeiro caso, o produto sobre todos
os automorfismos s de K de (x-s(a^(1/q)) e' um polinomio em Q[x], e seu
ultimo coeficiente elevado a q e' (-1)^q.P(0).
Confio em que o Doutor Okakamo tenha uma solucao mais elementar...
Abracos e saudacoes revolucionarias,
Gugu
1)
acho que d=E1 pra resolver assim:
prove que para polin=F4mios quaisquer de 1 vari=E1vel o n=FAmero de =
solu=E7=F5es =E9 m=FAltiplo de q
suponha que para polin=F4mios com n=FAmero de vari=E1veis 1 =3D k =3D =
n isso vale
pegue um polin=F4mio de k+1 vari=E1veis p(x1, x2, ..., xk, x[k+1])
os valores poss=EDveis para x[k+1] s=E3o { 0, 1, 2, ..., q-1 }
considere as solu=E7=F5es de p(x1, x2, ..., xk, 0), p(x1, x2, ..., xk, =
1), ... p(x1, x2, ..., xk, q-1), ou seja, no mesmo polin=F4mio p aplique =
o valor fixado de x[k+1] e assim obtenha um polin=F4mio de k =
vari=E1veis, que por hip. de indu=E7=E3o possui um n=FAmero de =
solu=E7=F5es m=FAltiplo de q.
O n=FAmero de solu=E7=F5es de p passa ent=E3o a ser a soma dos nrs. de =
solu=E7=F5es de cada polin=F4mio com x[k+1] fixado, e essa soma =E9 =
m=FAltiplo de q.
- Original Message -=20
From: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Wednesday, February 26, 2003 4:55 PM
Subject: [obm-l] Bem vindo OKAKAMO
Oi Professor,
Continua dando aulas de combinat=F3ria em cursinhos? H=E1 muito tempo =
eu n=E3o lia as mensagens da lista, e sua participa=E7=E3o vai dar um =
novo animo para ela. Tenho dois problemas legais que n=E3o consegui =
resolver:
1) se p =E9 um polin=F4mio de n vari=E1veis, de grau total menor que =
n, ent=E3o o n=FAmero de solu=E7=F5es de p =3D 0 (mod q) onde q e um =
n=FAmero primo, =E9 multiplo de q.
2) se p(x) =E9 um polin=F4mio irredut=EDvel e (p(0))^1/q n=E3o =E9 =
inteiro ent=E3o p(x^q) =E9 irredut=EDvel, onde q =E9 um primo =EDmpar.
Obrigado,
Marcio
___
Super iG - Internet em Alta Velocidade - http://www.superig.com.br/
=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =
Instru=E7=F5es para entrar na lista, sair da lista e usar a lista em =
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador =
desta lista =E9 =
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--=_NextPart_000_0059_01C2DDD7.61B6C3F0
Content-Type: text/html;
charset=Windows-1252
Content-Transfer-Encoding: quoted-printable
!DOCTYPE HTML PUBLIC -//W3C//DTD HTML 4.0 Transitional//EN
HTMLHEAD
META http-equiv=3DContent-Type content=3Dtext/html; =
charset=3Dwindows-1252
META content=3DMSHTML 6.00.2800.1141 name=3DGENERATOR
STYLE/STYLE
/HEAD
BODY bgColor=3D#ff
DIVFONT face=3DArial size=3D21)/FONT/DIV
DIVFONT face=3DArial size=3D2/FONTnbsp;/DIV
DIVFONT face=3DArial size=3D2acho que d=E1 pra resolver =
assim:/FONT/DIV
DIVFONT face=3DArial size=3D2prove que para polin=F4mios quaisquer =
de 1 vari=E1vel o=20
n=FAmero denbsp;solu=E7=F5es =E9 m=FAltiplo de q/FONT/DIV
DIVFONT face=3DArial size=3D2/FONTnbsp;/DIV
DIVFONT face=3DArial size=3D2suponha que para polin=F4miosnbsp;com =
n=FAmero=20
denbsp;vari=E1veis 1 lt;=3D k lt;=3D n isso vale/FONT/DIV
DIVFONT face=3DArial size=3D2/FONTnbsp;/DIV
DIVFONT face=3DArial size=3D2pegue um polin=F4mio de k+1 vari=E1veis =
p(x1, x2, ...,=20
xk, x[k+1])/FONT/DIV
DIVFONT face=3DArial size=3D2os valores poss=EDveis para
[obm-l] Treinamento no Rio
Caros colegas, Na primeira segunda-feira depois do carnaval (10/2), no IMPA, as 14:00 horas comecam as reunioes semanais de treinamento olimpico abertas ao publico, que visam entre outras coisas treinar para a IMO. Somos responsaveis por estas reunioes eu e o Luciano, mas deveremos tambem ter aulas de outros ilustres colegas (oi Nicolau! oi Okakamo! oi Morgado! oi Wagner!). Estao todos convidados (especialmente o pessoal do Rio...)! Abracos, Gugu = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Re: [obm-l] Dúvida de vestibular
Eu [ainda] não sei resolver o problema do Okakome mas... On Wed, Feb 26, 2003 at 04:39:33PM -0300, Domingos Jr. wrote: Oi Pessoal, Estava estudando análise combinatória por uma apostila de um curso pré-vestibular, e encontrei o seguinte problema, que achei interessante, mas minha solução foi muito longa, e não sei se está certa, porque tinha muitos casos. Se estivesse num vestibular, o que faria? Num país, as estradas ligam duas cidades e são de mão única (pode haver mais de uma estrada entre duas cidades). O número de estradas que partem de cada cidade é igual ao número de estradas que chegam nessa cidade. Um mapa da cidade C é um conjunto de rotas que: 1) levam C a cada uma das outras cidades do país, sem passar por uma cidade mais de uma vez. 2) Se uma rota parte de C a D passando por E, então a rota que vai de C a E coincide com o começo da rota de C a D. Prove que o número de mapas da cidade C é igual ao número de mapas de qualquer outra cidade. Acho que esse enunciado não está completo: - se existe uma cidade com nenhuma estrada partindo ou chegando possui um número de rotas 0 e não vai ser igual as demais, até aí é um caso idiota que pode ser excluído do problema. Neste caso não existe nenhum mapa pois é impossível ligar C a X, a cidade sem estradas. O problema fica correto pois o número de mapas é sempre 0. - se existem conjuntos de cidades disjuntos ou seja cidades de um conjunto A não possuem rota nenhuma para as cidades do conjunto B e vice-versa: C1 --- C2 ( 1 estrada de C1 - C2 e outra de C2 - C1 ) C3 == C4 ( 2 estradas de C3 - C4 e duas de C4 - C3 ) neste caso temos que o número de rotas de N(C1) = N(C2) = 1, mas N(C3) = N(C4) = 2. Também neste caso o número de mapas é sempre 0. além disso, há um trecho que eu considero confuso: 2) Se uma rota parte de C a D passando por E, então a rota que vai de C a E coincide com o começo da rota de C a D nessa situação parece que a rota de C a E deve ser única, mas podem haver outras rotas de C até E sem que uma cidade seja visitada mais de uma vez... mesmo que sempre fossem escolhidos os caminhos que passem por menos cidades isso poderia ocorrer já que é permitido haver mais de uma estrada ligando duas cidades. Acho que ajuda considerar o caso em que todas as estradas são de mão dupla: neste caso um mapa nada mais é do que uma árvore maximal e o problema fica trivial. []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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Re: [obm-l] Algum_progresso_(seqüência_de_potências)
On Wed, Feb 26, 2003 at 03:29:41PM -0300, Domingos Jr. wrote: Sinceramente, acho que você não deveria colocar um problema desses na categoria dos triviais, primeiro porque o nível dos participantes não é homogêneo e é para muitos esse é um problema difícil. Confesso que perdi um bom tempo para sacar que era possível aplicar o tma. de Euler repetidamente ao problema para chegar a solução, esse problema certamente não foi trivial para mim. Aliás, fiquei curioso, foi você quem criou o problema, simplesmente encontrou e o resolveu ou já o encontrou resolvido? Este problema, tanto quanto eu saiba, foi inventado pelo Gugu e por mim quando preparávamos uma prova de seleção para a IMO (e entrou na prova). A nossa solução era bem parecida com a apresentada pelo Okakome. Note que seguindo a solução já apresentada não é muito difícil obter uma estimativa para o ponto a partir do qual os algarismos ficam constantes. []s, N. PS: Quando você encontrar um problema que fale dos últimos 1000 algarismos de alguma coisa é uma boa aposta dizer que tem o dedo do Gugu. = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Dúvida de vestibular
On Thu, Feb 27, 2003 at 01:40:56PM -0300, Nicolau C. Saldanha wrote: Eu [ainda] não sei resolver o problema do Okakome mas... Aliás, Okakamo. Desculpe. De que origem é este nome? Procurando no Google encontrei um Okakamo Matsubachi mencionado na Eureka 14 e um Kokobongo em http://cs.tklan.com.br:8001/stats/player_a29rb2Jvbmdv.html que parece ser o apelido de um jogador em algum tipo de jogo. Também há um CD Kokobongo mencionado em http://sites.uol.com.br/marcomarrero/planeta/planeta0709/pagina1.htm e um Kokobongo Bar em Balneário Gaivota: http://www.jmnet.com.br/colunistas/claudete_matos.htm O nome Kokobongo também aparece em uma página em japonês: http://hamq.jp/stdB.cfm?i=DREAMNIGHTpn=13 []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 O administrador desta lista é [EMAIL PROTECTED] =
