Maths: Probablity Problem

Two distinct numbers x and y are chosen at random from the first 30 natural numbers. What is the probability that a2 - b2 is divisible by 3?

Well, instead of giving my clumsy solution, I'd provide the one from Karthik.

Hint: 3|(a2 - b2)
=> 3|(a - b)(a + b)
=> 3|(a - b) or 3|(a + b) or both

Find the doublets (a, b) such that either a - b or a + b or both are divisible by 3.

Class 1: {1, 4, 7, ... }, {2, 5, 8, ... }, {3, 6, 9, ... }. Each set has 10 numbers. Total number of such combinations is 3 * (10 * 9) / 2 = 135

Class 2: {1, (2, 5, 8, ..)}, {2, (4, 7, ...)}, ...

Now look at the three sets {1, 2, ... }, {2, 4, ... }, {3, 6, ... }. In these sets, we have covered all numbers in range [1, 30]. Forgetting about the third set, to find two numbers such that their sum is divisible by 3, all we need to do it pick one number from the first set and another from the second.

Total number of combinations = 10 * 10 = 100

Class 3: The combinations of {3, 6, 9, ... } will be repeated in both. So, we need to count them only once. We have already counted in Class 1, so we'll not count again.

Total number of picking two numbers is ³⁰C₂ = 435

Probability =

(135 + 100) / 435
  = 235/435
  = 470/870
  = 47/87