[obm-l] Re: [obm-l] Re: [obm-l] Número de sextas-feiras 13
Uma pergunta divertida ligeiramente relacionada: escolha um dia 13 aleatoriamente (todos os dias 13 de todos os meses de todos os anos com a mesma probabilidade; suponha que o numero de anos eh BEM grande, mas todos no calendario gregoriano para evitar complicacoes). Qual a probabilidade de este dia ser uma 6a feira? Se eu me lembro direito, surpreendentemente a resposta NAO EH 1/7 -- nem pegando o "estado estacionario" quando o numero de anos vai para infinito! Mas deixo o raciocinio exato como exercicio para o leitor... (Traducao: to c/ preg.) Abraco, Ralph 2012/1/13 Pedro Nascimento > Vendo as classes de congruencia mod 7 temos: > 0 > (0+31)=3 mod 7 > (3+29)=4 mod 7 > (4+31)=0 mod 7 > (0+30)=2 mod 7 > (2+31)=5 mod 7 > (5+30)=0 mod 7 > (0+31)=3 mod 7 > (3+31)=6 mod 7 > (6+30)=1 mod 7 > (1+31)=4 mod 7 > (4+30)=6 mod 7 > > a classe que aparece mais eh zero, podemos atribuir a ela uma sexta-feira > e temos assim que o maximo sao 3 meses mesmo. > > Em 13 de janeiro de 2012 09:32, Mauricio de Araujo < > mauricio.de.ara...@gmail.com> escreveu: > >> Este ano de 2012 possuirá 3 sextas-feiras 13: em janeiro, abril e julho. >> >> Pergunta-se: Considerando anos bissextos, qual o número máximo de meses >> com sexta-feira 13 pode haver em um mesmo ano? 2012 possuirá 3 meses. >> >> -- >> -- >> Abraços >> oɾnɐɹɐ ǝp oıɔıɹnɐɯ >> De Luto pelo Brasil até, no mínimo, 2014. >> >> >> >> "*NÃO À OBRIGATORIEDADE DO VOTO!*" >> >> >> >
[obm-l] RE: [obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Como eu ja disse, achei 23: 1. Teste ABC, se nao funcionar sabemos que pelo menos uma entre A, B e C nao funciona. 2. Teste as combinacoes entre DEFGH (DEF,DEG,DEH,DFG,DFH,DGH,EFG,EFH,EGH,FGH), se nenhuma funcionar temos que tres entre DEFGH nao funcionam, portando duas entre ABC e duas entre DEFGH funcionam. 3. Sabemos que AB, AC ou BC sao formadas por duas que funcionam e que pelo menos uma entre D,E,F,G funciona, bastam entao mais 12 testes totalizando 23. PS:Ainda tem mais outros dois algoritmos um pouco mais complicados que eu fiz e que tambem chegam em 23. Quem da menos?
[obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Pensei assim:
Separando a dupla AB temos 3 possibilidades:
1)A e B funcionam
2)Somente um dos dois funciona
3)Nenhum dos dois funcionam
Agora veremos com quantos testes conseguimos verificar cada hipótese
1) Supondo hipótese 1 verdadeira, existem duas que funcionam entre C D E F G H,
logo 5 testes bastam para essa hipótese
AB( C;D;E;F;G ) por exemplo
2) Supondo hipótese 2 verdadeira existem 3 que funcionam entre C D E F G H,
Assim podemos separar em duplas (CD;EF;GH) e dizer que?
2.1)ou exisste uma dupla com duas funcionando, e consequentemente uma sem
nenhum e uma com um.
2.2)ou cada dupla tem apenas uma funcionando.
2.1) Para testar 2.1) 6 testes bastam A(CD;EF;GH) e B(CD;EF;GH)
2.2) Para testar 2.2) 8 testes bastam, permutando duas duplas, por exemplo
A(CE;CF;DE;DF) e B(CE;CF;DE;DF)
3) Supondo a hipótese 3 verdadeira, sabemos que existem 4 que funcionam entre C
D E F G H, e de certa forma o problema é o mesmo porém com 6 pilhas ao invés de
8, assim sabemos que seguindo esse método teremos menos de 2*(5+6+8) = 38 casos
Para esse teste supomos:
3.1) C e D funcionam
3.2) C ou D funciona
3.3) C e D não funcionam
3.1) Supondo 3.1 verdadeiro precisamos de 3 testes CD(E;F;G), pois em E F G H
tem pelo menos 2 que funcionam
3.2) Supondo 3.2 verdadeiro precisamos de 4 testes C(EF;GH) e D(EF;GH), pois
em EF GH tem pelo menos uma dupla com duas que funcionam.
3.3) Tecnicamente não temos que testar mais nada, pois já sabemos que qualquer
combinação de E F G H irá funcionar, mas se quiser trocar de canal, mais um
teste é necessário, Assim 1+4+3+8+6+5 = 27
Obviamente não vejo uma maneira clara de provar que isso é o mínimo, logo, quem
dá menos?
> Date: Thu, 12 Jan 2012 15:36:44 +0100
> Subject: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de
> tentativas
> From: bernardo...@gmail.com
> To: obm-l@mat.puc-rio.br
>
> 2012/1/12 Bernardo Freitas Paulo da Costa :
> > 2012/1/12 Ralph Teixeira :
> >> Nao precisa testar 53 trincas nao! Rapidinho, arrumo um algoritmo com
> >> 38 testes...
> >>
> >> Sejam ABCDEFGH as 8 pilhas, seja X o conjunto das 4 que funcionam. Ha
> >> C(8,4)=70 possibilidades para X.
> >>
> >> Agora, voce testa ABC; se NAO funcionar, isto jah elimina 5
> >> possibilidades para X (a saber, ABCD, ABCE, ABCF, ABCG, ABCH).
> >> Teste CDE. Se nao funcionar, eliminamos ACDE, BCDE, CDEF, CDEG e CDEH.
> >> EFG elimina mais 5; GHA elimina mais 5.
> >> Tente agora ADF, CFH, EHB e GBD. Se nada disso funcionar, jah
> >> eliminamos no total 40 possibilidades -- ateh aqui, todas disjuntas!
> >> Explicitamente, sobram apenas as seguintes 30 possibilidades para X:
> >> ABDE ABDH ABEF ABEG ABFG ABFH ACDG ACDH ACEF ACEG ACEH ACFG ADEG ADEH AEFH
> >> BCDF BCDH BCEF BCEG BCFG BCGH BDEF BDFH BFGH CDFG CDGH CEGH DEFH DEGH DFGH
> >>
> >> Mesmo que voce agora escolha uma trinca de cada um desses 30
> >> conjuntos, seria um total de 8+30=38 testes. Mas ainda dah para
> >> diminuir bastante, jah que varias trincas aparecem em varias dessas
> >> quadras!
> >>
> >> Quem dah menos? :)
> > 32
> >
> >> Abraco,
> >> Ralph
> >
> > Eu acho que é outra idéia (que eu acho também dá pra ser "escovada"),
> > então aí vai:
> >
> > O princípio é "manter a simetria" (circular) das pilhas.
> > Teste ABC, BCD, CDE, ... GHA, HAB. (8 testes).
> > Se nada disso der certo, não tem 3 pilhas boas em série, que eu noto
> > "bbb". Portanto, bb => a próxima é r.
> >
> > Teste em seguida ABD, BCE, ... GHB, HAC.
> > Se nada disso der certo, não tem também "bbrb", portanto "bb => rr".
> >
> > Para a "simetria", teste ACD, BDE, ..., GAB, HBC.
> > Isso impede "brbb", portanto "brb => r"
> >
> > Para fechar a simetria, teste ABE, BCF, ..., GHC, HAD.
> > Isso impede "bbrrb", logo "bb => rrr".
> >
> > Agora, se houvesse um "bb" em algum momento, teríamos logo depois um
> > rrr. A situação é a seguinte:
> > bb rrr ???
> >
> > Sabemos que temos que colocar 2 bons, nos ??? que sobram. Só que o
> > último também não pode ser um b (afinal de contas, não há 3 bons
> > consecutivos). Portanto, é um "bb rrr bb r", que também é impossível
> > visto que temos um bb r b cíclico.
> >
> > Assim, não há "bb", e portanto podemos ficar com as 6 primeiras que
> > haverá 3 bons e 3 ruins. Há 20 = C(6,3) combinações possíveis para as
> > 6 pilhas. Mas acontece que a gente já testou
> > ABC, BCD, CDE, DEF (4)
> > ABD, BCE, CDF (3)
> > ACD, BDE, CEF (3)
> > ABE, BCF (2)
> > 12 possibilidades que não deram certo. Restam apenas 8, uma delas com
> > certeza vai dar.
> >
> > O que dá 8+8+8+8 ("simétricos") + 8 (restos dos 6 que a gente não testou).
> Opa, ninguém viu o erro, mas 5*8 = 40. Que é pior do que a solução do Ralph.
>
> MAAS, eu acho que dah pra corrigir e ainda ficar um pouco melhor
> do que os 38.
>
> Assim: quase no final, a gente jah excluiu bbb, bbrb, brbb, portanto
> se houver um "bb", tem que ser seguido (e precedido) de dois ruins. O
> que quer dizer que a unica configuraçao possivel com um "bb" é
>
[obm-l] FW: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
From: eusoupedroso...@hotmail.com
To: obm-l@mat.puc-rio.br
Subject: RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de
tentativas
Date: Fri, 13 Jan 2012 21:41:41 +
Pensei assim:
Separando a dupla AB temos 3 possibilidades:
1)A e B funcionam
2)Somente um dos dois funciona
3)Nenhum dos dois funcionam
Agora veremos com quantos testes conseguimos verificar cada hipótese
1) Supondo hipótese 1 verdadeira, existem duas que funcionam entre C D E F G H,
logo 5 testes bastam para essa hipótese
AB( C;D;E;F;G ) por exemplo
2) Supondo hipótese 2 verdadeira existem 3 que funcionam entre C D E F G H,
Assim podemos separar em duplas (CD;EF;GH) e dizer que?
2.1)ou exisste uma dupla com duas funcionando, e consequentemente uma sem
nenhum e uma com um.
2.2)ou cada dupla tem apenas uma funcionando.
2.1) Para testar 2.1) 6 testes bastam A(CD;EF;GH) e B(CD;EF;GH)
2.2) Para testar 2.2) 8 testes bastam, permutando duas duplas, por exemplo
A(CE;CF;DE;DF) e B(CE;CF;DE;DF)
3) Supondo a hipótese 3 verdadeira, sabemos que existem 4 que funcionam entre C
D E F G H, e de certa forma o problema é o mesmo porém com 6 pilhas ao invés de
8, assim sabemos que seguindo esse método teremos menos de 2*(5+6+8) = 38 casos
Para esse teste supomos:
3.1) C e D funcionam
3.2) C ou D funciona
3.3) C e D não funcionam
3.1) Supondo 3.1 verdadeiro precisamos de 3 testes CD(E;F;G), pois em E F G H
tem pelo menos 2 que funcionam
3.2) Supondo 3.2 verdadeiro precisamos de 4 testes C(EF;GH) e D(EF;GH), pois
em EF GH tem pelo menos uma dupla com duas que funcionam.
3.3) Tecnicamente não temos que testar mais nada, pois já sabemos que qualquer
combinação de E F G H irá funcionar, mas se quiser trocar de canal, mais um
teste é necessário, Assim 1+4+3+8+6+5 = 27
Obviamente não vejo uma maneira clara de provar que isso é o mínimo, logo, quem
dá menos?
> Date: Thu, 12 Jan 2012 15:36:44 +0100
> Subject: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de
> tentativas
> From: bernardo...@gmail.com
> To: obm-l@mat.puc-rio.br
>
> 2012/1/12 Bernardo Freitas Paulo da Costa :
> > 2012/1/12 Ralph Teixeira :
> >> Nao precisa testar 53 trincas nao! Rapidinho, arrumo um algoritmo com
> >> 38 testes...
> >>
> >> Sejam ABCDEFGH as 8 pilhas, seja X o conjunto das 4 que funcionam. Ha
> >> C(8,4)=70 possibilidades para X.
> >>
> >> Agora, voce testa ABC; se NAO funcionar, isto jah elimina 5
> >> possibilidades para X (a saber, ABCD, ABCE, ABCF, ABCG, ABCH).
> >> Teste CDE. Se nao funcionar, eliminamos ACDE, BCDE, CDEF, CDEG e CDEH.
> >> EFG elimina mais 5; GHA elimina mais 5.
> >> Tente agora ADF, CFH, EHB e GBD. Se nada disso funcionar, jah
> >> eliminamos no total 40 possibilidades -- ateh aqui, todas disjuntas!
> >> Explicitamente, sobram apenas as seguintes 30 possibilidades para X:
> >> ABDE ABDH ABEF ABEG ABFG ABFH ACDG ACDH ACEF ACEG ACEH ACFG ADEG ADEH AEFH
> >> BCDF BCDH BCEF BCEG BCFG BCGH BDEF BDFH BFGH CDFG CDGH CEGH DEFH DEGH DFGH
> >>
> >> Mesmo que voce agora escolha uma trinca de cada um desses 30
> >> conjuntos, seria um total de 8+30=38 testes. Mas ainda dah para
> >> diminuir bastante, jah que varias trincas aparecem em varias dessas
> >> quadras!
> >>
> >> Quem dah menos? :)
> > 32
> >
> >> Abraco,
> >> Ralph
> >
> > Eu acho que é outra idéia (que eu acho também dá pra ser "escovada"),
> > então aí vai:
> >
> > O princípio é "manter a simetria" (circular) das pilhas.
> > Teste ABC, BCD, CDE, ... GHA, HAB. (8 testes).
> > Se nada disso der certo, não tem 3 pilhas boas em série, que eu noto
> > "bbb". Portanto, bb => a próxima é r.
> >
> > Teste em seguida ABD, BCE, ... GHB, HAC.
> > Se nada disso der certo, não tem também "bbrb", portanto "bb => rr".
> >
> > Para a "simetria", teste ACD, BDE, ..., GAB, HBC.
> > Isso impede "brbb", portanto "brb => r"
> >
> > Para fechar a simetria, teste ABE, BCF, ..., GHC, HAD.
> > Isso impede "bbrrb", logo "bb => rrr".
> >
> > Agora, se houvesse um "bb" em algum momento, teríamos logo depois um
> > rrr. A situação é a seguinte:
> > bb rrr ???
> >
> > Sabemos que temos que colocar 2 bons, nos ??? que sobram. Só que o
> > último também não pode ser um b (afinal de contas, não há 3 bons
> > consecutivos). Portanto, é um "bb rrr bb r", que também é impossível
> > visto que temos um bb r b cíclico.
> >
> > Assim, não há "bb", e portanto podemos ficar com as 6 primeiras que
> > haverá 3 bons e 3 ruins. Há 20 = C(6,3) combinações possíveis para as
> > 6 pilhas. Mas acontece que a gente já testou
> > ABC, BCD, CDE, DEF (4)
> > ABD, BCE, CDF (3)
> > ACD, BDE, CEF (3)
> > ABE, BCF (2)
> > 12 possibilidades que não deram certo. Restam apenas 8, uma delas com
> > certeza vai dar.
> >
> > O que dá 8+8+8+8 ("simétricos") + 8 (restos dos 6 que a gente não testou).
> Opa, ninguém viu o erro, mas 5*8 = 40. Que é pior do que a solução do Ralph.
>
> MAAS, eu acho que dah pra corrigir e ainda ficar um pouco melhor
> do que os 38.
>
> Assim:
[obm-l] RE: [obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Acho que meus metodos com 23 testes ainda estao ganhando, mas estou interessado em saber qual seria o valor minimo.
[obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Arrumei um jeito com 27 tentativas mas não to conseguindo enviar e-mail para o
grupo, se este teste passar envio a solução
> Date: Thu, 12 Jan 2012 15:36:44 +0100
> Subject: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de
> tentativas
> From: bernardo...@gmail.com
> To: obm-l@mat.puc-rio.br
>
> 2012/1/12 Bernardo Freitas Paulo da Costa :
> > 2012/1/12 Ralph Teixeira :
> >> Nao precisa testar 53 trincas nao! Rapidinho, arrumo um algoritmo com
> >> 38 testes...
> >>
> >> Sejam ABCDEFGH as 8 pilhas, seja X o conjunto das 4 que funcionam. Ha
> >> C(8,4)=70 possibilidades para X.
> >>
> >> Agora, voce testa ABC; se NAO funcionar, isto jah elimina 5
> >> possibilidades para X (a saber, ABCD, ABCE, ABCF, ABCG, ABCH).
> >> Teste CDE. Se nao funcionar, eliminamos ACDE, BCDE, CDEF, CDEG e CDEH.
> >> EFG elimina mais 5; GHA elimina mais 5.
> >> Tente agora ADF, CFH, EHB e GBD. Se nada disso funcionar, jah
> >> eliminamos no total 40 possibilidades -- ateh aqui, todas disjuntas!
> >> Explicitamente, sobram apenas as seguintes 30 possibilidades para X:
> >> ABDE ABDH ABEF ABEG ABFG ABFH ACDG ACDH ACEF ACEG ACEH ACFG ADEG ADEH AEFH
> >> BCDF BCDH BCEF BCEG BCFG BCGH BDEF BDFH BFGH CDFG CDGH CEGH DEFH DEGH DFGH
> >>
> >> Mesmo que voce agora escolha uma trinca de cada um desses 30
> >> conjuntos, seria um total de 8+30=38 testes. Mas ainda dah para
> >> diminuir bastante, jah que varias trincas aparecem em varias dessas
> >> quadras!
> >>
> >> Quem dah menos? :)
> > 32
> >
> >> Abraco,
> >> Ralph
> >
> > Eu acho que é outra idéia (que eu acho também dá pra ser "escovada"),
> > então aí vai:
> >
> > O princípio é "manter a simetria" (circular) das pilhas.
> > Teste ABC, BCD, CDE, ... GHA, HAB. (8 testes).
> > Se nada disso der certo, não tem 3 pilhas boas em série, que eu noto
> > "bbb". Portanto, bb => a próxima é r.
> >
> > Teste em seguida ABD, BCE, ... GHB, HAC.
> > Se nada disso der certo, não tem também "bbrb", portanto "bb => rr".
> >
> > Para a "simetria", teste ACD, BDE, ..., GAB, HBC.
> > Isso impede "brbb", portanto "brb => r"
> >
> > Para fechar a simetria, teste ABE, BCF, ..., GHC, HAD.
> > Isso impede "bbrrb", logo "bb => rrr".
> >
> > Agora, se houvesse um "bb" em algum momento, teríamos logo depois um
> > rrr. A situação é a seguinte:
> > bb rrr ???
> >
> > Sabemos que temos que colocar 2 bons, nos ??? que sobram. Só que o
> > último também não pode ser um b (afinal de contas, não há 3 bons
> > consecutivos). Portanto, é um "bb rrr bb r", que também é impossível
> > visto que temos um bb r b cíclico.
> >
> > Assim, não há "bb", e portanto podemos ficar com as 6 primeiras que
> > haverá 3 bons e 3 ruins. Há 20 = C(6,3) combinações possíveis para as
> > 6 pilhas. Mas acontece que a gente já testou
> > ABC, BCD, CDE, DEF (4)
> > ABD, BCE, CDF (3)
> > ACD, BDE, CEF (3)
> > ABE, BCF (2)
> > 12 possibilidades que não deram certo. Restam apenas 8, uma delas com
> > certeza vai dar.
> >
> > O que dá 8+8+8+8 ("simétricos") + 8 (restos dos 6 que a gente não testou).
> Opa, ninguém viu o erro, mas 5*8 = 40. Que é pior do que a solução do Ralph.
>
> MAAS, eu acho que dah pra corrigir e ainda ficar um pouco melhor
> do que os 38.
>
> Assim: quase no final, a gente jah excluiu bbb, bbrb, brbb, portanto
> se houver um "bb", tem que ser seguido (e precedido) de dois ruins. O
> que quer dizer que a unica configuraçao possivel com um "bb" é
> bbrrbbrr (+ permutaçao circular, sempre).
> Agora, a gente para com a simetria. Basta testar ABE, BCF, CDG (que é
> o aeroporto de Paris) e DEH. Brincadeiras à parte, se nenhuma dessas 4
> acender, é que não temos bbrrbbrr (que é simétrica na metade, por isso
> basta testar 4 das oito configuraçoes). Agora, escolha ABCDEF e teste
> os 8 que sobraram. O mais legal é que não tanto faz pegar ABCDEF ou
> qualquer permutação circular disso, porque do ultimo teste, que é
> "assimétrico", soh temos 2 testes para alguns grupos, mas nao todos
> (por exemplo, DEFGHA soh tem 1 teste). Corrigindo a minha aritmética,
> dah 36 testes
>
> > A minha solução é meio "força bruta" comparada à do Ralph (que deve
> > ser mais fácil de "optimizar", mas sei lá. De repente eu dei sorte com
> > o método.
> >
> > Abraços,
> > --
> > Bernardo Freitas Paulo da Costa
>
>
>
> --
> Bernardo Freitas Paulo da Costa
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
[obm-l] Re: [obm-l] Número de sextas-feiras 13
Vendo as classes de congruencia mod 7 temos: 0 (0+31)=3 mod 7 (3+29)=4 mod 7 (4+31)=0 mod 7 (0+30)=2 mod 7 (2+31)=5 mod 7 (5+30)=0 mod 7 (0+31)=3 mod 7 (3+31)=6 mod 7 (6+30)=1 mod 7 (1+31)=4 mod 7 (4+30)=6 mod 7 a classe que aparece mais eh zero, podemos atribuir a ela uma sexta-feira e temos assim que o maximo sao 3 meses mesmo. Em 13 de janeiro de 2012 09:32, Mauricio de Araujo < mauricio.de.ara...@gmail.com> escreveu: > Este ano de 2012 possuirá 3 sextas-feiras 13: em janeiro, abril e julho. > > Pergunta-se: Considerando anos bissextos, qual o número máximo de meses > com sexta-feira 13 pode haver em um mesmo ano? 2012 possuirá 3 meses. > > -- > -- > Abraços > oɾnɐɹɐ ǝp oıɔıɹnɐɯ > De Luto pelo Brasil até, no mínimo, 2014. > > > > "*NÃO À OBRIGATORIEDADE DO VOTO!*" > > >
[obm-l] Número de sextas-feiras 13
Este ano de 2012 possuirá 3 sextas-feiras 13: em janeiro, abril e julho. Pergunta-se: Considerando anos bissextos, qual o número máximo de meses com sexta-feira 13 pode haver em um mesmo ano? 2012 possuirá 3 meses. -- -- Abraços oɾnɐɹɐ ǝp oıɔıɹnɐɯ De Luto pelo Brasil até, no mínimo, 2014. "*NÃO À OBRIGATORIEDADE DO VOTO!*"
