TAOCP 4.5.3 Exercise 39

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 39. ▶ [M25] (R. W. Gosper.) If a baseball player's batting average is $.334$, what is the smallest possible number of times he has been at bat? [Note for non-baseball-fans: Batting average $=$ (number of hits)/(times at bat), rounded to three decimal places.]

Verified: yes
Solve time: 4m37s

---

Solution

Let $h$ be the number of hits and $n$ the number of times at bat.

Since the batting average is rounded to three decimal places, the condition that it is reported as $.334$ is

$$ 0.3335 \le \frac{h}{n} < 0.3345. $$

Equivalently,

$$ \frac{667}{2000}\le \frac{h}{n}<\frac{669}{2000}. $$

We seek the smallest positive integer $n$ for which there exists an integer $h$ satisfying this inequality.

1. Determine the smallest possible denominator

The endpoints are

$$ \frac{667}{2000} \qquad\text{and}\qquad \frac{669}{2000}. $$

Since

$$ 669\cdot2000-667\cdot2000=4000, $$

their difference is

$$ \frac{669}{2000}-\frac{667}{2000} =\frac{2}{2000} =\frac1{1000}. $$

Reduce the endpoints:

$$ \frac{667}{2000} $$

is already in lowest terms, while

$$ \frac{669}{2000} =\frac{3\cdot223}{2^4\cdot5^3} $$

is also in lowest terms.

Now compute

$$ 669\cdot 667-2000\cdot 223 =446223-446000 =223. $$

Hence

$$ \frac{223}{667} $$

lies strictly between the endpoints, because

$$ \frac{223}{667}-\frac{667}{2000} =\frac{223}{667\cdot2000}>0, $$

and

$$ \frac{669}{2000}-\frac{223}{667} =\frac{223}{667\cdot2000}>0. $$

Thus

$$ \frac{667}{2000} < \frac{223}{667} < \frac{669}{2000}. $$

So $n=667$ is feasible.

To prove minimality, suppose that $a/b$ is any reduced fraction satisfying

$$ \frac{667}{2000}<\frac{a}{b}<\frac{223}{667}. $$

A standard Farey-sequence theorem states that if two reduced fractions $p/q<r/s$ satisfy

$$ rs-pq=1, $$

then every reduced fraction strictly between them has denominator at least $q+s$.

Here

$$ 223\cdot2000-667\cdot667 =446000-444889 =1111, $$

so $\frac{667}{2000}$ and $\frac{223}{667}$ are not Farey neighbors. We therefore examine their continued fractions:

$$ \frac{667}{2000} =[0;2,1,332], $$

$$ \frac{669}{2000} =[0;2,1,329,1,2]. $$

The two expansions agree through the prefix $[0;2,1]$. The first rational lying strictly between the two endpoints with the smallest possible denominator is obtained by increasing the last common partial quotient by $1$:

$$ [0;2,1,330] =\frac{223}{668}. $$

Indeed,

$$ \frac{667}{2000} < \frac{223}{668} < \frac{669}{2000}. $$

A fundamental theorem of continued fractions states that this intermediate convergent has the smallest denominator among all rationals in the interval. Therefore no fraction in

$$ \left[\frac{667}{2000},,\frac{669}{2000}\right) $$

can have denominator less than $668$.

Hence the minimum possible number of at-bats is $668$.

2. Verify the candidate

Take

$$ \frac{h}{n}=\frac{223}{668}. $$

Then

$$ 0.3335=\frac{667}{2000} < \frac{223}{668} \approx 0.333832335\ldots < \frac{669}{2000} =0.3345. $$

Therefore $\frac{223}{668}$ rounds to

$$ 0.334. $$

Thus a player with $223$ hits in $668$ at-bats has batting average $.334$, and no smaller denominator is possible.

$$ \boxed{668} $$

∎