Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jul 16, 2012

Pairwise Product Set Cardinality

Source: Nick's Mathematical Puzzles

Problem:Let n be a positive integer, and let Sn = {n2 + 1, n2 + 2, ... , (n + 1)2}.  Find, in terms of n, the cardinality of the set of pairwise products of distinct elements of Sn.
For example, S2 = {5, 6, 7, 8, 9},
5 × 6 = 6 × 5 = 30,
5 × 7 = 7 × 5 = 35,
5 × 8 = 8 × 5 = 40,
5 × 9 = 9 × 5 = 45,
6 × 7 = 7 × 6 = 42,
6 × 8 = 8 × 6 = 48,
6 × 9 = 9 × 6 = 54,
7 × 8 = 8 × 7 = 56,
7 × 9 = 9 × 7 = 63,
8 × 9 = 9 × 8 = 72,
and the required cardinality is 10.

Update (Sept 12, 2012):
Solution posted by Parakram Majumdar (CSE IITB Alumnus, Morgan Stanley Strats and Modeling Analyst) - Detailed explanation of the solution by unknown in comments!

4 comments:

  1. Should be (2n + 1)*n.
    Because
    ( n^2 + 1 ) * x > ( n + 1 )^2 \forall x \geq 2, n \geq 2

    Thus you cannot find a, b, c, d \in S_n such that a*b = c*d and a \neq c, d

    ReplyDelete
  2. The answer is (2n+1)C2=(2n+1)n
    Product of no two numbers in S_n is same

    Say there exist 1 <= a,b,p,q < 2n+1 such that
    (n^2+a)(n^2+b) = (n^2+p)(n^2+q)
    n^2 = (ab-pq)/(p+q-a-b)
    as n^2 was positive, assume p+q > a+b and ab > pq

    (ab-pq)/(p+q-a-b) <= (((a+b)^2)/4 - pq)/(p+q-a-b) < (((p+q)^2)/4 - pq)/(p+q-a-b)
    = ((p-q)^2)/4(p+q-a-b)
    <= 4n^2/4(p+q-a-b) // As p-q can take a max of 2n
    =n^2/(p+q-a-b)
    <=n^2
    So no such a,b,p,q exist.

    Hope its correct. This is too lengthy/inelegant compared to prev. solution. But just wanted to share it..

    ReplyDelete
  3. @Parakram:
    Thanks for the awesome solution.

    @Unknown:
    Thanks for the explanation.

    ReplyDelete
  4. This is an informal solution to what parakram gave:

    If a, b are two distinct elements in Sn, then to get the same product as a*b, a prime factor of at least a value of 2 should be transferred across them.
    But 2(n^2 + 1) > (n+1)^2 for n > 1, hence every such transfer results in elements outside of Sn.
    Hence, it is simply (2n + 1) choose 2 which is true for n =1 as well.

    ReplyDelete