Problem 26 · 2013 Math Kangaroo
Stretch
Number Theory
divisibilitycareful-counting
Using the numbers 1, 2, 3, …, 22, eleven fractions \(\frac{a}{b}\) are formed where each number is used exactly once. What is the maximum number of these fractions that can have whole-number values?
Show answer
Answer: B — 10
Show hints
Hint 1 of 2
A fraction is a whole number when the numerator is a multiple of the denominator; pair the numbers 1–22 to make as many such pairs as possible.
Still stuck? Show hint 2 →
Hint 2 of 2
Big primes like 13, 17, 19 are hard to use as denominators — one pair is forced to be non-integer.
Show solution
Approach: pair numbers so one divides the other, maximising integer pairs
- A fraction \(\frac{a}{b}\) is a whole number when \(b\) divides \(a\), so pair each number with one it divides into.
- The large primes 13, 17 and 19 have no other multiple in 1–22, so each can only sit on top of 1 to give an integer — but there is just one number 1, so at least two of them are forced into a non-integer fraction.
- Matching the rest greedily (e.g. \(\frac{22}{11}, \frac{20}{10}, \frac{18}{9}, \dots\)) lets 10 fractions come out whole while one stays non-integer.
- So the maximum is 10.
Mark:
· log in to save