Re: [obm-l] funções e poliminós

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

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 é <nicolau@mat.puc-rio.br>
=========================================================================