Questão M03 da 2ª fase da FUVEST 2017
Um quadriculado é formado por n \times n quadrados iguais, conforme ilustrado para n = 2 e n = 3. Cada um desses quadrados será pintado de azul ou de branco. Dizemos que dois quadrados \text{Q}_1 e \text{Q}_2 do quadriculado estão conectados se ambos estiverem pintados de azul e se for possível, por meio de movimentos horizontais e verticais entre quadrados adjacentes, sair de \text{Q}_1 e chegar a \text{Q}_2 passando apenas por quadrados pintados de azul.
a) Se n = 2, de quantas maneiras distintas será possível pintar o quadriculado de modo que o quadrado \text{Q}_1 do canto inferior esquerdo esteja conectado ao quadrado \text{Q}_2 do canto superior direito?
b) Suponha que n = 3 e que o quadrado central esteja pintado de branco. De quantas maneiras distintas será possível pintar o restante do quadriculado de modo que o quadrado \text{Q}_1 do canto superior esquerdo esteja conectado ao quadrado \text{Q}_2 do canto superior direito?
c) Suponha que n = 3. De quantas maneiras distintas será possível pintar o quadriculado de modo que o quadrado \text{Q}_1 do canto superior esquerdo esteja conectado ao quadrado \text{Q}_2 do canto superior direito?
Reportar erro na questão
Resolução comentada
a) Q1 e Q2 são os cantos opostos e já precisam ser azuis. Restam dois quadrados, o superior esquerdo e o inferior direito, e cada um pode ser azul ou branco, o que dá 2^2=4 pintinturas possíveis.
Os cantos opostos só se conectam passando por um desses dois quadrados, pois não são adjacentes. Basta que pelo menos um deles seja azul. Só falha o caso em que os dois são brancos.
Resposta: 3 maneiras.
b) Com o centro branco, os 8 quadrados da borda formam um anel. Chame os cantos de A=Q_1 (superior esquerdo) e C=Q_2 (superior direito), e percorra o anel assim: B (meio de cima), C, D, E, F, G, H e de volta a A. A e C são azuis. Os outros 6 quadrados são livres, o que dá 2^6=64 pintinturas.
Há dois caminhos possíveis entre A e C:
- Pelo caminho curto, A-B-C, que exige B azul. Sobram 5 quadrados livres: 2^5=32.
- Com B branco, só resta o caminho longo, A-H-G-F-E-D-C. Ele exige H,G,F,E,D todos azuis, o que dá 1 maneira.
Resposta: 33 maneiras.
c) Separe pelo quadrado central M.
- M branco: é exatamente o item (b), com 33 maneiras.
- M azul: A e C são azuis, e os livres são B,D,E,F,G,H (64 pintinturas).
- Se B é azul, A-B-C já conecta, e os outros 5 são livres: 2^5=32.
- Se B é branco, A só sai por H e C só sai por D, então H e D precisam ser azuis. Nesse caso H-M-D completa o caminho A-H-M-D-C. Os quadrados E,F,G ficam livres: 2^3=8.
- Total com M azul: 32+8=40.
Resposta: 73 maneiras.
Assuntos: análise combinatória, princípio multiplicativo, contagem com casos.
Reportar erro na resolução
Ver como caiu na prova
