AMC 10 · 2011 · #25

Grade 7 probabilitynumber-theory

Archetype Modular Cycle Frequency Count └ Sub-archetype Floor Count Across Residue Bins

modular-arithmeticfloor-functionprobability-basicoptimization casework ↑ Prerequisites: modular-arithmetic

📏 Long solution 💡 5 insights

Problem

A rounding identity must hold for a random pick, and the chance depends on an odd divisor. Find the smallest chance.

Pick an answer.

(A)

$\frac{1}{2}$

(B)

$\frac{50}{99}$

(C)

$\frac{44}{87}$

(D)

$\frac{34}{67}$

(E)

$\frac{7}{13}$

How to solve

Strategy Organize Information in More Ways

Tool #15 (Organize Information in More Ways): rounding is hard to compute with, but the same information can be stored as a leftover instead. Writing m=k[m/k]+s(m), where s(m) is the remainder measured from the nearest multiple of k, turns the rounding equation into the exact statement s(n)+s(100-n)=s(100) with no rounding left in it. Tool #9 (Solve an Easier Related Problem): the range 1 ≤ n ≤ 99! is unusable directly, but the event only depends on n modulo k, so the question shrinks to counting good remainders among k of them. Tool #4 (Introduce a Variable): naming c=s(100) and h=(k-1)/2 turns the count into the length of an overlap of two intervals. Tool #14 (Extreme Principle): the question asks for a minimum, so I need a bound on P(k) and a k that sits exactly on it. Tool #7 (Identify Subproblems): the bound settles all small k at once but goes slack for large k, so those must be computed exactly in a separate case.

1STEP 1

Rounding never ties

An odd divisor makes a rounding tie impossible.

m/k=j+1/2 → 2m=k(2j+1), even = odd, impossible

2STEP 2

Only the remainder of n matters

Only the remainder of the pick matters.

[(n+k)/k]+[(100-(n+k))/k]=([n/k]+1)+([(100-n)/k]-1)

3STEP 3

Why the problem says 99!

The huge range makes every remainder equally likely.

k ∣ 99! → P(k)=(#{good remainder classes mod k})/k

4STEP 4

Store the remainder as a leftover

Storing a signed leftover replaces the rounding.

[m/k]=(m-s(m))/k, -h ≤ s(m) ≤ h, h=(k-1)/2

5STEP 5

The rounding disappears

The rounding then disappears from the identity.

(n-s(n))/k+(100-n-s(100-n))/k=(100-s(100))/k⇔ s(n)+s(100-n)=s(100)

6STEP 6

When the leftovers add exactly

What remains is one size condition.

equation holds⇔ |c-a| ≤ h⇔ |s(n)-s(100)| ≤ (k-1)/2

7STEP 7

Count the good remainders

Counting good remainders gives a clean formula.

P(k)=(k-|c|)/k=1-|c|/k, |c|=distance from 100 to the nearest multiple of k

8STEP 8

A floor, and when it is touched

That formula has a floor touched only rarely.

P(k) ≥ (k+1)/2k, with equality ⇔ k ∣ 199 or k ∣ 201=3 · 67 → k∈{1,3,67}

9STEP 9

Two cases finish the job

Two ranges are checked separately.

k ≤ 67: P(k) ≥ (k+1)/2k ≥ 34/67; 69 ≤ k ≤ 99: P(k)=(2k-100)/k ≥ 38/69 ＞ 34/67

10STEP 10

The minimum is reached at k = 67

The smallest is 34/67, choice (D).

min_k odd, 1 ≤ k ≤ 99 P(k)=P(67)=34/67 (D)

Answer

34/67

The formula P(k)=1-|c|/k passes independent spot checks. For k=1 nothing is ever rounded and n+(100-n)=100 always holds, and indeed |c|=0 gives P(1)=1. For k=99 the number 100 is only 1 away from the multiple 99, so P(99)=98/99, almost certain, which matches the fact that the equation fails only for a single remainder. For k=13 the nearest multiple is 104, at distance 4, giving P(13)=9/13, comfortably above 34/67. The answer choices themselves confirm the reading of the problem: 50/99,44/87,34/67,7/13 are exactly the floor (k+1)/2k evaluated at k=99,87,67,13, and 1/2 is the value that floor approaches but never reaches. Two of those floors are smaller than 34/67, which is precisely why stopping at the bound is not enough: at k=99 and k=87 the true probabilities are 98/99 and 74/87, nowhere near their floors, while k=67 is one of only three values of k whose floor is actually attained. That is what makes 34/67 the genuine minimum rather than merely the smallest bound.

💡Key takeaway

Rounding to the nearest multiple of k just throws away the leftover nearest zero, so the whole question collapses to one thing: how far is 100 from the closest multiple of k?

Rounding never ties
Only the remainder of n matters
Why the problem says 99!
Store the remainder as a leftover
The rounding disappears
When the leftovers add exactly
Count the good remainders
A floor, and when it is touched
Two cases finish the job
The minimum is reached at k = 67