Em uma sala de reuniões há uma mesa circular com cadeiras em volta. Nessa sala estão Abel, Daniel e Rafael que esperam Pedro, um amigo comum. Um dos três presentes diz: “Vamos nos

Gabarito

Errado

Comentário do professor

Modele as cadeiras vazias entre os três presentes por \(x_1,x_2,x_3\) (número de cadeiras vazias consecutivas entre cada par de amigos). O total de cadeiras é \(3+x_1+x_2+x_3\).

Uma cadeira em que Pedro não tenha nenhum dos três como vizinho ocorre quando ela está no interior de uma sequência vazia de comprimento \(\ge 3\). Em uma sequência de comprimento \(x\) há \(\max(0,x-2)\) cadeiras com ambos os vizinhos vazios.

Queremos exatamente uma cadeira assim, logo \(\sum \max(0,x_i-2)=1\). Isso implica que exatamente um dos \(x_i\) vale 3 e os outros são \(\le 2\).

Para maximizar o total, escolha \(x_1=3\) e \(x_2=x_3=2\). Assim o número máximo de cadeiras é \(3+3+2+2=10\).