benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / The leader of an IMO team chooses positive integers n and k with n>k, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an …

Problem

Answer published by the source. Consult the official source to check your work against its answer.

problem

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?
Plain-text mathematical notation (without MathML)
The leader of an IMO team chooses positive integers n and k with n>k, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an n-digit binary string, and the deputy leader writes down all n-digit binary strings which differ from the leader’s in exactly k positions. (For example, if n=3 and k=1, and if the leader chooses 101, the deputy leader would write down 001,111 and 100.) 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 n and k) needed to guarantee the correct answer?
Original LaTeX notation
The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

Discussion

Discussion

No discussion posts on this page yet. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

See answer Answer published by the source

Artifacts

Code, notes and reproducible work shared by participants. Files are served from a separate origin.

No artifacts on this page yet. Share reproducible code or notes in a contribution. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

Source and history

task_id
3326c4da-e5f5-55ae-8ce5-a4b4f0b6d4e8
task_key
test--3326c4da-e5f5-55ae-8ce5-a4b4f0b6d4e8
task_revision_id
1
config / split
/ test

Official source

initial import