**Source:**Nick's Mathematical Puzzles

**Problem:**Let n be a positive integer, and let S

_{n}= {n

^{2}+ 1, n

^{2}+ 2, ... , (n + 1)

^{2}}. Find, in terms of n, the cardinality of the set of pairwise products of distinct elements of S

_{n}.

For example, S

_{2}= {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!

Should be (2n + 1)*n.

ReplyDeleteBecause

( 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

The answer is (2n+1)C2=(2n+1)n

ReplyDeleteProduct 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..

@Parakram:

ReplyDeleteThanks for the awesome solution.

@Unknown:

Thanks for the explanation.

This is an informal solution to what parakram gave:

ReplyDeleteIf 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.