Re: [obm-l] Problemas em Aberto III
Sauda,c~oes, Oi Cláudio, Acho que no livro (dos anos 60/70?) Flow Network de Ford and Fulkerson vc encontra a demonstração deste teorema. []'s Luís -Mensagem Original- De: Nicolau C. Saldanha [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Enviada em: sexta-feira, 7 de março de 2003 16:03 Assunto: Re: [obm-l] Problemas em Aberto III On Fri, Mar 07, 2003 at 12:05:14PM -0300, Cláudio (Prática) wrote: Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Será que esta demonstração está correta? = 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] Problemas em Aberto III
- Original Message - From: Nicolau C. Saldanha [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, March 07, 2003 9:15 AM Subject: Re: [obm-l] Problemas em Aberto III On Thu, Mar 06, 2003 at 04:28:24PM -0300, Cláudio (Prática) wrote: Caro Nicolau: No no. 24, eu empaquei exatamente na hora de provar que existem 3 caminhos disjuntos de X até Y. Como eu não conheço teoria dos grafos, maxflow-mincut (seja lá o que isso for) é novidade pra mim. Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Observe que M = N é trivial. Caro Nicolau: Será que esta demonstração está correta? Suponhamos que M N. Isso significa que qualquer corte tem mais do que N arestas. Tome um (possivelmente o único) fluxo de tamanho N, o qual liga os vértices X e Y e remova uma aresta de cada um dos N caminhos deste fluxo. Após a remoção das arestas será impossível ir de X a Y, pois cada caminho possível terá sido interrompido. Logo, as N arestas removidas constituem um corte == contradição, pois qualquer corte tem mais do que N arestas == M = N. Assim, concluimos que M = N. 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] =
Re: [obm-l] Problemas em Aberto III
On Thu, Mar 06, 2003 at 04:28:24PM -0300, Cláudio (Prática) wrote: Caro Nicolau: No no. 24, eu empaquei exatamente na hora de provar que existem 3 caminhos disjuntos de X até Y. Como eu não conheço teoria dos grafos, maxflow-mincut (seja lá o que isso for) é novidade pra mim. Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Observe que M = N é 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] =
Re: [obm-l] Problemas em Aberto III
On Fri, Mar 07, 2003 at 12:05:14PM -0300, Cláudio (Prática) wrote: Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Será que esta demonstração está correta? Suponhamos que M N. Isso significa que qualquer corte tem mais do que N arestas. Tome um (possivelmente o único) fluxo de tamanho N, o qual liga os vértices X e Y e remova uma aresta de cada um dos N caminhos deste fluxo. Após a remoção das arestas será impossível ir de X a Y, pois cada caminho possível terá sido interrompido. Logo, as N arestas removidas constituem um corte == contradição, pois qualquer corte tem mais do que N arestas == M = N. Assim, concluimos que M = N. Infelizmente não é tão simples. Retirar N arestas quaisquer, uma por caminho, não necessariamente desconecta o grafo (mesmo se N for máximo). Exemplo: x .---.---.---.---.---.---. | | | | | | | .---.---.---.---.---.---. y Neste exemplo claramente M=N=2 mas se tomarmos os dois caminhos como sendo o bordo superior e o bordo inferior e retirarmos duas arestas para obter x .---.---. .---.---.---. | | | | | | | .---.---.---. .---.---. y isso não desconectou o grafo. É claro que *teríamos* desconectado se tivéssemos escolhido ao invés x .---.---. .---.---.---. | | | | | | | .---.---. .---.---.---. y e é preciso provar que sempre existe uma escolha de N arestas que de fato desconecta (se N for máximo, claro). []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] =
Re: [obm-l] Problemas em Aberto III
Caro Nicolau: No no. 24, eu empaquei exatamente na hora de provar que existem 3 caminhos disjuntos de X até Y. Como eu não conheço teoria dos grafos, maxflow-mincut (seja lá o que isso for) é novidade pra mim. Você poderia recomendar alguma bibliografia a respeito (especialmente na internet)? Obrigado e um abraço, Claudio. - Original Message - From: Nicolau C. Saldanha [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, March 02, 2003 10:04 AM Subject: Re: [obm-l] Problemas em Aberto III On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote: 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. Sejam x e y vértices a distância máxima. Queremos construir três caminhos formados por arestas indo de x até y, e estes caminhos devem ser disjuntos (exceto por x, y e possivelmente algum vértice no meio). Ora, por maxflow-mincut estes três caminhos só *não* existem se existir um corte feito por duas arestas, ou seja, se existirem duas arestas que, se removidas, desconectam o grafo formado por vértices e arestas. Mas isso estaria em contradição com o fato de termos um poliedro convexo. 25) Um alienígena move-se na superfície de um planeta com velocidade não superior a U. Uma espaçonave que procura pelo alienígena move-se com velocidade V. Prove que a espaçonave sempre poderá encontrar o alinígena se V 10U. Não entendi nada. Quando é que a nave encontra o alienígena? []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] =
Re: [obm-l] Problemas em Aberto III
Caro Paulo:
Neste problema:
Seja S o conjunto de todas as sequencia FINITAS de INTEIROS POSITIVOS
tais que se {Xn}=X1, X2, ...,Xn pertence a S entao para todo P N,
X1+X2+...+Xp NAO E congruo a 1 modulo 3. Mostre que existe uma bijecao
entre
S e o conjunto de todos os impares positivos.
eu fiz o seguinte raciocínio:
Seja N = conjunto dos inteiros positivos.
Então:
1. Existe uma bijeção entre quaisquer dois conjuntos enumeráveis;
2. O conjunto dos ímpares positivos é enumerável;
3. Pelas definições básicas de função (conjunto de pares ordenados com
primeiras coordenadas distintas duas a duas) e sequência (função cujo
domínio é N) cada sequência de S consiste de um conjunto de pares ordenados
{ (1,X1), (2,X2), ..., (n,Xn) , ... } onde cada Xi é um inteiro positivo e
onde existe um inteiro positivo n, tal que Xk = 0 para k n. Assim, cada
sequência de S é um subconjunto de N x (N U {0}), o qual é enumerável. Logo,
cada sequência de S é um conjunto enumerável.
3. S é enumerável, por ser uma reunião enumerável de conjuntos enumeráveis.
Logo, existe uma bijeção entre S e o conjunto de todos os ímpares positivos.
Uma outra alternativa é fazer a correspondência:
(X1, ..., Xn) == 0,X1X2...Xn (ou seja, cada sequencia corresponde a um
número obtido justapondo-se os Xi's e tratando-os como decimais)
Como cada sequencia é finita, as decimais serão finitas e os números obtidos
serão todos racionais.
Assim, teremos obtido uma bijeção entre S e um subconjunto dos racionais.
Logo, S será enumerável.
Tá certo o que eu fiz?
O estranho é que em nenhum momento eu usei a propriedade aritmética das
sequências.
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]
=
Re: [obm-l] Problemas em Aberto III
Ola Prof Nicolau e demais
colegas desta lista ... OBM-L,
Representando por (um ponto) N a nave, traçamos todas as tangentes à esfera
que passam por N. Isso define uma calota na esfera. Se o alienígena estiver
nesta calota entao entende-se que a Nave o
encontrou.
A solução deve prescindir da distancia da Nave à superficie do planeta e de
eventuais variações nos sentidos e modulos das velocidades envolvidas.
A ideia - do Claudio/Pratica/ - de publicar os problemas que foram
propostos nesta lista e que permanecem em aberto me parece muito boa
Um famoso problema pode se reformulado da seguinte maneira :
Seja S o conjunto de todas as sequencia FINITAS de INTEIROS POSITIVOS
tais que se {Xn}=X1, X2, ...,Xn pertence a S entao para todo P N,
X1+X2+...+Xp NAO E congruo a 1 modulo 3. Mostre que existe uma bijecao entre
S e o conjunto de todos os impares positivos.
Um Abraço
Paulo Santa Rita
3,1900,040303
From: Nicolau C. Saldanha [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Problemas em Aberto III
Date: Sun, 2 Mar 2003 10:04:30 -0300
25) Um alienígena move-se na superfície de um planeta com velocidade
não superior a U. Uma espaçonave que procura pelo alienígena move-se com
velocidade V. Prove que a espaçonave sempre poderá encontrar o
alinígena se V 10U.
Não entendi nada. Quando é que a nave encontra o alienígena?
[]s, N.
_
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
O administrador desta lista é [EMAIL PROTECTED]
=
Re: [obm-l] Problemas em Aberto III
Oi pessoal ! Parece que falta alguma coisa no enunciado do problema 25, do modo como o problema é apresentado V 10U não garante que a nave vá encontrar o alienígena. Por exemplo, o alienígena e a nave podem ficar andando em trajetórias circulares que não se cruzam. André T. - Original Message - From: Nicolau C. Saldanha [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, March 02, 2003 10:04 AM Subject: Re: [obm-l] Problemas em Aberto III On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote: 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. Sejam x e y vértices a distância máxima. Queremos construir três caminhos formados por arestas indo de x até y, e estes caminhos devem ser disjuntos (exceto por x, y e possivelmente algum vértice no meio). Ora, por maxflow-mincut estes três caminhos só *não* existem se existir um corte feito por duas arestas, ou seja, se existirem duas arestas que, se removidas, desconectam o grafo formado por vértices e arestas. Mas isso estaria em contradição com o fato de termos um poliedro convexo. 25) Um alienígena move-se na superfície de um planeta com velocidade não superior a U. Uma espaçonave que procura pelo alienígena move-se com velocidade V. Prove que a espaçonave sempre poderá encontrar o alinígena se V 10U. Não entendi nada. Quando é que a nave encontra o alienígena? []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] =
Re: [obm-l] Problemas em Aberto III
On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote: 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. Sejam x e y vértices a distância máxima. Queremos construir três caminhos formados por arestas indo de x até y, e estes caminhos devem ser disjuntos (exceto por x, y e possivelmente algum vértice no meio). Ora, por maxflow-mincut estes três caminhos só *não* existem se existir um corte feito por duas arestas, ou seja, se existirem duas arestas que, se removidas, desconectam o grafo formado por vértices e arestas. Mas isso estaria em contradição com o fato de termos um poliedro convexo. 25) Um alienígena move-se na superfície de um planeta com velocidade não superior a U. Uma espaçonave que procura pelo alienígena move-se com velocidade V. Prove que a espaçonave sempre poderá encontrar o alinígena se V 10U. Não entendi nada. Quando é que a nave encontra o alienígena? []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] 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.
***
