Maths Olympiad Prep

Library / /12 of 13

Combinatorics Difficulty 6.9 National olympiad Find the answer

Let n>1n>1 be a positive integer. Ana and Bob play a game with other nn people. The group of nn people form a circle, and Bob will put either a black hat or a white one on each person's head. Each person can see all the hats except for his own one. They will guess the color of his own hat individually.

Before Bob distribute their hats, Ana gives nn people a strategy which is the same for everyone. For example, it could be "guessing the color just on your left" or "if you see an odd number of black hats, then guess black; otherwise, guess white".

Ana wants to maximize the number of people who guesses the right color, and Bob is on the contrary.

Now, suppose Ana and Bob are clever enough, and everyone forms a strategy strictly. How many right guesses can Ana guarantee?

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given a group of n n people forming a circle, Ana and Bob play a strategy-based game where Bob assigns each person either a black hat or a white hat. The challenge is that each person can see every other hat except their own. The goal is for Ana to devise a strategy to maximize the number of correct guesses about their own hat color, knowing Bob will try to minimize the number of correct guesses.

### Strategy Formulation

To tackle this problem, we need to explore the possibilities and constraints. The strategy Ana can choose must offer the best chance for correctness irrespective of Bob's actions.

Consider the following scenario:
- Each person makes a guess based on what they can see. Since each person only misses their own hat, the strategy that should be employed has to utilize this view efficiently.
- In particular, Ana might instruct each person to make their guess based on the color distribution they see among the other n1 n-1 people.

### Analysis

One effective strategy could be for each person to make a guess based on parity (odd or even count of a specific color).

Let's suppose:
- If the number of black hats seen by an individual is odd, they guess white.
- If the number of black hats seen is even, they guess black.

Bob aims to minimize the correct guesses. The most trouble Ana can create for Bob is by leaving Bob with minimal options.

### Ensuring Maximum Correct Guesses

For any given whole arrangement among n n people:
1. If we apply the parity check described above, there is a configuration wherein half plus one of the guesses could potentially be correct.
2. However, Bob can always adjust such that at most half (floor division) of guesses are correct, except one—a crucial impossibility—creating an inevitable wrong guess for that person.

Thus, Ana can ensure a maximum of correct guesses, dictated by the fact the challenge lies in the inability of an individual to resolve the parity of their own hat.

### Conclusion

With n n people, Ana's best guaranteed correct guesses that Bob cannot disrupt is the result of:

n12 \left\lfloor \frac{n-1}{2} \right\rfloor

Thus, Ana can guarantee that at least this many people will guess correctly:

n12 \boxed{\left\lfloor \frac{n-1}{2} \right\rfloor}

This solution leverages the inherent symmetry and parity checks within circular arrangements, bounded by strategic adversarial limitations.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.