Acertijos que usan en Google para sus entrevistas de trabajo

Según dicen, a las personas que buscan trabajo en Google se les pide solucionar dos acertijos acerca de presos. Gorras azules y rojas Cien presos se ubican en fila y les ponen gorras de color rojo o azul. No se sabe la cantidad de gorras azules y rojas. Cada preso solo ve el gorro de la persona en frente de él. Empezando desde el final de la fila el vigilante les pregunta a cada uno el color de su gorra, si el preso responde bien se le deja en libertad, si no, lo ejecutan. Cada siguiente preso escucha la respuesta del preso anterior pero no sabe si fue la respuesta correcta o no. ¿Qué deben acordar los presos antes de la prueba para que queden en libertad más personas? 100 personas y un foco 100 personas de la tarea anterior están en prisión. Todos están en celdas aisladas sin la posibilidad de hablarse entre sí. Cada día el vigilante elige a un preso al azar y lo mete por un tiempo en una celda de castigo. Solo tiene un foco y un interruptor. Cada preso que pasa por esa celda puede encender o apagar el foco. En cuanto alguno de los presos diga que los 100 han estado en la celda de castigo al menos una vez, los dejarán ir; pero si se equivoca, los ejecutarán a todos. Antes de esta prueba a los presos solo se les da una noche para hablar y definir su estrategia. ¿Qué deben inventar para que los dejen ir a todos tomando en cuenta que desde las demás celdas no se ve la luz de la celda de castigo?