Re: [obm-l] caixa colorida

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

On Sun, May 07, 2006 at 11:31:38AM -0300, Eduardo Soares wrote:
  Temos tr�s caixas, uma azul, uma branca e uma vermelha, e 8 bolinhas. Cada
  bolinha tem um n�mero de 1 a 8, sem repeti��es. Distribu�mos as 8 bolinhas
  nas caixas, de maneira que h� pelo menos duas bolinhas em cada caixa. Logo,
  em cada caixa, somam-se todos os n�meros escritos nas bolinhas contidas na
  caixa. Os tr�s resultados denominam-se soma azul, soma branca, e soma
  vermelha, segundo a cor da caixa correspondente. Encontre todas as poss�veis
  distribui��es das bolinhas tais que a soma vermelha seja igual ao dobro da
  soma azul, e a soma vermelha menos a soma branca seja igual a soma branca
  menos a soma azul.

Sejam a, b, v as somas azul, branca e vermelha, resp. Claramente
a+b+v=1+2+3+4+5+6+7+8=36. Pelo enunciado v=2a, v-b=b-a donde
a = 8, b = 12, v = 16.

A partir daqui eu s� sei fazer o problema por for�a bruta e
h� 13 solu��es:

(7+1,8+4,6+5+3+2)

(6+2,8+4,7+5+3+1)
(6+2,8+3+1,7+5+4)
(5+3,8+4,7+6+2+1)
(5+2+1,8+4,7+6+3)


(7+1,6+4+2,8+5+3)
(7+1,5+4+3,8+6+2)

(6+2,7+5,8+4+3+1)
(6+2,7+4+1,8+5+3)
(4+3+1,7+5,8+6+2)
(5+3,7+4+1,8+6+2)

(5+3,6+4+2,8+7+1)
(6+2,5+4+3,8+7+1)

Obtive esta lista fazendo uma �rvore de possibilidades.
A bolinha 8 n�o pode entrar na caixa azul (pois devemos ter >= 2 bolinhas
por caixa). Assim, desconsiderando a bolinha 8 temos
a' = 8, b' = 4, v' = 16 ou a' = 8, b' = 12, v' = 8.
Observe que a partir de agora podemos desconsiderar a condi��o
de >= 2 bolinhas por caixa pois fica sendo autom�tica.

Para (8,4,16), a bolinha 7 pode entrar na primeira posi��o ou na terceira,
nos deixando com dois ramos: (1,4,16) e (8,4,9).

Para (1,4,16), a bolinha 6 � obrigada a ir para a terceira posi��o: (1,4,10).
Para (1,4,10), a bolinha 5 � obrigada a ir para a terceira posi��o: (1,4,5).
Para (1,4,5), a bolinha 4 pode ir para a segunda ou terceira posi��es:
(1,0,5) e (1,4,1). A partir daqui (1,0,5) acaba dando a primeira solu��o
a (1,4,1) � imposs�vel.

A partir de (8,4,9) obtemos o segundo bloco de solu��es.

De (8,12,8) podemos ir para (1,12,8), (8,5,8) e (8,12,1).
Cada uma destas tr�s configura��es obtem um bloco de solu��es, como acima.

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