Re: [obm-l] Problema das pesagens

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Sat, Aug 17, 2002 at 01:18:04PM -0300, ghaeser@zipmail.com.br 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 é <nicolau@mat.puc-rio.br>
=========================================================================