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}$

Answer: D

Concepts:modular arithmetic floor and ceiling functions basic probability

Difficulty rating: 2650

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$ and $n=q_1k+r_1,$ choosing both remainders in $[-(k-1)/2,(k-1)/2].$ If $r\ge0,$ no carry occurs precisely when $r-(k-1)/2\le r_1\le(k-1)/2;$ this gives $k-r$ residue classes. The case $r<0$ similarly gives $k+r$ classes. Hence in both cases $P(k)=1-\dfrac{|r|}{k}.$

To minimize $P(k)$ we maximize $|r|/k.$ If $r=(k-1)/2,$ then $201=k(2q+1),$ and the largest possible $k\le99$ is the divisor $67$ of $201.$ If $r=-(k-1)/2,$ then $199=k(2q-1);$ because $199$ is prime, only $k=1$ is possible. In every remaining case $|r|\le(k-3)/2,$ so $\begin{aligned} P(k)&\ge\dfrac12+\dfrac{3}{2k} \\ &\ge\dfrac12+\dfrac{3}{198} \\ &>\dfrac{34}{67}. \end{aligned}$ For $k=67,$ $P(67)=\dfrac12+\dfrac{1}{2\cdot67}=\dfrac{34}{67}.$

Thus, the correct answer is D.

2011 AMC 12B Problem 25

Answer: D

Difficulty rating: 2650

Solution:

Problem 25 in Other Years