Can you pose an hard question about generating random numbers? I mean imagine that I…
- User
Can you pose an hard question about generating random numbers? I mean imagine that I pose this to a person that has some tools (like dice, paper and so on)
- Assistant
🎲 HARD RANDOM‑NUMBER CHALLENGE 🎲
You have nothing but
• an unlimited supply of perfectly fair six‑sided dice,
• a pencil, and
• a blank sheet of paper for keeping notes.Design a procedure that must eventually halt and output a single integer, and it must satisfy the following three requirements:
-
Uniformity
The output has to be an integer from 0 to 100 inclusive (that’s 101 possibilities), each occurring with probability exactly 1/101. -
Efficiency
Your goal is to minimise the expected number of die rolls.
a) Describe your algorithm in clear, step‑by‑step form (pseudo‑code is fine).
b) Compute the exact expected number of rolls your algorithm needs. -
Optimality Proof
Prove that no possible algorithm that uses only fair six‑sided dice can have a smaller expected roll count than the one you presented (a rigorous lower‑bound argument to within, say, 0.01 rolls is acceptable).
Good luck!
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.