Re: [obm-l] violencia
On Sat, Sep 07, 2002 at 11:45:37PM +, Fernanda Medeiros wrote: Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Sei que um monte de gente já respondeu mas gostei da questão e quero dar a minha solução. Antes de mais nada devemos entender que no enunciado estão implicitamente excluídos os bandidos suicidas (inimigos deles próprios)... (a) Se existe algum bandido x que é odiado por uma infinidade de outros bandidos, escolhemos todos os bandidos que odeiam x. Supomos a partir de agora que qualquer bandido é odiado apenas por um número finito de outros bandidos: assim a presença de um bandido na reunião só exclui um número finito de outros (o que ele odeia e os que o odeiam). É bem fácil montar um conjunto infinito: pegue um bandido qualquer, um que não tenha sido excluido pelo primeiro, um que não tenha sido excluido pelos dois primeiros,... A qualquer momento apenas um número finito de bandidos foi excluido logo podemos continuar. (b) Se os bandidos se chamam 0, 1, 2, 3, ..., n, ... e cada bandido odeia todos os que têm um número menor do que o dele é impossível reunir sequer dois bandidos. Mas o item que me parece mais interessante é: (c) se cada bandido odeia k outros bandidos (k fixo), ainda é possível reunir uma infinidade de bandidos? A resposta ainda é sim e provamos isso por indução em k. Imagine que cada bandido ordena seus inimigos de 1 a k. Por indução, podemos formar um subconjunto em que ninguém odeia ninguém nas (k-1) primeiras posições (mas talvez odeie na posição k). Acabamos de reduzir o problema ao item (a)... []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] violencia
Olá, Vinicius Cada vez que voce retira um elemento de C e coloca em R, na verdade voce mudou o conjunto C. Ou seja, cada escolha que voce fez, no processo indutivo, foi sobre um conjunto diferente. É semelhante a demonstração de que todo conjunto infinto possui um subconjunto enumerável, em que, dado um conjunto V, construímos indutivamente um conjunto S colocando nele, a cada passo, um elemento de V que não está em S, usando o Axioma da Escolha From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sun, 8 Sep 2002 18:41:45 -0300 Oi Rogério Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu nem tinha infinitos conjuntos! Apenas conjuntos infinitos. Até mais Vinicius - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 2:17 PM Subject: Re: [obm-l] violencia É bom notar que essa solução usa o axioma da escolha (de infinitos conjuntos não-vazios, escolhemos um elemento de cada). É essencial o axioma da escolha para resolvê-lo? From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 - Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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] = _ MSN Photos is the easiest way to share and print your photos: http://photos.msn.com/support/worldwide.aspx = 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] violencia
Você acha que a utilização do axioma da escolha invalida uma prova? Por exemplo, a prova de que todo conjunto aberto de R é dado por uma união numerável de intervalos abertos disjuntos também utiliza o axioma da escolha. Artur = 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] violencia e axioma da escolha
Não sei se entendi direito, mas, ao meu ver, não teríamos conjuntos dois a dois disjuntos e tal propriedade é necessária para aplicar o axioma da escolha (ou não?). De qualquer forma, não poderíamos mapear os bandidos nos números inteiros? Assim teríamos uma função de escolha que pegaria em C o bandido mapeado no menor inteiro tal que satisfaça aquelas condições para entrar em R. Se temos uma função de escolha então podemos escolhê-los independentemente do axioma da escolha. Agradeço esclarecimentos Vinicius Fortuna - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Monday, September 09, 2002 12:08 PM Subject: Re: [obm-l] violencia Olá, Vinicius Cada vez que voce retira um elemento de C e coloca em R, na verdade voce mudou o conjunto C. Ou seja, cada escolha que voce fez, no processo indutivo, foi sobre um conjunto diferente. É semelhante a demonstração de que todo conjunto infinto possui um subconjunto enumerável, em que, dado um conjunto V, construímos indutivamente um conjunto S colocando nele, a cada passo, um elemento de V que não está em S, usando o Axioma da Escolha From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sun, 8 Sep 2002 18:41:45 -0300 Oi Rogério Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu nem tinha infinitos conjuntos! Apenas conjuntos infinitos. Até mais Vinicius - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 2:17 PM Subject: Re: [obm-l] violencia É bom notar que essa solução usa o axioma da escolha (de infinitos conjuntos não-vazios, escolhemos um elemento de cada). É essencial o axioma da escolha para resolvê-lo? From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 - Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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] violencia e axioma da escolha
At 17:16 09/09/02 -0300, you wrote: Não sei se entendi direito, mas, ao meu ver, não teríamos conjuntos dois a dois disjuntos e tal propriedade é necessária para aplicar o axioma da escolha (ou não?). De qualquer forma, não poderíamos mapear os bandidos nos números inteiros? Assim teríamos uma função de escolha que pegaria em C o bandido mapeado no menor inteiro tal que satisfaça aquelas condições para entrar em R. Se temos uma função de escolha então podemos escolhê-los independentemente do axioma da escolha. Acho que o conjunto dos bandidos não precisa ser enumerável. Bruno Leite http://www.ime.usp.br/~brleite Agradeço esclarecimentos Vinicius Fortuna - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Monday, September 09, 2002 12:08 PM Subject: Re: [obm-l] violencia Olá, Vinicius Cada vez que voce retira um elemento de C e coloca em R, na verdade voce mudou o conjunto C. Ou seja, cada escolha que voce fez, no processo indutivo, foi sobre um conjunto diferente. É semelhante a demonstração de que todo conjunto infinto possui um subconjunto enumerável, em que, dado um conjunto V, construímos indutivamente um conjunto S colocando nele, a cada passo, um elemento de V que não está em S, usando o Axioma da Escolha From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sun, 8 Sep 2002 18:41:45 -0300 Oi Rogério Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu nem tinha infinitos conjuntos! Apenas conjuntos infinitos. Até mais Vinicius - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 2:17 PM Subject: Re: [obm-l] violencia É bom notar que essa solução usa o axioma da escolha (de infinitos conjuntos não-vazios, escolhemos um elemento de cada). É essencial o axioma da escolha para resolvê-lo? From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 - Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = Instruções para entrar na lista, sair da lista e usar a lista em http
RE: [obm-l] violencia
Title: RE: [obm-l] violencia Bom, com relação à primeira questão. Comecemos pela segunda parte e suponhamos, conforme vc disse, que cada bandido tenha um número finito de inimigos. Vou supor que, embora variando com o bandido, este número é conhecido para cada bandido. Escolha um bandido. Isto é possível pois há infinitos (Meu Deus!!) Dado que este bandido tem um número finito de inimigos e existem infinitos bandidos, podemos escolher um bandido que não seja inimigo dele. Logo, a base de nosso processo indutivo está formada. Suponhamos agora que, para algum natural n, tenhamos escolhido n bandidos tais que ninguém seja inimigo de ninguém. Suponhamos. Ora, cada um destes n bandidos tem um número apenas finito de inimigos. Logo, o número total de bandidos que são inimigos de um destes n bandidos escolhidos é finito - pois é a soma de n parcelas finitas.. Mas, temos infinitos bandidos, de modo que podemos escolher um que não seja inimigo de nenhum dos n que já escolhemos (e, é claro, que não seja um membro deste conjunto de n que escolhemos). Com isto, obtemos n +1 bandidos distintos tais que, neste conjunto, ninguém vai matar ninguém. A ponte de nosso processo indutivo está portanto formada, e mostra que nosso processo de escolha pode prosseguir indefinidamente. OK? Podemos dizer que geramos um seqüência B_n de bandidos tal que, dados quaisquer naturais m e n, com mn, então B_n não quer matar B_m. Estou assumindo, implicitamente, que ninguém quer cometer suicídio. A primeira parte de sua 1a questão é um caso particular da segunda, obtida quando cada bandido tem apenas um inimigo. Espero ter ajudado Artur Artur Costa Steiner SHCGN 705 Bloco P Ap 506 Brasília - DF Cep 70730-776 61 340-9788 61 913-3745 61 9987-0709 -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Fernanda Medeiros Sent: Saturday, September 07, 2002 8:46 PM To: [EMAIL PROTECTED] Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? 2.Encontre todas as soluções em inteiros não negativos para: 2^x +3^y =z^2 3.Encontre todos os inteiros positivos (x,y) tais q 7^x - 3^y =4 Valeu!! FÊ _ Converse com seus amigos online, faça o download grátis do MSN Messenger: 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] violencia
Title: RE: [obm-l] violencia Existe uma passagem que, ao meu ver, está falsa. Observe abaixo. - Original Message - From: Artur Costa Steiner To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 11:24 AM Subject: RE: [obm-l] violencia Bom, com relação à primeira questão. Comecemos pela segunda parte e suponhamos, conforme vc disse, que cada bandido tenha um número finito de inimigos. Vou supor que, embora variando com o bandido, este número é conhecido para cada bandido. Escolha um bandido. Isto é possível pois há infinitos (Meu Deus!!) Dado que este bandido tem um número finito de inimigos e existem infinitos bandidos, podemos escolher um bandido que não seja inimigo dele. Logo, a base de nosso processo indutivo está formada. Suponhamos agora que, para algum natural n, tenhamos escolhido n bandidos tais que ninguém seja inimigo de ninguém. Suponhamos. Ora, cada um destes n bandidos tem um número apenas finito de inimigos. Logo, o número total de bandidos que são inimigos de um destes n bandidos escolhidos é finito - pois é a soma de n parcelas finitas.. Mas, temos infinitos bandidos, de modo que podemos escolher um que não seja inimigo de nenhum dos n que já escolhemos (e, é claro, que não seja um membro deste conjunto de n que escolhemos). Com isto, obtemos n +1 bandidos distintos tais que, neste conjunto, ninguém vai matar ninguém. Não basta que ele não seja inimigo de nenhum que já foi escolhido, mas tbnenhum dosque já foram escolhidospode ser inimigodele. Pode haver o caso em que todos os infinitos bandidos restantes querem matar alguém do grupo que já foi escolhido. Neste caso o grupo da reunião não poderia ser aumentado. Observe a mensagem que mandei anteriormente. Até mais Vinicius Fortuna A "ponte" de nosso processo indutivo está portanto formada, e mostra que nosso processo de escolha pode prosseguir indefinidamente. OK? Podemos dizer que geramos um seqüência B_n de bandidos tal que, dados quaisquer naturais m e n, com mn, então B_n não quer matar B_m. Estou assumindo, implicitamente, que ninguém quer cometer suicídio. A primeira parte de sua 1a questão é um caso particular da segunda, obtida quando cada bandido tem apenas um inimigo. Espero ter ajudado Artur
RE: [obm-l] violencia
Title: RE: [obm-l] violencia -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Vinicius José Fortuna Sent: Sunday, September 08, 2002 8:12 AM To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Existe uma passagem que, ao meu ver, está falsa. Observe abaixo. - Original Message - From: Artur Costa Steiner To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 11:24 AM Subject: RE: [obm-l] violencia Bom, com relação à primeira questão. Comecemos pela segunda parte e suponhamos, conforme vc disse, que cada bandido tenha um número finito de inimigos. Vou supor que, embora variando com o bandido, este número é conhecido para cada bandido. Escolha um bandido. Isto é possível pois há infinitos (Meu Deus!!) Dado que este bandido tem um número finito de inimigos e existem infinitos bandidos, podemos escolher um bandido que não seja inimigo dele. Logo, a base de nosso processo indutivo está formada. Suponhamos agora que, para algum natural n, tenhamos escolhido n bandidos tais que ninguém seja inimigo de ninguém. Suponhamos. Ora, cada um destes n bandidos tem um número apenas finito de inimigos. Logo, o número total de bandidos que são inimigos de um destes n bandidos escolhidos é finito - pois é a soma de n parcelas finitas.. Mas, temos infinitos bandidos, de modo que podemos escolher um que não seja inimigo de nenhum dos n que já escolhemos (e, é claro, que não seja um membro deste conjunto de n que escolhemos). Com isto, obtemos n +1 bandidos distintos tais que, neste conjunto, ninguém vai matar ninguém. Não basta que ele não seja inimigo de nenhum que já foi escolhido, mas tbnenhum dosque já foram escolhidospode ser inimigodele. Pode haver o caso em que todos os infinitos bandidos restantes querem matar alguém do grupo que já foi escolhido. Neste caso o grupo da reunião não poderia ser aumentado. Observe a mensagem que mandei anteriormente. É, tem razão, neste caso, o processo que citei não vigora. Eu coloquei uma outra mensagem sobre isso. Abraços Artur Até mais Vinicius Fortuna A ponte de nosso processo indutivo está portanto formada, e mostra que nosso processo de escolha pode prosseguir indefinidamente. OK? Podemos dizer que geramos um seqüência B_n de bandidos tal que, dados quaisquer naturais m e n, com mn, então B_n não quer matar B_m. Estou assumindo, implicitamente, que ninguém quer cometer suicídio. A primeira parte de sua 1a questão é um caso particular da segunda, obtida quando cada bandido tem apenas um inimigo. Espero ter ajudado Artur
Re: [obm-l] violencia
É bom notar que essa solução usa o axioma da escolha (de infinitos conjuntos não-vazios, escolhemos um elemento de cada). É essencial o axioma da escolha para resolvê-lo? From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 - Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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] = s _ Join the worlds largest e-mail service with MSN Hotmail. http://www.hotmail.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] violencia
Oi Rogério Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu nem tinha infinitos conjuntos! Apenas conjuntos infinitos. Até mais Vinicius - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 2:17 PM Subject: Re: [obm-l] violencia É bom notar que essa solução usa o axioma da escolha (de infinitos conjuntos não-vazios, escolhemos um elemento de cada). É essencial o axioma da escolha para resolvê-lo? From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 - Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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] violencia
Oi Rogério Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu nem tinha infinitos conjuntos! Apenas conjuntos infinitos. Eu acho que você está certo. O axioma da escolha (a menos que eu esteja com um conceito equivocado) diz que, dada uma coleção infinita de conjuntos disjuntos, podemos formar um conjunto E escolhendo-se precisamente um elemento de cada conjunto da coleção. Isto não foi usado na sua prova. Acho ainda interessante fazer o seguinte comentário: No contra-exemplo que vc deu para a parte 2 da questão, observamos que sendo B_n o n-ésimo bandido, então ele quer matar n-1 outros. Logo, sendo (M_n), a sequencia dos números de bandidos que cada um quer matar, esta sequencia é ilimitada. Se admitirmos que tal sequencia seja limitada, isto é, se considerarmos esta condição adicional, então me parece que sua prova permanece válida. Pois para cada passo de seu processo indutivo, o conjunto dos elementos de C que os elementos de R querem matar continua sendo finito. Acho que neste caso o seu processo acaba sendo equivalente ao que eu havia sugerido. Agora, se a sequencia M_n for ilimitada, etão pode não ser possível achar uma reunião sem sangue, conforme mostra seu contra exemplo. Não estou porém certo se, neste caso, é sempre impossível achar a tal reunião. Um abraço Artur
Re: [obm-l] violencia
- Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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] =
