[obm-l] III-olimpiada de maio

[Faelccmm@xxxxxxx]

Ola pessoal,

Abaixo esta exposto um problema, a solucao dele e minha duvida entre parenteses no corpo da solucao. Nao precisem explicar o problema inteiro, a unica coisa que eu nao entendi foi o que se pensou para criar a equacao 8 × 8 + 2 × 7 =78. No mais, esta completamente entendido. 


Num tabuleiro de 8 por 8, colocam-se 10 fichas que ocupam, cada uma, uma casa. Em cada casa sem ficha estah escrito um numero entre 0 e 8, que eh igual aa quantidade de fichas colocadas nas casas vizinhas. Casas vizinhas sao as que tem um lado ou um vertice em comum. Mostre uma distribuicao das fichas que faca que a soma dos numeros escritos no tabuleiro seja a maior possivel.

Solucao:


Cada ficha soma 1 em cada uma das casas vizinhas que estao livres de ficha. Uma casa tem como maximo 8 vizinhas (perde vizinhas se esta numa borda do tabuleiro).Vejamos que eh impossivel colocar as 10 fichas em 10 casas isoladas, tais que nenhuma fique na borda do tabuleiro. Podemos pensar que temos um tabuleiro de 6 por 6 –pois as casas das bordas nao interessam– ou dividimos em 9 setores 2 por 2, mediante paralelas aos lados. Se queremos selecionar casas isoladas, em cada setor podemos escolher ao maximo 1. Sao, em total, no maximo 9 casas isoladas. Se uma casa fica na borda do tabuleiro, tera como maximo 5 vizinhas. Ou seja ao colocar uma ficha ali, somara no maximo 5. Por outro lado, podem-se colocar 8 fichas isoladas mais 2 nas quais as casas se toquem num vertice; neste caso seperde so uma casa vizinha por cada uma delas. 
A soma total eh: 8 × 8 + 2 × 7 =78. (Como foi montada esta equacao ?) Duas possiveis distribuicoes sao as seguintes: 


1   1   2   1   2   1   1   0   
1   *   2   *   2   *   1   0   
2   2   4   2   4   2   2   0   
1   *   2   *   2   *   1   0   
2   2   4   2   4   2   2   0   
1   *   2   *   2   *   2   1   
1   1   2   1   2   2   *   1   
0   0   0   0   0   1   1   1   




0   1   1   2   1   2   1   1   
0   1   *   2   *   2   *   1   
1   2   3   3   3   3   2   1   
1   *   2   *   2   *   1   0   
1   2   3   3   3   3   2   1   
1   2   *   2   *   2   *   1   
1   *   2   2   1   2   1   1   
1   1   1   0   0   0   0   0