Questão de Raciocínio Lógico · FCC CLDF 2018 (nº 17)

O conceito-chave aqui é que podemos representar as cores das peças como números: 0 para branco e 1 para preto. Quando giramos uma linha ou coluna, estamos "somando 1" (módulo 2) à cor de cada peça afetada. Nosso objetivo é que todas as peças se tornem 0 (brancas). Como girar uma peça duas vezes a retorna ao estado original, cada linha ou coluna será girada uma vez (1) ou nenhuma vez (0) no resultado final.

Vamos representar o tabuleiro inicial:
Linha 1: Preto, Branco, Preto (1, 0, 1)
Linha 2: Branco, Preto, Branco (0, 1, 0)
Linha 3: Preto, Branco, Preto (1, 0, 1)

Seja $r_i$ igual a 1 se a linha $i$ for girada, e 0 caso contrário.
Seja $c_j$ igual a 1 se a coluna $j$ for girada, e 0 caso contrário.
Para cada peça na posição $(i, j)$, sua cor final $x'_{ij}$ será $x_{ij} + r_i + c_j \pmod 2$.
Queremos que $x'_{ij} = 0$ para todas as peças. Isso significa que $r_i + c_j \equiv x_{ij} \pmod 2$.

Primeiro, vamos usar um truque de paridade para eliminar algumas alternativas.
Somando todas as 9 equações ($r_i + c_j \equiv x_{ij} \pmod 2$):
Cada $r_i$ aparece 3 vezes (uma para cada coluna), e cada $c_j$ aparece 3 vezes (uma para cada linha).
Então, $3(r_1+r_2+r_3) + 3(c_1+c_2+c_3) \equiv \sum x_{ij} \pmod 2$.
Como $3 \equiv 1 \pmod 2$, a equação se torna:
$(r_1+r_2+r_3) + (c_1+c_2+c_3) \equiv \sum x_{ij} \pmod 2$.
A soma de todas as peças pretas no tabuleiro inicial é 5 (contando os "1"s).
Portanto, o número total de jogadas (flips de linhas + flips de colunas) deve ser ímpar, pois $5 \equiv 1 \pmod 2$.
Isso elimina as alternativas com número par de jogadas (2, 4, 6).

Agora, vamos testar o menor número ímpar de jogadas:

1. 1 jogada: Se girarmos apenas uma linha ou uma coluna, não conseguiremos deixar todas as peças brancas, pois há peças pretas espalhadas por várias linhas e colunas. Por exemplo, girar $R_1$ mudaria $(1,0,1)$ para $(0,1,0)$, mas as outras duas linhas permaneceriam com peças pretas.

2. 3 jogadas: Vamos tentar encontrar uma solução com 3 jogadas.
   Montando o sistema de equações:
   $r_1 + c_1 \equiv 1$ (1)
   $r_1 + c_2 \equiv 0$ (2)
   $r_1 + c_3 \equiv 1$ (3)

   $r_2 + c_1 \equiv 0$ (4)
   $r_2 + c_2 \equiv 1$ (5)
   $r_2 + c_3 \equiv 0$ (6)

   $r_3 + c_1 \equiv 1$ (7)
   $r_3 + c_2 \equiv 0$ (8)
   $r_3 + c_3 \equiv 1$ (9)

   Das equações (1), (2), (3), podemos expressar $c_j$ em termos de $r_1$:
   $c_1 \equiv r_1 + 1 \pmod 2$
   $c_2 \equiv r_1 \pmod 2$
   $c_3 \equiv r_1 + 1 \pmod 2$

   Substituindo esses valores nas equações para $r_2$:
   $r_2 + (r_1+1) \equiv 0 \implies r_1 + r_2 \equiv 1 \pmod 2$
   $r_2 + r_1 \equiv 1 \implies r_1 + r_2 \equiv 1 \pmod 2$
   $r_2 + (r_1+1) \equiv 0 \implies r_1 + r_2 \equiv 1 \pmod 2$
   Todas as equações para $r_2$ são consistentes e nos dão $r_1 + r_2 \equiv 1 \pmod 2$.

   Substituindo nas equações para $r_3$:
   $r_3 + (r_1+1) \equiv 1 \implies r_1 + r_3 \equiv 0 \pmod 2$
   $r_3 + r_1 \equiv 0 \implies r_1 + r_3 \equiv 0 \pmod 2$
   $r_3 + (r_1+1) \equiv 1 \implies r_1 + r_3 \equiv 0 \pmod 2$
   Todas as equações para $r_3$ são consistentes e nos dão $r_1 + r_3 \equiv 0 \pmod 2$.

   Temos duas condições:
   I) $r_1 + r_2 \equiv 1 \pmod 2$
   II) $r_1 + r_3 \equiv 0 \pmod 2$

   Podemos escolher $r_1$ para encontrar uma solução:
   Cenário 1: Se $r_1 = 0$ (não girar a linha 1)
   De (I): $0 + r_2 \equiv 1 \implies r_2 = 1$ (girar a linha 2)
   De (II): $0 + r_3 \equiv 0 \implies r_3 = 0$ (não girar a linha 3)
   Número de giros de linha: $r_1+r_2+r_3 = 0+1+0 = 1$.
   Agora, calculamos os giros de coluna:
   $c_1 \equiv r_1 + 1 \equiv 0 + 1 \equiv 1$ (girar a coluna 1)
   $c_2 \equiv r_1 \equiv 0$ (não girar a coluna 2)
   $c_3 \equiv r_1 + 1 \equiv 0 + 1 \equiv 1$ (girar a coluna 3)
   Número de giros de coluna: $c_1+c_2+c_3 = 1+0+1 = 2$.
   Total de jogadas = $1 + 2 = 3$.

   Vamos verificar essa solução (girar $R_2$, $C_1$, $C_3$):
   Inicial: $\begin{pmatrix} 1 & 0 & 1 \ 0 & 1 & 0 \ 1 & 0 & 1 \end{pmatrix}$
   Girar $R_2$: $\begin{pmatrix} 1 & 0 & 1 \ 1 & 0 & 1 \ 1 & 0 & 1 \end{pmatrix}$
   Girar $C_1$: $\begin{pmatrix} 0 & 0 & 1 \ 0 & 0 & 1 \ 0 & 0 & 1 \end{pmatrix}$
   Girar $C_3$: $\begin{pmatrix} 0 & 0 & 0 \ 0 & 0 & 0 \ 0 & 0 & 0 \end{pmatrix}$
   Todas as peças estão brancas!

   Como encontramos uma solução com 3 jogadas, e sabemos que 1 jogada não é suficiente e o número total de jogadas deve ser ímpar, 3 é o mínimo.

(A) Incorreta: O número total de jogadas deve ser ímpar, conforme a análise de paridade. 2 é um número par.
(B) Incorreta: O número total de jogadas deve ser ímpar, conforme a análise de paridade. 4 é um número par.
(C) Correta: A análise algébrica e o teste de paridade demonstram que 3 jogadas é o número mínimo. Uma solução é girar a linha 2, a coluna 1 e a coluna 3. Outra solução é girar as linhas 1 e 3, e a coluna 2.
(D) Incorreta: O número total de jogadas deve ser ímpar, conforme a análise de paridade. 6 é um número par. Além disso, mesmo que fosse um número ímpar, já encontramos uma solução com menos jogadas (3).
(E) Incorreta: Embora 5 seja um número ímpar e, portanto, teoricamente possível, já encontramos uma solução com um número menor de jogadas (3). O objetivo é encontrar a quantidade mínima.