[obm-l] PROBLEMA DA OBM
EU ACHO QUE ESTÁ FALTANDO DETALHES E INFORMAÇÕES NESTE PROBLEMA, EU NÃO SEI POIS COMO ESTA NUMA LISTA AVULSA PODE TER SIDO MAU DIGITADO. AÍ VAI: (OBM-)EM UM JOGO DE DUAS PESSOAS OS JOGADORES TIRAM, ALTERNADAMENTE, 1, 2, 3, 4 OU 5 PALITOS DE UMA PILHA QUE INICIALMENTE TEM 1000 PALITOS. GANHA O JOGADOR QUE TIRAR O ÚLTIMO PALITO DA PILHA. QUANTOS PALITOS O JOGADOR QUE COMEÇA DEVE TIRAR NA SUA JOGADA INICIAL DE MODO A ASSEGURAR A SUA VITÓRIA? A) 1 B) 2 C) 3 D) 4 E) 5 EU ACHEI 4, LETRA D. PORÉM EU ACHEI A QUESTÃO PROBLEMÁTICA, POIS ELE NÃO ESPECIFICA SE TEM QUE SER NESTA ORDEM, SE PODE TIRAR NÚMEROS REPETIDOS OU SE NO FINAL SE ALGUM DOS DOIS TIRAR UM NÚMERO DE PALITOS MAIOR DO QUE O NECESSÁRIO ELE VENCE TAMBÉM. VALEU! AGRADEÇO! _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
[obm-l] Problema da OBM - 2001
Alo colegas de lista
Essa mensagem é sobre o 6º problema do nível 3 da
3ª fase da OBM do ano passado. A resolução de Humberto Silva Navaes pode ser
vista na Eureka! nº13, 2002.
Na solução da segunda parte esta escrita
abaixo:
-Notação: S(x) A: Somatória dos termos do tipo A
para todos os valores de x pertencentes ao evento.
Sabemos que dada uma configuração inicial, independente das
escolhas dos movimentos sempre chegamos a uma configuração onde é impossível
mover (configuração parada). Suponha por absurdo que a partir de uma
configuração inicial se chegue a duas configurações paradas distintas A e
B.
Seja k' a posição da pedra mais à direita das
configurações A e B e k = k' + 2.
Considere o seguinte invariante: (não varia a cada movimento)
I= S(x) F (k-pos(x)), onde Fn é o
n-ésimo número de Fibonacci.
Lembramos que F1 = 1, F2 = 1 e
Fn + 2 = Fn + 1 + Fn, para
todo n ³ 1)
Sabemos que Ia=Ib ,pois I é invariante, isto é,
permanece o mesmo depois de cada movimento.
De fato, Fk – (p – 1) =
Fk – p + 1 = Fk – p + Fk –
p – 1 = Fk – p + Fk – (p +
1), donde I não muda após um movimento do tipo A, e F
(k-(p-1)) + F (k-(p+2)) = F (k-p) + F (k-p-1) + F (k-p-2)= 2 F (k-p), donde
I não muda após um movimento do tipo B.
Algoritmo:
Seja x a pedra mais à esquerda de A e y a pedra mais
à esquerda de B.
Devemos ter pos(x) = pos(y), pois se fosse
pos(x) ¹ pos(y) (assumimos sem perda de
generalidade que pos(x) > pos(y)), teríamos:
Ia=S(t \in A) F (k-pos(t)), menor ou igual à F (k-pos(x))
+ F (k-pos(x)-2) + F (k-pos(x)-4) + ... + F (2)
se k-pos(x) for par e
Ia= S(t \in A) F (k-pos(x)), menor ou igual à F
(k-pos(x)) + F (k-pos(x)-2) + ... + F (3) caso contrário:
Mas F (2) + ... + F (2k)=F(2k+1)-1, menor que F
(2k+1) e F(3) + ... + F (2k+1)= F (2k+2)-1, menor que
F (2k+2). (como se prova facilmente por indução).
logo Ia é menor ou igual que F (k-pos(x)+1)-1,
que é menor que F (k-pos(x)+1), menor ou igual à
F(k-pos(y),menor ou igual que Ib, um
absurdo!
Seja A: = A – {x} e B: = {y}.
Vá para o 1.
Pronto! Demonstramos que A e B são a mesma
configuração, o que é um absurdo! A configuração final independe da escolha dos
movimentos.
Queria uma explicação mais detalhada de cada passo
e se isso implica que as duas configurações são iguais por quê se pode deduzir
um invariante.
André T.
[obm-l] Problema da OBM 2003
Há N cidades em Tumbólia. Cada duas cidades desse país são ligadas por uma rodovia ou uma ferrovia, não existin do nenhum par de cidades ligadas por ambos os meios. Um turista deseja viajar por toda a Tumbólia, visitando cada cidade exatamente uma vez, e retornar a cidade onde ele começou sua jornada. Prove que é possível escolher a ordem na qual as cidades serão visitadas de modo que o turista mude o meio de transporte no máximo uma vez. Obrigado
Re: [obm-l] PROBLEMA DA OBM
Caro Rafael Alfinito Ferreira <[EMAIL PROTECTED]>: De fato, tirando 4 no primeiro lance, o primeiro jogador deixa um multiplo de 6 (996). A partir de ai, basta, a cada lance em que o adversario tirar n, responder titarndo 6-n. Angelo Barone Netto <[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 =
Re: [obm-l] PROBLEMA DA OBM
Eu acho que voce esta enrolando demais... Bem, a questao nao deixa claro se e para fazer variacoes do enunciado. Se ha uma regra explicita como "nao se pode retirar o mesmo numero de palitos que o adversario ja tirou na jogada imediatamente anterior", ela deve ser seguida; se tal regra nao aparecer, nao ha o que considerar. Como se diz na advocacia, "o que as leis nao proibem, nada mais proibe". Alias, imagine o tamanho do "enunciado mais claro possivel": EM UM JOGO DE DUAS PESSOAS OS JOGADORES TIRAM, ALTERNADAMENTE, 1, 2, 3, 4 OU 5 PALITOS (em qualquer ordem possivel, ao desejo de qualquer jogador, apenas lembraqndo que nao se pode tirar mais palitos do que a pilha atualmente contem) DE UMA PILHA QUE INICIALMENTE TEM (exatamente) 1000 PALITOS (nbem mais nem menos. A pilha tambem na o recebe mais nenhum palito a partir do inicio do jogo). (O primeiro jogador e escolhido por algum acordo entre os participantes.) GANHA O JOGADOR QUE TIRAR O ÚLTIMO PALITO DA PILHA (ou melhor, os ultimos palitos da pilha, uu quem deixar a pilha vazia ou tambem o que impedir o outro jogador de jogar a partir das regras ja estabelecidas). QUANTOS PALITOS O JOGADOR QUE COMEÇA DEVE TIRAR NA SUA JOGADA INICIAL DE MODO A ASSEGURAR A SUA VITÓRIA(nao importando quao bem ou quao inteligentemente o adversario jogue, supondo que os dois jogadores sao inteligentes e honestos e jogarao ate o fim)? Pergunta: como e possivel tirar 100 palitos de 1? E possivel ficar devendo palitos? Rafael Alfinito Ferreira <[EMAIL PROTECTED]> wrote: EU ACHO QUE ESTÁ FALTANDO DETALHES E INFORMAÇÕES NESTE PROBLEMA, EU NÃO SEI POIS COMO ESTA NUMA LISTA AVULSA PODE TER SIDO MAU DIGITADO.AÍ VAI:(OBM-)EM UM JOGO DE DUAS PESSOAS OS JOGADORES TIRAM, ALTERNADAMENTE, 1, 2, 3, 4 OU 5 PALITOS DE UMA PILHA QUE INICIALMENTE TEM 1000 PALITOS. GANHA O JOGADOR QUE TIRAR O ÚLTIMO PALITO DA PILHA. QUANTOS PALITOS O JOGADOR QUE COMEÇA DEVE TIRAR NA SUA JOGADA INICIAL DE MODO A ASSEGURAR A SUA VITÓRIA?A) 1 B) 2 C) 3 D) 4 E) 5EU ACHEI 4, LETRA D.PORÉM EU ACHEI A QUESTÃO PROBLEMÁTICA, POIS ELE NÃO ESPECIFICA SE TEM QUE SER NESTA ORDEM, SE PODE TIRAR NÚMEROS REPETIDOS OU SE NO FINAL SE ALGUM DOS DOIS TIRAR UM NÚMERO DE PALITOS MAIOR DO QUE O NECESSÁRIO ELE VENCE TAMBÉM.VALEU! AGRADEÇO!_Chegou o que faltava: MSN! Acesso Grátis. Instale Já! http://www.msn.com.br/discador=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=__Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/
[obm-l] Problema da OBM 2017
Pessoal, gostaria de uma ajuda no item c dessa questão. Os dois primeiros itens são tranquilos. *Na Terra dos Impas, somente os algarismos ímpares são utilizados para contar e escrever números. Assim, em vez dos números 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, . . . os Impas tem os números correspondentes 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33, . . . (note que os números dos Impas têm somente algarismos ímpares). Por exemplo, se uma criança tem 11 anos, os Impas diriam que ela tem 31 anos. * *a) Como os Impas escrevem o nosso numero 20? * *b) Numa escola desse lugar, a professora escreveu no quadro-negro a continha de multiplicar abaixo. Se você fosse um aluno Impa, o que escreveria como resultado?* *13 × 5* *c) Escreva, na linguagem dos Impas, o numero que na nossa representação ao decimal é escrito como 2017.* Obrigado! -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Problema da OBM 2017
Boa tarde, Vanderlei Bom, o que pensei nessa letra é o seguinte: Temos que encontrar o elemento que ocupa a posição 2017 (no conjunto crescentemente ordenado dos números que podemos escrever na terra dos Impas). Para isso, podemos pensar qual o número mínimo de algarismos que esse número procurado deve ter. Usando combinatória percebemos que: *Com 1 algarismo -> 5 números *Com 2 algarismos -> 25 números *Com 3 algarismos -> 125 números *Com 4 algarismos -> 625 números *Com 5 algarismos -> 3125 números Logo, o número procurado terá 5 algarismos (concorda?). Assim, basta encontrarmos esses algarismos. O último número que conseguiremos escrever com 5 algarismos é o 9 e o primeiro número é o 1. Assim, vamos analisar qual número ocupa a posição 2017. Bom, com até 4 algarismos, ja conseguimos escrever 780 números (certo?), então estamos procurando o número de posição 1237 depois do 1. Se o primeiro digito for 1, teremos 625 possibilidades. Vamos então para o segundo digito (3), teremos mais 625 possibilidades. Mas atenção (625 + 625 > 1237), então concluímos que o nosso número começa com 3. Agora se o segundo digito for 1, teremos 125 possibilidades, assim como se for 3, 5, 7 e 9. Novamente, devemos parar antes que a soma de todas as possibilidades seja maior que 1237. Logo, teremos que o segundo digito é 9. Trabalhando de modo análogo para o terceiro digito, concluiremos que o mesmo é 7 e o quarto digito é 5. Finalmente estaremos com o número 3975_ e falta um número. O número 39751 ocupa a posição 2016 portanto, o número 39753 ocupa a posição 2017 no conjunto analisado. Veja se é um raciocínio coerente. Abraços Kevin Kühl On 10 May 2018 16:44 -0300, Vanderlei Nemitz , wrote: > Pessoal, gostaria de uma ajuda no item c dessa questão. Os dois primeiros > itens são tranquilos. > > Na Terra dos Impas, somente os algarismos ímpares são utilizados para contar > e escrever números. Assim, em vez dos números 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, > 11, 12, . . . os Impas tem os números correspondentes 1, 3, 5, 7, 9, 11, 13, > 15, 17, 19, 31, 33, . . . (note que os números dos Impas têm somente > algarismos ímpares). Por exemplo, se uma criança tem 11 anos, os Impas diriam > que ela tem 31 anos. > a) Como os Impas escrevem o nosso numero 20? > b) Numa escola desse lugar, a professora escreveu no quadro-negro a continha > de multiplicar abaixo. Se você fosse um aluno Impa, o que escreveria como > resultado? > 13 × 5 > c) Escreva, na linguagem dos Impas, o numero que na nossa representação ao > decimal é escrito como 2017. > > Obrigado! > > -- > Esta mensagem foi verificada pelo sistema de antiv�rus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
