Skip to main content.

Solution to puzzle 110: Pairwise products

Skip restatement of puzzle.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.


After some experimentation, we may conjecture that, disregarding order, all pairwise products of distinct elements of Sn are distinct.  A proof follows.

Let a, b, c, d be integers such that n2 < a < b < c < d, and ad = bc.  If we can show that d > (n + 1)2, the result will follow.

Consider (d − a)2 = (d + a)2 − 4ad
  = (d + a)2 − 4bc
  > (d + a)2 − (b + c)2.  (Since (b − c)2 > 0 implies b2 + c2 > 2bc.)
  = (d + a + b + c)(d + a − b − c)
  > 4n2(d + a − b − c)(1)

Considering d/c = b/a, clearly d − c > b − a, in which case d + a > b + c.
(More formally, ad = bc implies a(d − c) = (b − a)c implies a(d − c) > (b − a)a implies d − c > b − a.)
Hence d + a − b − c greater than or equal to 1.

From (1), (d − a)2 > 4n2, and so d − a > 2n.
Hence d > (n2 + 1) + 2n, from which d > (n + 1)2.

It follows that, disregarding order, all pairwise products of distinct elements of Sn are distinct.
Disregarding order, we may choose two distinct elements in C(2n+1, 2) = n(2n + 1) ways.

Therefore the cardinality of the set of pairwise products of distinct elements of Sn is n(2n + 1).

Source: Inspired by problem 9 in Conjecture and Proof, Sheet 6. (Document since taken down.)

Back to top