5

Let $a$, $b$, $c$, and $d$ four integers such that $0 <a <b <c <d$. We can get all integers from $1$ to $40$ by expressions containing or not only the numbers $a, b, c$ and $d$. In these expressions $a, b​​, c$ and $d$ do not appear more than once and in those expressions that use more than one of these numbers only addition and / or subtraction are allowed. Determine $a, b​​, c$ and $d$.

I have found out these numbers but not in an elegant way. I wonder if anyone knows any more appropriate method to tackle that problem.

Edit: It's not sufficiently clear to me why {1,3, 9, 27} is the only set that solves the problem. If it was stated in the problem "get all integers from 1 to 38", then there would be at least three solutions for this problem: {1, 3, 9, 25}, {1, 3, 9, 26} and {1, 3 , 9, 27}.

RicardoCruz
  • 3,693
  • A closer look reveals that duplicacy may actually be contested (at least with my suggestion as it is not an exact duplicate). This is simply a frequently recurring problem - often given as a weighing problem. There may be a better/exact match here somewhere. – Jyrki Lahtonen Jun 11 '13 at 20:12
  • 1
    @JyrkiLahtonen Thanks for the link it was useful. – RicardoCruz Jun 12 '13 at 11:23

2 Answers2

4

The trick is to try to find a set of numbers that lets you write a lot of numbers as a sum and difference, without overlapping.

$$\begin{array}{cc} \mbox{set of numbers} & \mbox{the numbers you can reach with them}\\ \left\{ 1\right\} & \underbrace{\overset{-1}{\star}\overset{0}{\star}\overset{1}{\star}}_{3}\\ \left\{ 1,3\right\} & \underbrace{\overset{-4}{\star}\overset{}{\star}\overset{}{\star}}_{3}\underbrace{\overset{}{\star}\overset{0}{\star}\overset{}{\star}}_{3}\underbrace{\overset{}{\star}\overset{}{\star}\overset{4}{\star}}_{3}\\ \left\{ 1,3,9\right\} & \underbrace{\overset{-13}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}}_{9}\underbrace{\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{0}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}}_{9}\underbrace{\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{}{\star}\overset{13}{\star}}_{9}\\ \left\{ 1,3,9,27\right\} & \underbrace{\overset{-40}{\star}\cdots\overset{}{\star}\overset{}{\star}\overset{}{\star}\cdots\overset{}{\star}}_{27}\underbrace{\overset{}{\star}\cdots\overset{}{\star}\overset{0}{\star}\overset{}{\star}\cdots\overset{}{\star}}_{27}\underbrace{\overset{}{\star}\cdots\overset{}{\star}\overset{}{\star}\overset{}{\star}\cdots\overset{40}{\star}}_{27} \end{array}$$

At each step above if I had added a smaller number to the set, there would be overlap, and the highest reachable number would be lower. (Hence we would not get up to 40) If I had chosen a larger number, I would be missing some numbers.

Alex L
  • 590
  • 6
  • 13
1

$\{1,3,9,27\}$ can express all numbers from $-40$ to $40$ in the manner requested. See @Jirki's link for an explanation of why these numbers are selected. This is called a balanced ternary representation.

vadim123
  • 82,796