2011 AMC 12B Problem 25

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 $99!$ is divisible by $k$ 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 $[-\frac{(k-1)}{2},\frac{k-1}{2}].$ If $r\ge0,$ no carry occurs precisely when $r-\frac{k-1}{2}\le r_1\le\frac{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=\frac{k-1}{2},$ then $201=k(2q+1),$ and the largest possible $k\le99$ is the divisor $67$ of $201.$ If $r=-\frac{(k-1)}{2},$ then $199=k(2q-1);$ because $199$ is prime, only $k=1$ is possible. In every remaining case $|r|\le\frac{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.