benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / You have to organize a fair procedure to randomly select someone from n people so that every one of them would be chosen with the probability (1)/(n). You are allowed to choose two…

Problem

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

problem

You have to organize a fair procedure to randomly select someone from n n people so that every one of them would be chosen with the probability 1n \frac{1}{n}. You are allowed to choose two real numbers 0<p1<1 0<p_1<1 and 0<p2<1 0<p_2<1 and order two coins which satisfy the following requirement: the probability of tossing "heads" on the first coin p1 p_1 and the probability of tossing "heads" on the second coin is p2 p_2. Before starting the procedure, you are supposed to announce an upper bound on the total number of times that the two coins are going to be flipped altogether. Describe a procedure that achieves this goal under the given conditions.
Plain-text mathematical notation (without MathML)
You have to organize a fair procedure to randomly select someone  from n people  so that every one of them would be chosen with the probability (1)/(n). You are allowed to choose two real numbers 0<p₁<1 and 0<p₂<1 and order two coins which satisfy the following requirement: the probability of tossing "heads" on the first coin p₁ and the probability of tossing "heads" on the second coin is p₂. Before starting the procedure, you are supposed to announce an upper bound on the total number of times that the two coins are going to be flipped altogether. Describe a procedure that achieves this goal under the given conditions.
Original LaTeX notation
You have to organize a fair procedure to randomly select someone  from $ n$ people  so that every one of them would be chosen with the probability $ \frac{1}{n}$. You are allowed to choose two real numbers $ 0<p_1<1$ and $ 0<p_2<1$ and order two coins which satisfy the following requirement: the probability of tossing "heads" on the first coin $ p_1$ and the probability of tossing "heads" on the second coin is $ p_2$. Before starting the procedure, you are supposed to announce an upper bound on the total number of times that the two coins are going to be flipped altogether. Describe a procedure that achieves this goal under the given conditions.

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
34652d91-dbd5-56a2-8c15-40ad0377f74a
task_key
test--34652d91-dbd5-56a2-8c15-40ad0377f74a
task_revision_id
1
config / split
/ test

Official source

initial import