Questão de Raciocínio Lógico · FGV CMSP 2024 (nº 64)

Este problema de otimização pede o menor número de vagas ocupadas para que toda vaga vazia tenha, obrigatoriamente, um carro ao lado. Isso significa que não pode haver nenhuma vaga vazia "isolada" ou "desprotegida".

A condição "qualquer vaga vazia terá, pelo menos, um carro já estacionado ao lado" significa que:

1. Se uma vaga V está vazia, ela não pode ter ambos os vizinhos vazios. Ou seja, a sequência V V V é proibida.
2. Se a vaga 1 (V_1) está vazia, sua vizinha à direita (V_2) deve estar ocupada (O). Se V_2 estivesse vazia, V_1 não teria vizinho ocupado (pois não há vizinho à esquerda). Assim, V_1 V_2 é proibido.
3. Analogamente, se a vaga 100 (V_100) está vazia, sua vizinha à esquerda (V_99) deve estar ocupada (O). Assim, V_99 V_100 é proibido.

Para minimizar o número de vagas ocupadas (N_O), devemos maximizar o número de vagas vazias (N_V).
As vagas ocupadas (O) dividem as 100 vagas em N_O + 1 "segmentos" de vagas vazias.
Seja x_0 o número de vagas vazias antes da primeira vaga ocupada, x_i o número de vagas vazias entre a i-ésima e a (i+1)-ésima vaga ocupada, e x_{N_O} o número de vagas vazias após a última vaga ocupada.
A soma de todas as vagas vazias é N_V = x_0 + x_1 + ... + x_{N_O}.

Com base nas condições proibidas:

• x_0 (vagas vazias no início) pode ser no máximo 1 (V O...). Se fosse V V..., a primeira V não teria vizinho ocupado.
• x_{N_O} (vagas vazias no final) pode ser no máximo 1 (...O V). Se fosse ...V V, a última V não teria vizinho ocupado.
• x_i (vagas vazias entre duas vagas ocupadas, O x_i O) pode ser no máximo 2 (O V V O). Se fosse O V V V O, a V do meio não teria vizinho ocupado.

Para maximizar N_V, atribuímos os valores máximos a cada x_i:
N_V <= x_0 + x_1 + ... + x_{N_O-1} + x_{N_O}
N_V <= 1 + (N_O - 1) * 2 + 1 (assumindo N_O >= 1)
N_V <= 1 + 2*N_O - 2 + 1
N_V <= 2*N_O.

Sabemos que N_V + N_O = 100 (total de vagas).
Substituindo N_V por 100 - N_O:
100 - N_O <= 2*N_O
100 <= 3*N_O
N_O >= 100 / 3
N_O >= 33.33...

Como o número de vagas ocupadas deve ser um número inteiro, o valor mínimo de N_O é 34.

Para verificar se N_O = 34 é realmente possível, precisamos construir uma configuração.
Se N_O = 34, então N_V = 100 - 34 = 66.
Temos N_O + 1 = 35 segmentos para vagas vazias (x_0 a x_{34}).
Precisamos que x_0 + x_1 + ... + x_{34} = 66.
Podemos usar:

• x_0 = 1 (a primeira vaga é vazia, a segunda é ocupada: V O...)
• x_{34} = 1 (a penúltima vaga é ocupada, a última é vazia: ...O V)
• 32 segmentos intermediários (x_1 a x_{32}) com 2 vagas vazias cada (O V V O).
• 1 segmento intermediário (x_{33}) com 0 vagas vazias (O O).

Somando as vagas vazias: 1 + (32 * 2) + 0 + 1 = 1 + 64 + 0 + 1 = 66.
Esta configuração é válida e utiliza 34 vagas ocupadas e 66 vagas vazias, totalizando 100 vagas.

Exemplo da configuração: V O (V V O) * 32 O V
V_1 O_2 V_3 V_4 O_5 V_6 V_7 O_8 ... V_{96} V_{97} O_{98} O_{99} V_{100}.

• V_1: vizinho O_2. OK.
• V_3: vizinho O_2. OK.
• V_4: vizinho O_5. OK.
• V_{96}: vizinho O_{95}. OK.
• V_{97}: vizinho O_{98}. OK.
• V_{100}: vizinho O_{99}. OK.
  Todas as vagas vazias têm pelo menos um vizinho ocupado.

• (A) Incorreta: Se houvesse 33 vagas ocupadas, o número máximo de vagas vazias seria $2 \times 33 = 66$. Como o total de vagas é 100, teríamos $100 - 33 = 67undefined67 > 66$).
• (B) Correta: O número mínimo de vagas ocupadas é 34. Com 34 vagas ocupadas, é possível arranjar as vagas de forma que todas as 66 vagas vazias tenham pelo menos um vizinho ocupado, como demonstrado na explicação.
• (C) Incorreta: 40 é um número possível de vagas ocupadas, mas não é o mínimo.
• (D) Incorreta: 49 é um número possível de vagas ocupadas, mas não é o mínimo.
• (E) Incorreta: A armadilha aqui é interpretar a condição como "não pode haver duas vagas vazias adjacentes" (ou seja, V V proibido). Se V V fosse proibido, a densidade máxima de vagas vazias seria V O V O ..., o que levaria a um mínimo de 50 vagas ocupadas. No entanto, O V V O é uma sequência permitida, pois cada V tem um O ao lado.