Four Numbers, Six Differences, GCD of the Products

Pick any 4 positive integers. Form 6 differences always subtracting a smaller number from a larger one. Multiply all the differences. Consider a collection of all such products for various choices of the initial four numbers. Find the largest common divisor of the products in the collection.

Solution

Credits: This is one of the Problems to Ponder offered by NCTM President Mike Shaughnessy.


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

Pick any 4 distinct positive integers. Form 6 differences always subtracting a smaller number from a larger one. Multiply all the differences. Consider a collection of all such products for various choices of the initial four numbers. Find the largest common divisor of the products in the collection.

Solution

All such products are divisible by 12. There is no greater number that divides all the products.

The letter assertion is immediate because, for the 4 numbers 1, 2, 3, 4, the product is exactly 12.

For the first claim let's first show that every product is divisible by 3. Sort the numbers in the ascending order:

a < b < c < d

and make them as the nodes of a digraph, with arrow pointing from a smaller number to a larger one.

We also associate the edge with the difference of the numbers in the nodes it joins. This leads to a representation of the directed edges as vectors. For example, since (b - a) + (c - b) = c - a, which provides an interpretation for the addition of edges/vectors.

Assume none of the difference is 0 modulo 3. There are three vectors emanating from node a. By the pigeonhole principle, two of them correspond to the same residue modulo 3. The vector joining the end nodes of these vectors is necessarily associated with the difference equal 0 modulo 3. It follows that 3 is a factor of the product of the six differences.

Now consider the differences modulo 2. If there are two zero (modulo 2) vectors emanating from a, we are done. If there is only one, then the difference of the other 2 is 0, and again we have two factors equal to 2. If none of the vectors emanating from a is zero, two of their differences equal 0 (mod 2), again supplying at least two factors equal to 2.

Note: the problem admits a generalization on any number of integers.


Related material
Read more...

  • 17 rooks on a Chessboard
  • Chinese Remainder Theorem
  • Pigeonhole in a Chessboard
  • Pigeonhole in Concurrent Cuts
  • Monochromatic Rectangle in a 2-coloring of the Plane
  • Polynomial and Integer Division
  • Power of three that ends with 001
  • Pigeonhole Principle (subsets)
  • Pigeonhole in Integer Differences

    • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71945687