Pairwise Product Set Cardinality

[pratikpoddar]

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.

I have not been able to solve it.

Apologies for not posting the problem here as could not resolve latex issues. Someone please post the problem here.

 

[Faisal]

n(2n+1)

 

[Faisal]

Correct me if I am wrong somewhere as this looks to be a very straightforward question. From n^2 + 1 to n^2 + 2n+1, there are 2n+1 terms. So the pairwise cardinality simply reduces to (2n+1)C2, which reduces to n(2n+1).

 

[koupparis]

I think there may be a problem with 2 sets of numbers giving the same product e.g. 3*4 = 2*6. If you can prove that this doesn't happen for large n then you have the correct solution. I'm not entirely convinced that it does happen though ...

 

[Faisal]

How about this:

Assume there are two sets of numbers giving the same products:
\((n^2+a_{1})(n^2+a_{2})=(n^2+b_{1})(n^2+b_{2})\)
Let \((n^2+a_{1})\) be the largest number in a given set, hence for equality, \((n^2+a_{2})\) is the smallest and \(\ (n^2+b_{1})\) & \((n^2+b_{2})\) lying in between. Hence, we have, a1>b1,b2>a2.

\(n^4 + n^2 (a_{1}+a_{2})+a_{1} a_{2} = n^4 + n^2 (b_{1}+b_{2})+b_{1} b_{2} = k (say) \)
Solving for \(n^2\), and noting that \(n^2\) has a unique value, we obtain

\((a_{1}+a_{2})^2 - 4(a_{1} a_{2}-k)=0\)
\((b_{1}+b_{2})^2 - 4(b_{1} b_{2}-k)=0\)

eliminating k , we obtain

\((a_{1}-a_{2})^2 = (b_{1} - b_{2})^2\) ,

which is contrary to our assumption as b1 &b2 lie between a1& a2 hence \((a_{1}-a_{2})^2 > (b_{1} - b_{2})^2\)

 

[pruse]

How about this:

Assume there are two sets of numbers giving the same products:
\((n^2+a_{1})(n^2+a_{2})=(n^2+b_{1})(n^2+b_{2})\)
Let \((n^2+a_{1})\) be the largest number in a given set, hence for equality, \((n^2+a_{2})\) is the smallest and \(\ (n^2+b_{1})\) & \((n^2+b_{2})\) lying in between. Hence, we have, a1>b1,b2>a2.

\(n^4 + n^2 (a_{1}+a_{2})+a_{1} a_{2} = n^4 + n^2 (b_{1}+b_{2})+b_{1} b_{2} = k (say) \)
Solving for \(n^2\), and noting that \(n^2\) has a unique value, we obtain

\((a_{1}+a_{2})^2 - 4(a_{1} a_{2}-k)=0\)
\((b_{1}+b_{2})^2 - 4(b_{1} b_{2}-k)=0\)

eliminating k , we obtain

\((a_{1}-a_{2})^2 = (b_{1} - b_{2})^2\) ,

which is contrary to our assumption as b1 &b2 lie between a1& a2 hence \((a_{1}-a_{2})^2 > (b_{1} - b_{2})^2\)

This is obviously wrong, since nowhere are you using the fact that a_1, a_2, b_1, b_2 are in the range [1,2n+1]...

 

[pruse]

Okay, here's a correct proof.

Let \(p < q < t < u\in \{n^2+1, ..., (n+1)^2\}\) such that \(pu = qt\). Note that \((u-p)^2 = (u+p)^2-4pu = (u+p)^2-4qt > (u+p)^2-(q+t)^2\), where the latter follows by the AM-GM inequality. Then \((u-p)^2>(u+p+q+t)(u+p-q-t)>4n^2(u+p-q-t)\). Note that since \(\frac{u}{t} = \frac{q}{p}\), we must have \(u-t>q-p\) (\(u, t\) are bigger, so to have the same ratio as \(p, q\), they must be spaced farther apart), so the RHS of the last inequality is in fact positive. Thus \((u-p)^2 > 4n^2\), from which \(u-p>2n\), contradicting the fact that \(u-p\leq (n+1)^2-(n^2+1)=2n\)

 

[tuanl]

Another solution:

Assume there exists 4 distinct numbers \(\in {n^2+1,...(n+1)^2}\) such that \((n^2+a_m)(n^2+a_n)=(n^2+a_t)(n^2+a_u)\) where \(a_m,a_n,a_t,a_u\in {1,2,...,2n+1}\) for every \(n\geq 1\). We have:
\(a_m+a_n=a_t+a_u\)
\(a_m*a_n=a_t*a_u\)

Thus, \(a_m^2+a_n^2=a_t^2+a_u^2\), which implies \(a_m-a_n=a_t-a_u\) (W.L.O.G, assume \(a_m>a_n, a_t>a_u\)). Therefore, \(a_m=a_t\), which implies \(a_n=a_u\)(contradiction since the 4 numbers must be distinct). We conclude that there doesn't exist such 4 distinct numbers(Q.E.D)

 

[pruse]

\(a_m+a_n=a_t+a_u\)
\(a_m*a_n=a_t*a_u\)

Can you justify that? (I don't think that's true.)

Also, like Faisal, you are not using the fact that \(1\leq a_i\leq 2n+1\), which is crucial. This means that the argument is probably flawed.

 

[tuanl]

Can you justify that? (I don't think that's true.)

Also, like Faisal, you are not using the fact that \(1\leq a_i\leq 2n+1\), which is crucial. This means that the argument is probably flawed.

You're correct. I just realize my argument is flawed since it only shows that there doesn't exist any 4 fixed numbers \(a_m, a_n,a_t,a_u\in {1,2,...,2n+1}\) such that \((n^2+a_n)(n^2+a_m)=(n^2+a_t)(n^2+a_u)\) for EVERY \(n\geq 1\). But \(a_m,a_n,a_t,a_u\) can vary depending on n.