4
$\begingroup$

This question already has an answer here:

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}.

$\endgroup$

marked as duplicate by Julian Kuelshammer, Amzoti, Martin, Alex Wertheim, user67258 Jun 18 '13 at 4:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 11 '13 at 20:12
  • 1
    $\begingroup$ @JyrkiLahtonen Thanks for the link it was useful. $\endgroup$ – RicardoCruz Jun 12 '13 at 11:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Alex. Could you clarify what I pointed out in my Edit? I'd be grateful. $\endgroup$ – RicardoCruz Jun 13 '13 at 0:46
  • $\begingroup$ I've edited the last paragraph to try to make it more clear. $\endgroup$ – Alex L Jun 13 '13 at 1:04
1
$\begingroup$

$\{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.

$\endgroup$

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