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