Q2 Matemática (Czech-Polish-Slovak Match 2016)
Sejam inteiros pares. Considere um tabuleiro de tamanho cujas células são coloridas em preto ou branco. O Adivinho não vê a coloração do tabuleiro, mas pode fazer algumas perguntas ao Oráculo sobre isso. Em particular, ela pode perguntar sobre duas células adjacentes (compartilhando uma borda) e o Oracle revela se as duas células adjacentes têm a mesma cor ou não. O Guesser eventualmente quer encontrar a paridade do número de pares de células adjacentes cujas cores são diferentes. Qual é o número mínimo de perguntas que a Guesser precisa fazer para garantir que ela encontre sua resposta? (República Tcheca)