benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / An illusionist and his assistant are about to perform the following magic trick.

Problem

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

problem

An illusionist and his assistant are about to perform the following magic trick. Let kk be a positive integer. A spectator is given n=k!+k−1n=k!+k-1 balls numbered $1,2,…,n$. Unseen by the illusionist, the spectator arranges the balls into a sequence as he sees fit. The assistant studies the sequence, chooses some block of kk consecutive balls, and covers them under her scarf. Then the illusionist looks at the newly obscured sequence and guesses the precise order of the kk balls he does not see. Devise a strategy for the illusionist and the assistant to follow so that the trick always works. (The strategy needs to be constructed explicitly. For instance, it should be possible to implement the strategy, as described by the solver, in the form of a computer program that takes kk and the obscured sequence as input and then runs in time polynomial in nn. A mere proof that an appropriate strategy exists does not qualify as a complete solution.)
Plain-text mathematical notation (without MathML)
An illusionist and his assistant are about to perform the following magic trick.

Let k be a positive integer. A spectator is given n=k!+k−1 balls numbered $1,2,…,n$. Unseen by the illusionist, the spectator arranges the balls into a sequence as he sees fit. The assistant studies the sequence, chooses some block of k consecutive balls, and covers them under her scarf. Then the illusionist looks at the newly obscured sequence and guesses the precise order of the k balls he does not see.

Devise a strategy for the illusionist and the assistant to follow so that the trick always works.

(The strategy needs to be constructed explicitly. For instance, it should be possible to implement the strategy, as described by the solver, in the form of a computer program that takes k and the obscured sequence as input and then runs in time polynomial in n. A mere proof that an appropriate strategy exists does not qualify as a complete solution.)
Original LaTeX notation
An illusionist and his assistant are about to perform the following magic trick.

Let $k$ be a positive integer. A spectator is given $n=k!+k-1$ balls numbered $1,2,…,n$. Unseen by the illusionist, the spectator arranges the balls into a sequence as he sees fit. The assistant studies the sequence, chooses some block of $k$ consecutive balls, and covers them under her scarf. Then the illusionist looks at the newly obscured sequence and guesses the precise order of the $k$ balls he does not see.

Devise a strategy for the illusionist and the assistant to follow so that the trick always works.

(The strategy needs to be constructed explicitly. For instance, it should be possible to implement the strategy, as described by the solver, in the form of a computer program that takes $k$ and the obscured sequence as input and then runs in time polynomial in $n$. A mere proof that an appropriate strategy exists does not qualify as a complete solution.)

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
2cdbc3de-a71f-5df7-b928-29f6f8f13e37
task_key
test--2cdbc3de-a71f-5df7-b928-29f6f8f13e37
task_revision_id
1
config / split
/ test

Official source

initial import