7
$\begingroup$

From the 1991 Canada National Olympiad:

Can ten distinct numbers $a_1, a_2, b_1, b_2, b_3, c_1, c_2, d_1, d_2, d_3$ be chosen from $\{0, 1, 2, \dotsc, 14\}$ so that the $14$ differences $$ \begin{matrix} |a_1 − b_1| & |a_1 − b_2| & |a_1 − b_3| \\ |a_2 − b_1| & |a_2 − b_2| & |a_2 − b_3| \\ |c_1 − d_1| & |c_1 − d_2| & |c_1 − d_3| \\ |c_2 − d_1| & |c_2 − d_2| & |c_2 − d_3| \\ \end{matrix} \\ \begin{matrix} |a_1 − c_1| & |a_2 − c_2| \end{matrix} $$ are all distinct?

My observations so far:

  • There are $14$ differences, none of which can be zero. So the differences must comprise the set $\{1, 2, \dotsc , 14\}$.

  • The ten numbers must include both of $\{0, 14\}$ and at least one of $\{1, 13\}$.

  • Subsets $A, C$ are the most central, as they also have differences with each other. If trying to construct a positive example for the choice of ten numbers, an unwise choice of $a_1, a_2$ or $c_1, c_2$ may quickly restrict other choices. Subsets $B, D$ are less central and could perhaps accomodate more awkward choices.

The diagram indicates which pairwise set differences are included in the $14$. Note that the dotted line from $A$ to $C$ indicates that not all combinations of pairwise differences are taken.

Pairwise differences

Some of the work of Solomon Golomb, e.g. a Golomb Ruler, may be of tangential interest, although the solution to this problem must be simpler than that.

$\endgroup$
9
$\begingroup$

Concept tested: Parity

Observe that each term appears an even number of times in all of the absolute values.

Can the sum of absolute values be $1+2+3+\ldots + 14 = 105$?

$\endgroup$
  • $\begingroup$ ... and very quick! $\endgroup$ – Marconius Jul 20 '15 at 0:41
  • $\begingroup$ That's a neat trick! $\endgroup$ – Brian Tung Jul 20 '15 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.