Re: [obm-l] Tres problemas

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 15.10.04 21:21, Edward Elric at edwardelric666@hotmail.com wrote:

> Parece que minha mensagem antiga não chegou. Entao eu aproveitei e coloquei
> mais um problema:
> O primeiro é de um nivel baixo, o segundo eu até consegui fazer, mas dei uma
> soluçao estupida, deve existir uma soluçao mais rapida, o terceiro eu nao
> consegui fazer.
> 
> 1) As camponesas de certa região têm uma superstição curiosa para
> determinar quando vão casar: A solteira segura em uma das mãos seis folhas
> longas de capim, pelo centro delas, de forma que as pontas fiquem de fora,
> acima e abaixo da mão. Uma amiga sua amarra as seis pontas de cima duas a
> duas, de maneira aleatória, e depois faz o mesmo com as pontas de baixo. Se
> as folhas de capim assim amarradas formarem um único anel, as camponesas
> crêem que a solteira se casará em menos de um ano. Determine a probabilidade
> de o anel ser formado.
> 
Chame as folhas de 1, 2, 3, 4, 5 e 6.

Suponhamos que as pontas de cima sejam amarradas formando os pares:
{1,2}, {3,4} e {5,6}
e que as pontas de baixo sejam amarrados formando os pares X, Y e Z.

Os pares X, Y e Z podem ser escolhidos de Binom(6,2)*Binom(4,2)/3! = 15
maneiras distintas. Estes sao os casos possiveis.

Vamos agora aos casos favoraveis.
Obviamente, 1 e 2 nao podem pertencer ao mesmo par de baixo.
Suponhamos que 1 pertenca a X e 2 pertenca a Y.

A fim de termos um anel, o outro elemento de X deve ser 3, 4, 5 ou 6.
Ou seja, pode ser escolhido de 4 maneiras distintas.

Digamos, pra facilitar, que seja o 3, de forma que X = {1,3}.
A fim de termos um anel, o outro elemento de Y deve ser 5 ou 6 pois se for o
4, teremos um anel parcial formado apenas por 1, 2, 3 e 4, o que nao nos
interessa.
Ou seja, o outro elemento de Y pode ser escolhido de 2 maneiras diferentes.

Uma vez escolhido o outro elemento de Y, os elementos de Z ficam
automaticamente determinados.

Em suma, um anel pode ser formado de 4*2 = 8 maneiras distintas e, portanto,
a probabilidade de termos um anel eh igual a 8/15.


> 2) Existe um inteiro positivo tal que seus fatores primos pertencem ao
> conjunto {2,3,5,7} e
> que termina em 11? Se existir, ache o menor deles. Se não existir, mostre
> porque.
>
Seja N o tal inteiro.

Claramente, 2 e 5 nao podem ser fatores pois nenhum multiplo de 2 ou de 5
termina em 11. Assim, N, caso exista, serah da forma 3^a*7^b.

Os ultimos digitos de 3^k e 7^k sao:
k     3^k   7^k
4m     1     1
4m+1   3     7
4m+2   9     9
4m+3   7     3

Assim, uma inspecao rapida mostra que, se N termina em 1, os expoentes de 3
e 7 devem ser congruentes mod 4, ou seja, devem existir inteiros
nao-negativos r e s tais que N = 3^(4r+k)*7^(4s+k), com k em {0,1,2,3}.

Em outras palavras, N = 81^r*2401^s*21^k

Vamos agora trabalhar mod 100:
N == 81^r*1^s*21^k == 81^r*21^k.

81^0 == 1, 81^1 == 81, 81^2 == 61, 81^3 == 41, 81^4 == 21, 81^5 == 1
Ou seja, 81^k eh periodico de periodo 5.
 
21^0 == 1, 21^1 == 21, 21^2 == 41, 21^3 == 81

Infelizmente, o produto de quaisquer dois elementso (nao necessariamente
distintos) de {1, 21, 41, 61, 81} nao eh congruente a 11 mod 100.

Ou seja, o tal N nao existe.


> 3) Em cada vértice de um quadrado há algumas fichas. Um movimento é
> escolher um vertice, tirar algumas fichas dele, escolher um vizinho e pôr o
> dobro de fichas retiradas no vizinho. Se no inicio ha 1,0,0,0 fichas, é
> possivel termos 1,9,8,9 fichas em algum momento?
> 
Esse problema eh interessante. A solucao deve envolver algum invariante ou,
pelo menos, um monovariante.

[]s,
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
=========================================================================