O problema �: > 4.� poss�vel cobrirmos um tabuleiro 8x8 usando 21 trimin�s retos se tirarmos uma casa qualquer do tabuleiro?
A resposta � n�o. Inclusive, � poss�vel determinar todas as casas que podemos retirar de modo que a cobertura seja poss�vel. Para variar, a solu��o � usar uma pintura. Mas � uma pintura, digamos, dupla. Vamos associar a cada casinha (i+1;j+1) do tabuleiro um mon�mio da forma x^i*y^j: 1 x x^2 x^3 x^4 x^5 x^6 x^7 y xy x^2y x^3y x^4y x^5y x^6y x^7y y^2 xy^2 x^2y^2 x^3y^2 x^4y^2 x^5y^2 x^6y^2 x^7y^2 y^3 xy^3 x^2y^3 x^3y^3 x^4y^3 x^5y^3 x^6y^3 x^7y^3 y^4 xy^4 x^2y^4 x^3y^4 x^4y^4 x^5y^4 x^6y^4 x^7y^4 y^5 xy^5 x^2y^5 x^3y^5 x^4y^5 x^5y^5 x^6y^5 x^7y^5 y^6 xy^6 x^2y^6 x^3y^6 x^4y^6 x^5y^6 x^6y^6 x^7y^6 y^7 xy^7 x^2y^7 x^3y^7 x^4y^7 x^5y^7 x^6y^7 x^7y^7 (Espero que esteja leg�vel...) Agora, suponha que cobrimos o tabuleiro com os trimin�s 1x3. Observe que cada trimin� cobre tr�s casas associadas a termos da forma x^iy^j, x^iy^(j+1) e x^iy^(j+2) ou tr�s casas associadas a termos da forma x^iy^j, x^(i+1)y^j e x^(i+2)y^j. Somando os tr�s termos em cada caso, temos x^iy^j(1 + y + y^2) no primeiro caso e x^iy^j(1 + x + x^2) no segundo caso. Adivinha quais valores de x e y s�o legais para substituir? Para "zerar" as somas associadas a trimin�s, tomamos x = y = w, onde w � raiz da equa��o z^2 + z + 1 = 0 (w � uma das ra�zes c�bicas da unidade). Assim, se somarmos todos os mon�mios, todos aqueles associados a trimin�s s�o iguais a zero. Sobra s� o que corresponde � casa retirada. Mas somando todos os mon�mios obtemos (1 + x + ... + x^7)(1 + y + ... + y^7) Usando o fato de que 1 + x + x^2 = 1 + y + y^2 = 0 e que x^3 = y^3 = 1, temos que (1 + x + ... + x^7)(1 + y + ... + y^7) = (x^6 + x^7)(y^6 + y^7) = x^6y^6(1 + x)(1 + y) = (-x^2)(-y^2) = x^2y^2 Assim, se o mon�mio x^ny^m corresponde � casa que deve ser retirada, devemos ter m e n congruentes a 2 m�d 3, ou seja, (m = 2 ou m = 5) e (n = 2 ou n = 5). Olhando as posi��es correspondentes no tabuleiro, vemos que todas correspondem a uma casa s�, salvo simetrias. Neste caso, n�o � muito dif�cil ver que a cobertura � poss�vel (letras iguais representam casas cobertas por um mesmo trimin�): AAABBBCD EEEFFFCD GGGHHHCD IJKKKLLL IJMMMNNN IJOOO PQ RRRSSSPQ TTTUUUPQ []'s Shine __________________________________________________ Do You Yahoo!? Yahoo! Movies - coverage of the 74th Academy Awards� http://movies.yahoo.com/ ========================================================================= 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]> =========================================================================
