On Sat, Aug 17, 2002 at 01:18:04PM -0300, [EMAIL PROTECTED] wrote: > considere uma balança de dois pratos e n bolas sendo que uma delas possui > peso diferente (sem saber se a bola defeituosa é mais leve ou mais pesada) > > Determine a função f:IN->IN tal que f(n) > é o menor numero de pesagens suficientes > para determinar a bola defeituosa, n>=3. > > f(3) = f(4) = f(5) = 2 > f(6) = .. = f(11) = 3 > f(12) = .. = f(?) = 4
Na verdade f(5) = ... = f(12) = f(13) = 3 f(14) = ... = f(40) = 4 e em geral f((3^(n-1) + 1)/2) = ... = f((3^n - 1)/2) = n É importante que no enunciado *não* se exige determinar se a bola defeituosa é mais pesada ou mais leve. Apresento a prova de que f(13) <= 3 e de que f(14) >= 4, acho que elas ilustram todas as idéias importantes. f(13) <= 3 Devemos mostrar como determinar a bola defeituosa dentre as bolas A, B, C, D, E, F, G, H, I, J, K, L, M. Vou exibir o processo em detalhe, como se fosse um programa. Perdoem-me os amantes da língua portuguesa. Observe que há 26 possibilidades: a bola defeituosa pode ser A e ser mais pesada, chamemos este caso de A+ a bola defeituosa pode ser A e ser mais leve, chamemos este caso de A- ... a bola defeituosa pode ser M e ser mais pesada, chamemos este caso de M+ a bola defeituosa pode ser M e ser mais leve, chamemos este caso de M- Nossa primeira pesagem será A,B,C,D contra E,F,G,H + Se o prato A,B,C,D for mais pesado sabemos que a possibilidade certa é A+,B+,C+,D+,E-,F-,G- ou H- (e portanto as bolas I,J,K,L e M são boas). Pesamos agora A,B,E contra C,D,F + Se o prato A,B,E for mais pesado sabemos que A+,B+ ou F- e a pesagem A contra B termina o problema. - Se o prato A,B,E for mais leve sabemos que E-,C+ ou D+ e a pesagem C contra D termina o problema. = Se os pratos se equilibrarem sabemos que G- ou H- e a pesagem G contra H termina o problema. - Se o prato A,B,C,D for mais leve sabemos que A-,B-,C-,D-,E+,F+,G+ ou H+. A,B,E contra C,D,F + Se A,B,E é mais pesado temos E+,C- ou D- e fazemos C contra D - Se A,B,E é mais leve temos A-,B- ou F+ e fazemos A contra B = Se equilibra temos G+ ou H+ e fazemos G contra H = Se os pratos A,B,C,D e E,F,G,H equilibram temos I+-, J+-, K+-, L+- ou M+- e fazemos A,B,C contra I,J,K + Se A,B,C é mais pesado temos I-,J- ou K- e fazemos I contra J - Se A,B,C é mais leve temos I+,J+ ou K+ e fazemos I contra J = Se A,B,C e I,J,K equilibram temos L+- ou M+- e fazemos A contra L = Observe que se A e L equilibram temos M+-, ou seja, sabemos que M é a bola diferente mas como ela nunca subiu na balança não sabemos se ela é mais pesada ou mais leve. Resumindo, seguindo as instruções acima temos: +++ A+ ++- B+ ++= F- +-+ C+ +-- D+ +-= E- +=+ H- +=- G- +== IMPOSSÍVEL -++ D- -+- C- -+= E+ --+ B- --- A- --= F+ -=- H+ -=+ G+ -== IMPOSSÍVEL =++ J- =+- I- =+= K- =-+ I+ =-- J+ =-= K+ ==+ L- ==- L+ === M+ ou M- f(14) >= 4 Devemos mostrar que é impossível resolver o problema com 14 bolas e 3 pesagens. Temos 28 possibilidades em total e é aceitável manter no final uma dúvida entre, digamos N+ e N-. Note que só podemos ter esta dúvida se N nunca subiu na balança; se *duas* moedas nunca tivessem subido na balança não saberíamos qual das duas era diferente portanto esta dúvida final só pode existir para (no máximo) *uma* moeda. Devemos portanto ao final do processo decidir entre 27 possibilidades. Cada vez que usamos a balança há três resultados possíveis e podemos resumir as conclusões do algorimo em 27 = 3^3 linhas de conclusões finais correspondentes a resultados consecutivos da balança (são os ramos da árvore de deduções descrita acima como um programa). Observe que o caso-dúvida (N+ ou N-) deve necessariamente corresponder a ===. Como temos 27 possibilidades e 27 linhas não podem existir linhas impossíveis (como +== e -== no caso 13 acima). Assim na primeira pesagem precisamos dividir as 27 possibilidades em 9 para +, 9 para - e 9 para =. Mas se colocarmos m bolas em um prato e m bolas no outro prato teremos 2m possibilidades para +, 2m possibilidades para - e 27 - 4m possibilidades para =. Não podemos ter 2m = 9 pois 9 é ímpar. []s, N. ========================================================================= 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 é <[EMAIL PROTECTED]> =========================================================================