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