Q4 Matemática  (Benelux 2012)

Ontem, $n\ge 4$ pessoas estavam sentadas ao redor de uma mesa redonda. Cada participante lembra apenas quem eram seus dois vizinhos, mas não necessariamente qual deles estava sentado à sua esquerda e qual estava sentado à sua direita. Hoje, você gostaria que as mesmas pessoas se sentassem ao redor da mesma mesa redonda para que cada participante tenha os mesmos dois vizinhos de ontem (é possível que o vizinho do lado esquerdo de ontem seja o vizinho do lado direito de hoje). Você tem permissão para questionar alguns dos participantes: se alguém for perguntado, ele responderá apontando para seus dois vizinhos de ontem. a) Determine o número mínimo $f(n)$ de participantes que você deve consultar para ter certeza de que terá sucesso, se as perguntas posteriores não dependerem do resultado das perguntas anteriores. Ou seja, você tem que escolher com antecedência a lista de pessoas que vai consultar, antes de efetivamente fazer qualquer pergunta. b) Determine o número mínimo $g(n)$ de participantes que você deve consultar para ter certeza do sucesso, se as perguntas posteriores puderem depender do resultado das perguntas anteriores. Ou seja, você pode esperar até obter a primeira resposta para escolher a quem fazer a segunda pergunta e assim por diante.