benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / For an even integer positive integer n Kevin has a tape of length 4n with marks at −2n,−2n+1,…,2n−1,2n. He then randomly picks n points in the set −n,−n+1,−n+2,…,n−1,n, and places …

Problem

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

problem

For an even integer positive integer nn Kevin has a tape of length 4n4 n with marks at −2n,−2n+1,…,2n−1,2n-2 n,-2 n+1, \ldots, 2 n-1,2 n. He then randomly picks nn points in the set −n,−n+1,−n+2,…,n−1,n-n,-n+1,-n+2, \ldots, n-1, n, and places a stone on each of these points. We call a stone 'stuck' if it is on 2n2 n or −2n-2 n, or either all the points to the right, or all the points to the left, all contain stones. Then, every minute, Kevin shifts the unstuck stones in the following manner: He picks an unstuck stone uniformly at random and then flips a fair coin. If the coin came up heads, he then moves that stone and every stone in the largest contiguous set containing that stone one point to the left. If the coin came up tails, he moves every stone in that set one point right instead. He repeats until all the stones are stuck. Let pkp_{k} be the probability that at the end of the process there are exactly kk stones in the right half. Evaluate pn−1−pn−2+pn−3−…+p3−p2+p1pn−1+pn−2+pn−3+…+p3+p2+p1\frac{p_{n-1}-p_{n-2}+p_{n-3}-\ldots+p_{3}-p_{2}+p_{1}}{p_{n-1}+p_{n-2}+p_{n-3}+\ldots+p_{3}+p_{2}+p_{1}} in terms of nn.
Plain-text mathematical notation (without MathML)
For an even integer positive integer n Kevin has a tape of length 4n with marks at −2n,−2n+1,…,2n−1,2n. He then randomly picks n points in the set −n,−n+1,−n+2,…,n−1,n, and places a stone on each of these points. We call a stone 'stuck' if it is on 2n or −2n, or either all the points to the right, or all the points to the left, all contain stones. Then, every minute, Kevin shifts the unstuck stones in the following manner: He picks an unstuck stone uniformly at random and then flips a fair coin. If the coin came up heads, he then moves that stone and every stone in the largest contiguous set containing that stone one point to the left. If the coin came up tails, he moves every stone in that set one point right instead. He repeats until all the stones are stuck. Let p_(k) be the probability that at the end of the process there are exactly k stones in the right half. Evaluate (p_(n−1)−p_(n−2)+p_(n−3)−…+p₃−p₂+p₁)/(p_(n−1)+p_(n−2)+p_(n−3)+…+p₃+p₂+p₁) in terms of n.
Original LaTeX notation
For an even integer positive integer $n$ Kevin has a tape of length $4 n$ with marks at $-2 n,-2 n+1, \ldots, 2 n-1,2 n$. He then randomly picks $n$ points in the set $-n,-n+1,-n+2, \ldots, n-1, n$, and places a stone on each of these points. We call a stone 'stuck' if it is on $2 n$ or $-2 n$, or either all the points to the right, or all the points to the left, all contain stones. Then, every minute, Kevin shifts the unstuck stones in the following manner: He picks an unstuck stone uniformly at random and then flips a fair coin. If the coin came up heads, he then moves that stone and every stone in the largest contiguous set containing that stone one point to the left. If the coin came up tails, he moves every stone in that set one point right instead. He repeats until all the stones are stuck. Let $p_{k}$ be the probability that at the end of the process there are exactly $k$ stones in the right half. Evaluate $$\frac{p_{n-1}-p_{n-2}+p_{n-3}-\ldots+p_{3}-p_{2}+p_{1}}{p_{n-1}+p_{n-2}+p_{n-3}+\ldots+p_{3}+p_{2}+p_{1}}$$ in terms of $n$.

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
f8352230-6268-5615-93fe-8786e7578ff9
task_key
test--f8352230-6268-5615-93fe-8786e7578ff9
task_revision_id
1
config / split
/ test

Official source

initial import