Question

For every $m$ and $k$ integers with $k$ odd, denote by $\left[\dfrac{m}{k}\right]$ the integer closest to $\dfrac{m}{k}.$ For every odd integer $k,$ let $P(k)$ be the probability that $\left[\dfrac{n}{k}\right]+\left[\dfrac{100-n}{k}\right]=\left[\dfrac{100}{k}\right]$ for an integer $n$ randomly chosen from the interval $1\le n\le99!.$ What is the minimum possible value of $P(k)$ over the odd integers $k$ in the interval $1\le k\le99?$

$\dfrac{1}{2}$

$\dfrac{50}{99}$

$\dfrac{44}{87}$

$\dfrac{34}{67}$

$\dfrac{7}{13}$

Solution:

Because $\left[\dfrac{n+mk}{k}\right]=\left[\dfrac{n}{k}\right]+m,$ whether $n$ satisfies the identity depends only on $n\bmod k.$ Since $k\mid99!$ for $1\le k\le99,$ every residue class is equally likely.

Write $100=qk+r$ with $|r|\le\dfrac{k-1}{2}.$ Analyzing the carry in $[\,(100-n)/k\,]$ shows the identity holds precisely for the residues in an interval of the appropriate length, giving $P(k)=1-\dfrac{|r|}{k}.$

To minimize $P(k)$ we maximize $\dfrac{|r|}{k}.$ Taking $r=\dfrac{k-1}{2}$ gives $201=k(2q+1),$ and the largest odd $k\le99$ dividing $201=3\cdot67$ is $k=67.$ Then $P(67)=\dfrac12+\dfrac{1}{2\cdot67}=\dfrac{34}{67},$ which is smaller than the values from all other cases.

Thus, the correct answer is D.

2011 AMC 12B Problem 25

Solution:

Problem 25 in Other Years