Problem:
For every m and k integers with k odd, denote by [kmβ] the integer closest to kmβ. For every odd integer k, let P(k) be the probability that
[knβ]+[k100βnβ]=[k100β]
for an integer n randomly chosen from the interval 1β€nβ€99 !. What is the minimum possible value of P(k) over the odd integers k in the interval 1β€kβ€99?
Answer Choices:
A. 21β
B. 9950β
C. 8744β
D. 6734β
E. 137β
Solution:
Let
100=qk+r, with q,rβZ and β£rβ£β€2kβ1β, and n=q1βk+r1β, with q1β,r1ββZ and β£r1ββ£β€2kβ1ββ
so that [k100β]=q and [knβ]=q1β. Note that [kn+mkβ]=[knβ]+m for every integer m. Thus n satisfies the required identity if and only if n+mk satisfies the identity for all integers m. Thus all members of a residue class modk either satisfy the required equality or not; moreover, k divides 99 ! for every 1β€kβ€99, so every residue class mod k in the interval 1β€nβ€99 ! has the same number of elements. Suppose rβ₯0. If r1ββ₯rβ2kβ1β, then
100βn=(qβq1β)k+(rβr1β)
where 0β€rβr1ββ€2kβ1β. Thus [k100βnβ]=qβq1β=[k100β]β[knβ]. Similarly, if r1β<rβ2kΛβ1β, then
100βn=(qβq1β+1)k+(rβr1ββk)
where β2kβ1ββ€rβr1ββkβ€β1. Thus [k100βnβ]=qβq1β+1>[k100β]β[knβ]. It follows that the only residue classes r1β that satisfy the identity are those in the interval rβ2kβ1ββ€r1ββ€2kβ1β. Thus for rβ₯0,
P(k)=k1β(2kβ1β+1β(rβ2kβ1β))=kkβrβ=1βkβ£rβ£β
Similarly, if r<0 then the identity is satisfied only by the residue classes r1β in the interval β2kβ1ββ€r1ββ€r+2kβ1β. Thus for r<0,
P(k)=k1β(r+2kβ1β+1β(β2kβ1β))=kk+rβ=1βkβ£rβ£β
To minimize P(k) in the range 1β€kβ€99, where k is odd, first suppose that r=2kβ1β. Note that P(k)=21β+2k1β,100=qk+2kβ1β, and so 201=k(2q+1).
The minimum of P(k) in this case is achieved by the largest possible k under this restriction. Because 201=3β
67, it follows that the largest factor k of 201 in the given range is k=67. In this case P(67)=21β+2β
671β=6734β. Second, suppose r=21βkβ. In this case P(k)=21β+2k1β and 199=k(2qβ1). Because 199 is prime, it follows that k=1 and P(k)=1>6734β. Finally, if β£rβ£β€2kβ3β, then
P(k)=1βkβ£rβ£β>1β2kkβ3β=21β+2k3ββ₯21β+2β
993β>21β+2β
671β=6734ββ
Therefore the minimum value of P(k) in the required range is 6734ββ.
The problems on this page are the property of the MAA's American Mathematics Competitions