Re: [obm-l] IMO

["amurpe" <amurpe@xxxxxxxxxx>]

> Acho que nao tem muito a ver voce ficar inundando a lis
ta com problemas resolvidos.. A maioria das pessoas aqui 
conhece o site do Kalva, e lá há diversos problemas resol
vidos, de diversos níveis de dificuldade.. 
>   ----- Original Message ----- 
>   From: Johann Peter Gustav Lejeune Dirichlet 
>   To: obm-l@mat.puc-rio.br 
>   Sent: Thursday, February 06, 2003 3:26 PM
>   Subject: [obm-l] IMO
> 
> 
>   Problem 3
> 
>   The set of all positive integers is the union of two 
disjoint subsets {f(1), f(2), f(3), ... }, {g(1), g(2), g
(3), ... }, where f(1) < f(2) < f(3) < ..., and g(1) < g
(2) < g(3) < ... , and g(n) = f(f
(n)) + 1 for n = 1, 2, 3, ... . Determine f(240). 
> 
> 
>   Solution
> Alô pessoal , gosraia de saber o site do KAlva .por 
favor me enviem .um abraço.Amurpe
> 
>   Let F = {f(1), f(2), f(3), ... }, G = {g(1), g(2), g
(3), ... }, Nn = {1, 2, 3, ... , n}. f(1) >= 1, so f(f
(1)) >= 1 and hence g
(1) >= 2. So 1 is not in G, and hence must be in F. It mu
st be the smallest element of F and so f(1) = 1. Hence g
(1) = 2. We can never have two successive integers n and 
n+1 in G, because if g(m) = n+1, then f
(something) = n and so n is in F and G. Contradiction. In
 particular, 3 must be in F, and so f(2) = 3. 
> 
>   Suppose f(n) = k. Then g(n) = f(k) + 1. So |Nf(k)
+1 Ç G| = n. But |Nf(k)+1 Ç F| = k, so n + k = f
(k) + 1, or f(k) = n + k - 1. Hence g
(n) = n + k. So n + k + 1 must be in F and hence f
(k+1) = n + k + 1. This so given the value of f for n we 
can find it for k and k+1. 
> 
>   Using k+1 each time, we get, successively, f
(2) = 3, f(4) = 6, f(7) = 11, f(12) = 19, f(20) = 32, f
(33) = 53, f(54) = 87, f(88) = 142, f(143) = 231, f
(232) = 375, which is not much help. Trying again with k,
 we get: f(3) = 4, f(4) = 6, f(6) = 9, f(9) = 14, f
(14) = 22, f(22) = 35, f(35) = 56, f(56) = 90, f
(90) = 145, f
(145) = 234. Still not right, but we can try backing up s
lightly and using k+1: f
(146) = 236. Still not right, we need to back up further:
 f(91) = 147, f(148) = 239, f(240) = 388. 
> 
> 
> 
> 
> 
> 
> 
> -------------------------------------------------------
-----------------------
>   Busca Yahoo! 
>   O serviço de busca mais completo da Internet. O que v
ocê pensar o Yahoo! encontra.
> 

 
__________________________________________________________________________
E-mail Premium BOL
Antivírus, anti-spam e até 100 MB de espaço. Assine já!
http://email.bol.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 é <nicolau@mat.puc-rio.br>
=========================================================================