Maximize correct guesses in a hat line puzzle

Q: Maximize correct guesses in a hat line puzzle

This question evaluates logical reasoning about information constraints, group strategy design, and combinatorial encoding in the Coding & Algorithms domain, with a level of abstraction that emphasizes conceptual understanding alongside practical algorithmic reasoning.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem (Hat Guessing Strategy)

There are N people standing in a line. Each person wears a hat that is either Red or Blue.

Person i can see the hats of people in front of them (people with index > i ).
They cannot see their own hat or the hats behind them.
Starting from the back of the line (person 1 ) to the front (person N ), each person must say out loud either Red or Blue as their guess of their own hat color.
Everyone hears all previous guesses.
Before the guessing starts, the group can agree on a deterministic strategy.

Task

Describe a strategy that guarantees the maximum possible number of correct guesses in the worst case , regardless of the actual hat arrangement.
State how many people can be guaranteed to guess correctly.

Notes

You may assume N >= 1 .
The hat colors are arbitrary (not necessarily random).

Maximize correct guesses in a hat line puzzle

Quick Overview

Problem (Hat Guessing Strategy)

Task

Notes

Comments (0)