Re: [obm-l] Mais uma coisinha

["Marcio" <marciocohen@xxxxxxxxxxxxxx>]

Oi Helder. Legal esse problema.. Minha solucao ficou um pouco longa pq eu
fui escrevendo direto no computador.. Espero que esteja certa..

Vamos montar, a partir do final, uma estratégia vencedora para o jogador A.
(1)    A vence na rodada k sse receber um número x1 que seja maior ou igual
a n/9. (n/9 <= x1 < n)
Como A pode forcar B a responder um x1 nessas condicoes?
(2)Para que B fique sem saida, A manda um número y1 tal que 2y1 > n/9, isto
é y1 > n/18..
Alem disso, A deve se preocupar para que B nao venca, logo ele deve mandar
y1 < n/9.
    Ou seja, se o jogador A puder deixar y1 em [n/18,  n/9), então B
fatalmente retorna um número x1 em [n/9,n) e A vence.
(1) Para poder garantir que B recebe esse y1, A deve receber um número x2 em
[n/18.9, n/18)  (e ai A vai escolher um multiplicador de 2 a 9 para garantir
o y1. Se x2 for n/18.9, o multiplicador pode ser 9. Se for n/18, A escolhe
2).
(2) Para que B fique sem saida, A manda um y2 em [n/18.18, n/18.9)
E assim por diante..

Agora vamos reverter o processo.. Para comecar, voce deve descobrir em que
tipo de intervalo o 1 vai cair..
Por exemplo, se existir k tq  n / (9.18^k) <= 1 < n/ (18^k), entao Joao eh
A, e vence o jogo.

Seja k = [(log n)/(log 18)] (função teto), ou seja, 18^k < n <= 18^(k+1).
Entao, 1 pertence ao intervalo I = [ n / (18^(k+1)) , n/(18^k) [.
Mas I = [n/ (18^(k+1)), n/ (9.18^k) [  U  [n/(9.18^k), n/(18^k) [  = X U Y
(nessa ordem).

Agora eh facil reverter o processo acima e concluir que se 1 pertence a X,
então Joao comeca na situacao que acima fora descrita como sendo a de B, ou
seja, Joao eh perdedor. Por outro lado, se 1 pertence a Y, entao Joao eh
vencedor..

Voce pode formalizar isso se quiser, fazendo o caminho logico correto.. Por
exemplo, se 1 esta em X, entao:
Joao pega um numero em [n/ (18^(k+1)), n/ (9.18^k) [  .. Como Joao
multiplica no minimo por 2 e no maximo por 9:
Maria recebe um numero em [n / (9.18^k), n/18^k [. Maria pode entao escolher
um multiplicador dentre 2,3,...,9 para forcar que:
Joao receba um numero em [n / (18^k), n/ (9. 18^(k-1) ) [.
e assim por diante.. Agora, o expoente do 18 vai diminuindo. Quando esse
expoente chegar em 0:
Maria recebe um numero em [n/9, n[, e ganha o jogo multiplicando esse nr por
9.

O outro caso (em que 1 esta em Y) eh analogo.

----- Original Message -----
From: "Helder Suzuki" <heldersuzuki@yahoo.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, April 22, 2003 7:14 PM
Subject: [obm-l] Mais uma coisinha


> Olá!
>
> Bom, primeiro eu agradeço a todos que responderam ao
> "4 coisinhas", embora o problema do jogo não foi lá
> bem muito resolvido e eu não sei aonde achar a tal
> revista hehehe :P
>
> 1)
> João e Maria brincam de multiplicar.
> Antes de começar o jogo, eles escolhem um natural n>1.
>
> João começa com o número 1 e multiplica-o por um
> natural do intervalo [2, 9], Maria pega o resultado
> faz o mesmo, e assim sucessivamente.
>
> Ganha o jogo o primeiro que conseguir fazer o
> resultado >= n.
>
> Se João e Maria jogam perfeitamente, e João sempre
> começa o jogo, para quais valores de n João ganha? e
> Maria?

=========================================================================
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
=========================================================================