Olimpiada Nacional de Argentina 2005 Problema 6
6 Sea $k\geq 1$ un entero. En un grupo de $2k+1$ personas, algunas son sinceras (siempre dicen la verdad) y el resto son impredecibles (a veces dicen la verdad y a veces mienten). Se sabe que los impredecibles son a lo sumo $k$ . Alguien externo al grupo debe determinar quién es sincero y quién es impredecible mediante una secuencia de pasos. En cada paso elige dos personas $A$ y $B$ del grupo y le pregunta a $A$ si $B$ es sincero. Demuestre que después de $3k$ pasos el extraño podrá clasificar con certeza a las $2k+1$ personas del grupo. (Antes de hacer cada pregunta, se conocen las respuestas a las preguntas anteriores.) Aclaración: Cada una de las $2k+1$ personas del grupo sabe quiénes son sinceros y quiénes son impredecibles.
0
0
Inicia sesión para agregar soluciones y pistas