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