0%

Problem 624


Problem 624


Two heads are better than one

An unbiased coin is tossed repeatedly until two consecutive heads are obtained. Suppose these occur on the $(M−1)$ th and $M$th toss.
Let $P(n)$ be the probability that $M$ is divisible by $n$. For example, the outcomes HH, HTHH, and THTTHH all count towards $P(2)$, but THH and HTTHH do not.

You are given that $P(2)=\frac{3}{5}$ and $P(3)=\frac{9}{31}$. Indeed, it can be shown that $P(n)$ is always a rational number.

For a prime $p$ and a fully reduced fraction $\frac{a}{b}$, define $Q(\frac{a}{b},p)$ to be the smallest positive $q$ for which $a\equiv bq\pmod p$.
For example $Q(P(2),109)=Q(\frac{3}{5},109)=66$, because $5\cdot66=330\equiv 3\pmod{109}$ and $66$ is the smallest positive such number.
Similarly $Q(P(3),109)=46$.

Find $Q(P(10^{18}),1\ 000\ 000\ 009)$.


一个不少,两个正好

不断抛掷一枚标准硬币,直到连续两次抛出正面,记此时已经抛掷的次数为$M$。
令$P(n)$表示$M$被$n$整除的概率。比方说,在计算$P(2)$时,如“正正”、“正反正正”或是“反正反反正正”这样的抛掷结果都要算入,而“反正正”或“正反反正正”就不算。

已知$P(2)=\frac 3 5$ 和 $P(3)=\frac{9}{31}$。实际上,可以证明$P(n)$总是有理数。

对于素数$p$和最简分数$\frac a b$,记 $Q(\frac{a}{b},p)$ 为满足$a\equiv bq\pmod p$ 的最小正整数$q$。
例如,$Q(P(2),109)=Q(\frac{3}{5},109)=66$, 这是因为$5\cdot66=330\equiv 3 \pmod{109}$且$66$是满足上式的最小正整数;同理可得$Q(P(3),109)=46$。

求$Q(P(10^{18}),1\ 000\ 000\ 009)$。

(注:标题为我国1971年“四五计划”时期提出的计生政策口号)