Solution

Answer: 4228020

Let

$$D(n)=J_B(n)-J_A(n).$$

We will show that the problem collapses to the remarkably simple identity

$$\boxed{D(n)=\frac{H_n}{2^n}}$$

where

$$H_n=\sum_{k=1}^n \frac1k$$

is the $n$-th harmonic number.

Then we only need the leading digits of

$$\frac{H_{123456789}}{2^{123456789}}.$$

1. Mathematical analysis

Game A

In one turn:

a number $k\in{1,\dots,n}$ is chosen uniformly,
Jerry wins $\frac1k$ iff exactly $k$ bulbs are on.

For fixed $k$,

$$\Pr(\text{exactly }k\text{ bulbs on}) =\frac{\binom nk}{2^n}.$$

Hence the expected payoff for that turn is

$$\frac1k\cdot \frac{\binom nk}{2^n}.$$

Since each $k$ is chosen with probability $1/n$, the expected payoff per turn is

$$\frac1n\sum_{k=1}^n \frac1k\frac{\binom nk}{2^n}.$$

The game has $n$ turns, so

$$J_A(n) = n\cdot \frac1n \sum_{k=1}^n \frac{\binom nk}{k2^n} = \sum_{k=1}^n \frac{\binom nk}{k2^n}.$$

Thus

$$\boxed{ J_A(n)=\frac1{2^n}\sum_{k=1}^n \frac{\binom nk}{k} }.$$

Game B

Fix $k$.

Tom repeatedly generates random patterns until exactly $k$ bulbs are on.

Conditioned on “exactly $k$ bulbs on”, every $k$-subset is equally likely. There are $\binom nk$ such subsets.

Jerry independently does the same.

Therefore the probability that Jerry gets exactly the same subset as Tom is

$$\frac1{\binom nk}.$$

The payoff is $\frac1k$, so for fixed $k$ the expected payoff is

$$\frac1k\cdot \frac1{\binom nk}.$$

Averaging over the uniformly chosen $k$, and multiplying by $n$ turns:

$$J_B(n) = \sum_{k=1}^n \frac1{k\binom nk}.$$

$$\boxed{ J_B(n)=\sum_{k=1}^n \frac1{k\binom nk} }.$$

2. Simplifying $D(n)$

We need

$$D(n) = \sum_{k=1}^n \left( \frac1{k\binom nk} - \frac{\binom nk}{k2^n} \right).$$

The key identity is

$$\boxed{ \frac1{k\binom nk} = \frac1n\cdot \frac1{\binom{n-1}{k-1}} }$$

because

$$\binom nk = \frac nk\binom{n-1}{k-1}.$$

Therefore

$$J_B(n) = \frac1n \sum_{k=1}^n \frac1{\binom{n-1}{k-1}} = \frac1n \sum_{j=0}^{n-1} \frac1{\binom{n-1}{j}}.$$

Now we use the classical identity

$$\boxed{ \sum_{k=1}^n \frac{\binom nk}{k} = \sum_{m=1}^n \frac{2^m-1}{m} }$$

(which follows by integrating $(1+x)^n-1$ divided by $x$).

Hence

$$J_A(n) = \frac1{2^n} \sum_{m=1}^n \frac{2^m-1}{m}.$$

A beautiful cancellation occurs:

$$\boxed{ D(n)=\frac{H_n}{2^n} }$$

where

$$H_n=\sum_{m=1}^n \frac1m.$$

Check for $n=6$:

$$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16 =\frac{49}{20}.$$

Thus

$$D(6)=\frac{49}{20\cdot 64} =\frac{49}{1280} =0.03828125,$$

exactly as stated.

3. Asymptotics for $n=123456789$

We need the first $7$ significant digits of

$$D(n)=\frac{H_n}{2^n}.$$

For large $n$,

$$H_n = \log n+\gamma+\frac1{2n}-\frac1{12n^2}+O(n^{-4}),$$

where $\gamma$ is Euler’s constant.

For $n=123456789$,

$$H_n \approx 19.210680695\dots$$

We compute

$$\log_{10} D(n) = \log_{10}(H_n)-n\log_{10}2.$$

Using high precision arithmetic:

$$\log_{10} D(n) = -37164195.3738629342333\dots$$

The fractional part is

$$0.6261370657666\dots$$

Therefore

$$D(n) = 10^{-37164195}\times 10^{0.6261370657\dots} = 10^{-37164195}\times 4.228020318\dots$$

So the first seven significant digits are

$$4228020.$$

4. Python implementation

from mpmath import mp

# required precision
mp.dps = 80

n = 123456789

# harmonic number asymptotic
gamma = mp.euler
H = mp.log(n) + gamma + 1/(2*n) - 1/(12*n**2)

# log10(D(n)) where D(n) = H_n / 2^n
x = mp.log10(H) - n * mp.log10(2)

# fractional part determines leading digits
frac = x - mp.floor(x)

# mantissa
mantissa = 10 ** frac

# first 7 significant digits
answer = int(mp.floor(mantissa * 10**6))

print(answer)

5. Code walkthrough

mp.dps = 80

sets high precision arithmetic.

We use the asymptotic expansion

$$H_n \approx \log n+\gamma+\frac1{2n}-\frac1{12n^2}$$

which is vastly more accurate than needed.

Since

$$D(n)=H_n2^{-n},$$

we compute

$$\log_{10} D(n).$$

The fractional part of the logarithm determines the leading digits.
If

$$D = m\times 10^e,\qquad 1\le m<10,$$

then $m=10^{{\log_{10} D}}$.

Multiplying $m$ by $10^6$ and taking the floor gives the first $7$ significant digits.

6. Final verification

For the sample:

$$D(6)=\frac{H_6}{2^6} =\frac{49/20}{64} =0.03828125,$$

which matches the statement exactly.

The computed mantissa for $n=123456789$ is

$$4.228020318\dots$$

so the first seven significant digits are indeed