9

The puzzle is:

Place each number from 1 through 10 in a box. Each box must contain a number that is the difference of two boxes above it, if there are two above it.

The ten boxes are positioned in an inverted triangle with side 4.

My question is: is there an easy way to solve the problem? (as opposed to guessing the solution by a systematic search).

My approach was: 10 is obviously in the top row, so WLOG it is either in the corner or in the second position (the problem is symmetric). 9 is either in the top row or under 10. &c &c &c - until I arrived at

9     10       3       8
   1       7       5
       6       2
           4

Another solution is (mathforum & answers):

8     10       3       9
   2       7       6
       5       1
           4

and mathforum wrongly claims that these two (+ 2 symmetric) are the only ones.

Brute search (using CLOCC/CLLIB/math.lisp):

(defun triangle-is-good (tr)
  (and (= (abs (- (aref tr 0) (aref tr 1))) (aref tr 4))
       (= (abs (- (aref tr 1) (aref tr 2))) (aref tr 5))
       (= (abs (- (aref tr 2) (aref tr 3))) (aref tr 6))
       (= (abs (- (aref tr 4) (aref tr 5))) (aref tr 7))
       (= (abs (- (aref tr 5) (aref tr 6))) (aref tr 8))
       (= (abs (- (aref tr 7) (aref tr 8))) (aref tr 9))))

(with-collect (co)
  (with-permutations-shuffle (tr (vector 1 2 3 4 5 6 7 8 9 10))
    (when (triangle-is-good tr)
      (co (copy-seq tr)))))

yields two more (for a total of 8) solutions:

6     10       1       8
   4       9       7
       5       2
           3

and

8     10       1       6
   2       9       5
       7       4
           3

The only common features across all four solution I see are:

  • the position of 10
  • 8 is in a top corner
  • the sum of the "top inner triangle" is 20
Glorfindel
  • 3,955
sds
  • 4,533
  • 1
    A brute force search found 2 more solutions (+ their reflections): [[6, 1, 10, 8], [5, 9, 2], [4, 7], [3]] and [[6, 10, 1, 8], [4, 9, 7], [5, 2], [3]] – cardboard_box Apr 06 '16 at 20:49
  • 1
    It turns out that one can find such an arrangement for numbers 1 to 15: [6 14 15 3 13], [8 1 12 10], [7 11 2], [4 9], [5] – Dmitry Kamenetsky Jul 20 '19 at 01:50

1 Answers1

1

The arrangements found so far, two having $4$ at the bottom and two having $3$ at the bottom (plus their reflections), are the only solutions.

The key observation is that each of the four rows, from top to bottom, must contain exactly one of the numbers $1, 2, 3$ and $4$. In addition, $10$ in the top row must sit next to the number $1, 2, 3$ or $4$ that is in the top row.

To see that, let $d$ be the number at the bottom. Let $a$ and $b$ be the numbers in the third row (from the top), with $a > b$. Then $d = a - b$. Then let $u$ and $v$ be the numbers in the second row that sit above a, with $u > v$. So $a = u - v$. Finally, let $u = x - y$ with $x, y$ in the top row, $x > y$. So in the end we have $x = d + b + v + y$. $d, b, v, y$ are distinct, positive integer, and their sum is at most $10$; so $x$ must be $10$, and $d, b, v, y$ must be a permutation of $1, 2, 3, 4$.

Now it takes about $10$ minutes to try the various arrangements that satisfy this condition. I won't show them here (no good notation for that), but as you start from the bottom, with $d = 1, 2, 3 or 4$, and you work your way up, most possible arrangements collapse quickly because you will need to use two of the numbers $1, 2, 3, 4$ in the same row (usually the second row from the top) to make the differences work, and that violates the condition we derived above.

This solution requires some manual work but no computer verification.

Roby5
  • 4,287