Sum and Divisibility Puzzle

I have $5$ positive integers: $a,b,c,d,e$.

$a,b,c,d,e$ are all different, and $a\mid b\mid c\mid d\mid e$, in other words the ratios $$\frac ba, \frac cb, \frac dc, \frac ed $$ are all integers.

$$a+b+c+d+e = 47.$$

I need to find out what $a,b,c,d,e$ are. Apparently there is only one solution to this.

I did some trial and error and came to an answer of $1,2,4,8,32$. But I really have no idea how to come to this conclusion more formally.

The problem comes from a section of my book that talks about prime factorization.

I can figure that the direction that I need to go in is looking at the fact that 47 is prime and that adding the prime factorizations of a,b,c,d,e will give me 47 in some elegant way.

Can someone provide some direction?

Solution 1:

Since $47$ is prime and all variables must be divisible by $a$, one must have $a=1$. Now $b+c+d+e=46=2\times23$, of which $b$ must be a divisor. It is not hard to exclude $b\in\{23,46\}$ and $b=1=a$ is forbidden, so $b=2$. Now $c+d+e=44=2\times2\times11$. Again $c\geq11$ is easy to rule out and $c\leq2$ is forbidden, so $c=4$. One gets $d+e=40=2\times2\times2\times 5$. Since $d$ must be a multiple of $c=4$, we have $d\in\{8,20,40\}$, of which only $d=8$ is feasible. This leaves $e=32$.

Solution 2:

Simplest method:

Convert the number into binary.

$$47_{10}=(2^5+2^3+2^2+2^1+2^0)_{10}=101111_2$$

The intermediate step gives you the answer.

$$47=32+8+4+2+1$$

This works because every binary digit has exactly twice the value of the next one, and is therefore, a multiple of every digit that follows.

If suppose the binary number gave you less/more than $5$ ones, repeat the process with every number base, till you get a number with exactly $5$ ones, any number of zeroes, but no other digits. For example, $121_{10}=11111_3$, so $121=81+27+9+3+1$.

I have tried for $47$, there is no other solution. I'm not sure whether there exist natural numbers with more than one solution, but I suppose they do.

Solution 3:

All numbers being different imply that all ratios are at least $2$ and the smallest possible sum is $16+8+4+2+1=31$, just $16$ units from $47$.

Obviously, $a=32$ fixes that, but let us make sure there are no other solutions by trying to increase each unknown in turn while adjusting the previous ones with right-to-left doubling (or tripling or quadrupling... as necessary, but this does not arise here):

$\color{green}{\underline{32}+8+4+2+1=47}$.

$24+\underline{12}+4+2+1=43$.

$32+\underline{16}+4+2+1>47$.

$24+12+\underline6+2+1=45$.

$32+16+\underline8+2+1>47$.

$24+12+6+\underline3+1=46$.

$32+16+8+\underline4+1>47$.

$32+16+8+4+\underline2>47$.

Solution 4:

First, if $a \geq 2$, then you'd have $b \geq (2)(2) = 4$, and $c\geq (2)(4) = 8$, and $d\geq (2)(8) = 16$ and $e\geq (2)(16) = 32$, since each of the "adjacent ratios" must be at least $2$. But then $a + b + c + d + e \geq 62$, which doesn't work. Hence $a = 1$.

Next, if $b = 3$, then $b, c, d, e$ are all divisible by $3$, which means $a + b + c + d + e$ is congruent to $1$ modulo $3$, which doesn't work since $47$ is congruent to $2$ rather than $1$. Also, if $b \geq 4$, then $a+b+c+d+e > 47$ as above. Therefore we must have $b = 2$, since $b > a = 1$.

Now $c = bk = 2k$ for some $k>1$. If $c = (2)(3) = 6$, then $a+b+c+d+e = 0$ mod $3$, which again doesn't work, while if $c \geq (2)(4) = 8$, then $a+b+c+d+e > 47$ again. Hence $c = (2)(2) = 4$.

At this point we have $(a, b, c) = (1, 2, 4)$, so $a+b+c=7$ and therefore $d+e = 40$. Also, $d = 4m$ and $e = dn = 4mn$ for some integers $m, n > 1$.

Thus $40 = 4m + 4mn = 4(m + mn)$, so $10 = m + mn = m(1 +n)$. The only way to write $10$ as the product of two integers both greater than $1$ is $10 = (2)(5)$, so either $m = 2$ and $1+n = 5$, or $m=5$ and $1+n = 2$. The latter possibility is eliminated as it would mean $n=1$, so we conclude $m=2$ and $1+n=5$, so $n=4$. That is, $d=8$ and $e=32$.