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

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

##### Carpe noctum
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

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

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.

Replies
42
Views
8K
Replies
7
Views
3K
Replies
2
Views
70K
Replies
0
Views
3K
Replies
8
Views
2K