Maths Olympiad Prep

Library / /114 of 144

Combinatorics Difficulty 8.6 Shortlist Find the answer

The leader of an IMO team chooses positive integers nn and kk with n>kn > k, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an nn-digit binary string, and the deputy leader writes down all nn-digit binary strings which differ from the leader’s in exactly kk positions. (For example, if n=3n = 3 and k=1k = 1, and if the leader chooses 101101, the deputy leader would write down 001,111001, 111 and 100100.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of nn and kk) needed to guarantee the correct answer?

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

Solution

To solve this problem, we need to determine the minimum number of guesses a contestant needs to guarantee correctly identifying the leader’s n n -digit binary string, given the constraints on how the strings can differ.

### Explanation

1. Binary Strings and Hamming Distance:
The problem involves binary strings of length n n and the concept of Hamming distance, which measures the number of positions at which two strings differ. Specifically, the deputy leader lists all binary strings that differ in exactly k k positions from the leader’s string.

2. Determining the Guesses:
- If n=2k n = 2k , each string written by the deputy is unique in the sense that no other strings exist which differ by exactly k k positions. Therefore, the contestant must check two strings. The strings could potentially be symmetric—a situation arising from the properties of binary complements within a set of size 2k 2k . It results in no single binary string having a unique distance of k k from every other string without ambiguity.
- If n2k n \neq 2k , there is less ambiguity. In such a scenario, examining one potential candidate string suffices because, among the possibilities, one and only one string will be the solution (the leader's string), ensuring the contestant can identify the leader's string definitively with a single guess.

3. Mathematical Justification:
- **Case n=2k n = 2k **: The contestant faces a symmetrical setup where the total number of different strings at a distance of k k equals the remaining possibilities of leader's string setup, necessitating 2 guesses.
- **Case n2k n \neq 2k **: Asymmetry in possible distances allows the contestant to uniquely identify the leader's binary string with just 1 guess since a single guess resolves all possibilities.

Based on these assessments, the minimum number of guesses required is:
2 if n=2k, and 1 otherwise \boxed{2 \text{ if } n = 2k, \text{ and } 1 \text{ otherwise}}
This answer effectively accounts for all potential configurations of the problem, ensuring the uniqueness needed for a definitive guess regarding the leader’s string.

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.