Problem J
Binary Choosing
Two years have passed, and Binary Town is having its next round of biennial elections.1 The “binary voting” system from last time confused a lot of people, so the citizens have decided to not vote at all this year and instead choose one citizen uniformly at random to become the town’s next mayor.
Because of a lack of trust from last time, though, Binary Town’s citizens have only found a single source of randomness that everyone agrees on: a single perfectly balanced coin that shows $0$ on one side and $1$ on the other. The town council will repeatedly flip this coin where everyone can see it until they manage to find one random citizen to serve as the next mayor.
The exact process will go as follows: first, the town will conduct a census and assign every citizen a unique number from $0$ to $c - 1$, where $c$ equals the number of citizens. Next, the council will flip up to $\lceil \log _2 c \rceil $ coins and read the resulting bit string as a binary number. If they read a binary number at least as big as $c$, then this doesn’t represent a valid citizen’s number and so they start again in a new round. Since the citizens have no time to waste, they will start a new round as soon as it becomes clear that their bit string corresponds to too big a number.
For example, if the census counts $c = 5$ citizens, they will flip up to $\lceil \log _2 5 \rceil = 3$ coins to try to generate a binary number from $000_2 = 0$ to $100_2 = 4 = c-1$. If they get the binary number $101_2 = 5$ they will have to restart, and if their bit string begins with two $1$’s in a row they will also immediately restart, since $110_2 = 6$ and $111_2 = 7$ both exceed the highest number corresponding to a citizen.
Binary Town hasn’t conducted its census yet but would like to know how many expected coin flips they will have to make before choosing their new mayor. In the case of $c = 5$, they have a $5/8$ chance of flipping $3$ coins and choosing the new mayor without having to start a new round, a $1/8$ chance of flipping $3$ coins and starting a new round (if they get the bit string $101$), and a $1/4$ chance of flipping $2$ coins and starting a new round early (if they get a bit string starting with $11$). The expected number of total coin flips then equals the expected number of coin flips in a single round ($3 \cdot 3/4 + 2 \cdot 1/4 = 11/4 = 2.75$ expected coin flips in our example) times the expected number of rounds (this equals the inverse of the probability of successfully choosing a neighbour, or $1/(5/8) = 8/5 = 1.6$ expected rounds in our example, making the total expected coin flips across all rounds $2.75 \cdot 1.6 = 4.4$).2
Input
Input consists of a single integer $1 \leq c \leq 10^9$ on a single line, the number of citizens (Binary Town really should conduct censuses more often given how much uncertainty they have about their population).
Output
Output the expected number of coin flips needed to choose Binary Town’s next mayor as a real number. Answers will be accepted up to a relative or absolute error of $10^{-3}$. (If you submit answer $a$ and the correct answer equals $b$, the judge will accept your solution if $\min \left(\frac{|a-b|}{b}, |a-b|\right) \leq 10^{-3}$.)
| Sample Input 1 | Sample Output 1 |
|---|---|
5 |
4.4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2022 |
11.0969337289812 |
Footnotes
- Rather conveniently, the problem author wrote this problem on 2022-02-22.
- We can equivalently calculate the expected number of coin flips by adding the number of coin flips in the final round, always $\lceil \log _2 c \rceil $, to the expected number of coin flips given that a round ended with a restart multiplied by the expected number of restarts. With $c=5$, this works out to $3 + (2 + 1/3) \cdot 0.6 = 4.4$.
