HMMT 二月 2016 · COMB 赛 · 第 3 题

HMMT February 2016 — COMB Round — Problem 3

Find the number of ordered pairs of integers ( a, b ) such that a, b are divisors of 720 but ab is not.

解析

Find the number of ordered pairs of integers ( a, b ) such that a, b are divisors of 720 but ab is not. Proposed by: Casey Fu Answer: 2520 4 2 First consider the case a, b > 0. We have 720 = 2 · 3 · 5, so the number of divisors of 720 is 5 ∗ 3 ∗ 2 = 30. We consider the number of ways to select an ordered pair ( a, b ) such that a, b, ab all divide 720. Using the balls and urns method on each of the prime factors, we find the number of ways to distribute the ( ) ( ) ( ) 6 4 3 factors of 2 across a and b is , the factors of 3 is , the factors of 5 is . So the total number of 2 2 2 ways to select ( a, b ) with a, b, ab all dividing 720 is 15 ∗ 6 ∗ 3 = 270. The number of ways to select any ( a, b ) with a and b dividing 720 is 30 ∗ 30 = 900, so there are 900 − 270 = 630 ways to select a and b such that a, b divide 720 but ab doesn’t. Now, each a, b > 0 corresponds to four solutions ( ± a, ± b ) giving the final answer of 2520. (Note that ab 6 = 0.)