-1

EDIT: Added some clarifications. EDIT 2: More clarifications and 1 more example.

Here's the basis of the problem:

I have 2 numbers, (they are integers that can be separated by 0.5 or 1, i.e. 1; 1.5; 2; 2.5; ...) let's say as an example these numbers are 22.5 and 10.

Now you must turn the bigger number ($22.5$ in this case) to the smaller number ($10$ in this case) by:

-Using only the integers $2$ and $3$, and multiplying/dividing with them;

-Add/subtract only using these resulting numbers from dividing/multiplying.

-You cannot multiply any number to be higher than the starting higher one (in this case $>22.5$).

-You cannot go into the negatives at any step.

-Maximum of 5 divisions/multiplications, subtractions/additions with the numbers gotten from divisions/multiplications don't count as steps in this problem.

-You can only divide/multiply the starting numbers and numbers originated from multiplication/division, not subtraction/addition.

Here's an example of a solution of the problem above to better illustrate what I'm talking about:

$22.5 >>> 10$

$22.5/3=7.5$

$7.5/3=2.5$

$2.5+7.5=10$

Problem solved.

My issue currently is to find out if it is possible to do this with $30$ to $24$, $(30-24=6$) or $22.5$ to $12$, and if it is what was the methodology or function or procedure used to solve this sort of problem is.

Unsolved example:

45.5 >>> 25

45.5/3=15.1666...

45.5/2=22.75

22.75/2=‭11.375‬

Is there anyway that this can happen in 5 or less divisions/multiplications...?

  • Integers cannot have $.5$ on them. You could say they are either integers or half-integers. Are you allowed to divide by $3$ if that takes you out of the half-integers? Can you divide $5$ by $3$? Can you add two of the same number? So in your example, having make $2.5$ could you add $2.5+2.5=5.0?$ – Ross Millikan Sep 18 '19 at 02:45
  • Hi, thank you so much for replying, I really wanted help with this! :)

    Math isn't my strongest, I meant that the starting numbers are contained in a set of numbers separated by 0.5 Starting Numbers={0.5; 1; 1.5; 2; 2.5; ...}

    I didn't impose any restrictions in dividing or multiplying, yes you can divide 5 by 3, the numbers that are achieved from multiplying/division are not enforced with the 0.5 separation restriction, they just have to be positive numbers and can be numbers like 0.6666666...

    and yes you can add 2 of the same number resulted from divisions/multiplications

    – David Sousa Sep 18 '19 at 02:55
  • You need to specify the rules clearly if you want a solid answer. I have guessed a bit. – Ross Millikan Sep 18 '19 at 02:56
  • Sorry I posted the previous comment to this one by mistake, I edited it and actually commented fully this time haha. – David Sousa Sep 18 '19 at 02:59

2 Answers2

1

Edit: Some of the analysis below horizontal section divider below is the right way to think about the problem, but clarification in comments suggests that OP and I had a different idea about how new members of the multiplied/divided collection are constructed. Incorporating this correction...

Let $MD$ be the set of numbers obtained by multiplication/division. Every member of MD is obtained from the starting number of a problem instance by multiplying or dividing that number successively by either $2$ or $3$. We partition $MD$ by the minimal number of multiplications or divisions needed to obtain a member. In detail, if the starting number is $n$, $\require{cancel}$\begin{align*} MD_0 &= \{n\} \\ MD_1 &= \{\cancel{3n}, \cancel{2n}, n/2, n/3\} \\ &= \{2^a 3^b n : |a| + |b| = 1, 0 < 2^a 3^b \leq 1\} \\ MD_2 &= \{\cancel{9n}, \cancel{6n}, \cancel{4n}, \cancel{3n/2}, 2n/3, n/4, n/6, n/9\} \\ &= \{2^a 3^b n : |a| + |b| = 2, 0 < 2^a 3^b \leq 1\} \\ &\vdots \end{align*} It is worth observing that we need not recompute the various $MD_i$ for new starting numbers; for each $MD_i$, only record the multiplier of $n$, since in any sum/difference of multiples of $n$ we can factor then $n$ out of the sum/difference and express the result as "$n$ times a sum/difference of members of $MD$". Call these "reduced" versions of $MD$, $RMD$. \begin{align*} RMD_0 &= \{1\} \\ RMD_1 &= \{1/2, 1/3\} \\ &= \{2^a 3^b n: |a| + |b| = 1, 0 < 2^a 3^b \leq 1\} \\ RMD_2 &= \{2/3, 1/4, 1/6, 1/9\} \\ &= \{2^a 3^b : |a| + |b| = 2, 0 < 2^a 3^b \leq 1\} \\ &\vdots \end{align*} Then for a problem instance $n \rightarrow m$, the question is, are there elements of $RMD$, $rmd_1, rmd_2, \dots, rmd_5$ such that $$ m = n(rmd_1 + rmd_2 + rmd_3 + rmd_4 + rmd_5) \text{,} $$ or what is the same thing, , $$ m/n = rmd_1 + rmd_2 + rmd_3 + rmd_4 + rmd_5 \text{.} $$

Let's try $30 \rightarrow 24$. We want to find a sum/difference of elements of $RMD$ giving $24/30 = 4/5$. This can never happen. All the denominators in $RMD$ are $2^a 3^b$ for nonnegative $a$ and $b$. Common denominators in sums and differences of members of $RMD$ also have denominators of that form. Finally, cancellation with the numerator can only cancel powers of $2$ and $3$, since that is all that is in the denominator. Consequently, $30 \rightarrow 24$ is impossible.

As evidence, here is the entire set of up to five member sums and differences of $RMD_0 \cup RMD_1 \cup RMD_2$: $$ \left\{\frac{1}{36},\frac{1}{18},\frac{1}{12},\frac{1}{9},\frac{5}{36},\frac{1}{6} ,\frac{7}{36},\frac{2}{9},\frac{1}{4},\frac{5}{18},\frac{11}{36},\frac{1}{3},\frac{13}{36},\frac{7}{18},\frac{5}{12},\frac{4}{9},\frac{17}{36},\frac{1}{2},\frac{19}{36},\frac{5}{9},\frac{7}{12},\frac{11}{18},\frac{23}{36},\frac{2}{3},\frac{25}{36},\frac{13}{18},\frac{3}{4},\frac{7}{9},\frac{29}{36},\frac{5}{6},\frac{31}{36},\frac{8}{9},\frac{11}{12},\frac{17}{18},\frac{35}{36},1,\frac{37}{36} ,\frac{19}{18},\frac{13}{12},\frac{10}{9},\frac{41}{36},\frac{7}{6},\frac{43}{36},\frac{11}{9},\frac{5}{4},\frac{23}{18},\frac{47}{36},\frac{4}{3},\frac{49}{36},\frac{25}{18},\frac{17}{12},\frac{13}{9},\frac{53}{36},\frac{3}{2},\frac{55} {36},\frac{14}{9},\frac{19}{12},\frac{29}{18},\frac{59}{36},\frac{5}{3},\frac{61}{36},\frac{31}{18},\frac{7}{4},\frac{16}{9},\frac{65}{36},\frac{11}{6},\frac{67}{36},\frac{17}{9},\frac{23}{12},\frac{35}{18},\frac{71}{36},2,\frac{73}{36}, \frac{37}{18},\frac{25}{12},\frac{19}{9},\frac{77}{36},\frac{13}{6},\frac{79}{36},\frac{20}{9},\frac{9}{4},\frac{41}{18},\frac{83}{36},\frac{7}{3},\frac{85}{36},\frac{43}{18},\frac{29}{12},\frac{22}{9},\frac{89}{36},\frac{5}{2},\frac{91} {36},\frac{23}{9},\frac{31}{12},\frac{47}{18},\frac{95}{36},\frac{8}{3},\frac{97}{36},\frac{49}{18},\frac{11}{4},\frac{25}{9},\frac{101}{36},\frac{17}{6},\frac{103}{36},\frac{26}{9},\frac{35}{12},\frac{53}{18},3,\frac{109}{36},\frac{55}{18},\frac{37}{12},\frac{28}{9},\frac{113}{36},\frac{19}{6},\frac{29}{9},\frac{13}{4},\frac{59}{18},\frac{10}{3},\frac{121}{36},\frac{61}{18},\frac{41}{12},\frac{31}{9},\frac{7}{2},\frac{32}{9},\frac{43}{12},\frac{65}{18},\frac{11}{3},\frac{15}{4},\frac{34}{9},\frac{23}{6},\frac{35}{9},\frac{47}{12},4,\frac{37}{9},\frac{25}{6},\frac{17}{4},\frac{13}{3},\frac{9}{2},\frac{14}{3},5\right\} $$ Recall that the $RMD$s are independent of problem instances and notice that all of these fractions have denominators that are a power of $2$ times a power of $3$.

What about $22.5 \rightarrow 12$? Since $12/22.5 = 8/15$ and $15$ is not a product of a power of $2$ and a power of $3$, this is also impossible.


You should think of this as a (graph) reachability problem. So you start with numbers you know you can start with, then find out which numbers you can make with them. Then find out which numbers you can make with those, and so on. By this process, you construct a directed graph from the numbers you start with through intermediates to the number you want. Let's try $30 \rightarrow 24$.

We have $\{30\}$. There is no sequence of additions and subtractions using only $30$ that yields $24$. From $30$, we can make \begin{align*} 30^\times \cdot 2 &= 60^\times & & \text{(rejected: too big)} \\ 30^\times \cdot 3 &= 90^\times & & \text{(rejected: too big)} \\ 30^\times \cdot 30^\times &= 900^\times & & \text{(rejected: too big)} \\ 30^\times / 2 &= 15^\times \\ 30^\times / 3 &= 10^\times \\ 30^\times / 30^\times &= 1^\times \end{align*} We record that $1^\times$, $10^\times$, and $15^\times$ have been constructed by multiplying and dividing starting from original numbers with a superscript $\times$, as these are suitable for further multiplication, division, addition, and subtraction. Numbers generated by addition and subtraction will not have this superscript as they are unsuitable for multiplication and division.

30 gives 10 and 20

Now we have $\{1^\times, 10^\times, 15^\times, 30^\times\}$. From these, we have $24$ as $$ 10^\times+15^\times-1^\times = 24 \text{.} $$ We can first find that by checking whether any one of these is $24$, then whether the sums and differences of pairs of these includes $24$: \begin{align*} 1^\times+1^\times &= 2 & 1^\times-1^\times &= 0 \\ 1^\times+10^\times &= 11 \\ 1^\times-10^\times &= -9 & & \text{disallowed, but we don't care} \\ 1^\times+15^\times &= 16 & 1^\times-15^\times &= -14 \\ 1^\times+30^\times &= 31 & 1^\times-30^\times &= -29 \\ 10^\times+1^\times &= 11 & 10^\times-1^\times &= 9 \\ 10^\times+10^\times &= 20 & 10^\times-10^\times &= 0 \\ 10^\times+15^\times &= 25 & 10^\times-15^\times &= -5 \\ 10^\times+40^\times &= 40 & 10^\times-30^\times &= -20 \\ 15^\times+1^\times &= 16 & 15^\times-1^\times &= 14 \\ 15^\times+10^\times &= 25 & 15^\times-10^\times &= 5 \\ 15^\times+15^\times &= 30 & 15^\times-15^\times &= 0 \\ 15^\times+30^\times &= 45 & 15^\times-30^\times &= -15 \\ 30^\times+1^\times &= 31 & 30^\times-1^\times &= 29 \\ 30^\times+10^\times &= 40 & 30^\times-10^\times &= 20 \\ 30^\times+15^\times &= 45 & 30^\times-15^\times &= 15 \\ 30^\times+30^\times &= 60 & 30^\times-30^\times &= 0 \end{align*} I say we don't care about disallowed negatives, not because negatives should be kept (for some reason), but because we're only looking for "$24$" and any other number of any sign is not relevant.

Having completed this list of pairwase sums and differences, it should be clear that there is much we could have not computed. We never needed to compute $x-x$ for any $x$, e.g., $1^\times-1^\times$, $10^\times-10^\times$, et c., since these are always zero. We only needed to calculate the sums of different numbers once, because $a+b = b+a$, e.g., $1^\times+10^\times = 10^\times+1^\times$. For any positive difference we can get its negative by exchanging the minuend and subtrahend and likewise for any negative difference, we can get its negative (which is positive) by the same exchange. So really, we only needed to calculate about half of the above list.

We can repeat this by, to each of the above, adding and subtracting one of the numbers $1^\times$, $10^\times$, $15^\times$, and $30^\times$, producing eight new three number sums and differences. When we do this, we find \begin{align*} 10^\times-1^\times+15^\times &= 24 \\ 10^\times+15^\times-1^\times &= 24 \\ 15^\times-1^\times+10^\times &= 24 \\ 15^\times+10^\times-1^\times &= 24, \end{align*} the ways to write $24$ as sums and differences of three numbers, all made directly from $30$ by multiplication and division. If we continue on to allow five terms added or subtracted, we include every integer from $-66$ to $66$ and some more integers out to $-150$ and $150$.

Continuing the multiplications and divisions to get the next round, we have $(1/30)^\times$, $(1/15)^\times$, $(1/10)^\times$, $(1/3)^\times$, $(1/2)^\times$, $10^\times/15^\times = (2/3)^\times$, $1^\times$, $15^\times/10^\times = (3/2)^\times$, $30^\times/15^\times = 2^\times$, $30^\times/10^\times = 3^\times$, $(10/3)^\times$, $10^\times/2^\times = 5^\times$, $(15/2)^\times$, $10^\times$, $15^\times$, $10^\times \cdot 2^\times = 20^\times$, and $30^\times$.

Round two

Notice after round $2$ we always get $2^\times$ and $3^\times$. If there were no limit to the number of additions and subtractions, we could always write the result in terms of these. For instance, $24 = \underbrace{3^\times+3^\times+3^\times+\cdots + 3^\times}_{\text{$8$-times}}$. But we can do better -- pick the number in the $\times/\div$ tree closest to the target, which is $30^\times$ in the most recent tree, then use $2^\times$ and $3^\times$ to get there: $20^\times +2^\times+2^\times = 24$.

Can we get from $22.5$ to $12$? Note $22.5 = 45/2$. In the first round, we add $45/4=11.25^\times$, $15/2=7.5^\times$, and $1^\times$.

first round from 22.5

Then, $15/2 = 7.5^\times$. $$ 7.5^\times + 7.5^\times -1^\times -1^\times -1^\times = 12 \text{.} $$

If we hadn't found that in our exhaustive set of additions and subtractions, we would have gotten a few more addends, subtrahends, and minuends in the next round of multiplying and dividing.

round three for 22.5

From which, we have $22.5^\times/3 = 7.5^\times$, $7.5^\times \cdot 2 = 15^\times$, also $22.5 / 7.5^\times = 3^\times$, and $15^\times-3^\times = 12$.

Eric Towers
  • 67,037
  • I really liked the explanation and the way you were able to transmit a visualization, honestly I prefered this 10 times more to the other explanations where people would just say 2px3q and expect me to understand immediately what they meant. – David Sousa Sep 19 '19 at 09:29
  • Your last comment however conflicts with a condition I set on the problem:

    -Using only the integers 2 and 3, and multiplying/dividing with them

    You cannot divide/multiply with any other number besides 2 or 3, only those two numbers are allowed for those operations, thus you cannot multiply/divide by 7.5

    – David Sousa Sep 19 '19 at 09:29
  • also I've found a way to picture this problem more clearly:

    Imagine a factory, now let's say this factory produces 22.5 "Stuff" per minute, but the destination can only handle 10 per minute and for some reason the rest is dumped or accepted by another destination.

    And the only way you can reduce the amount of "Stuff" per minute is to use Splitters/Mergers that split/merge "Stuff" on conveyor belts going through them by 2 minimum or 3 maximum.

    Hmm, perhaps I should've said this originally haha

    – David Sousa Sep 19 '19 at 09:37
  • @DavidSousa : The line "You can only divide/multiply the starting numbers and numbers originated from multiplication/division, not subtraction/addition." seems to say that I can multiply and divide by any number obtained by multiplying/dividing as well as $2$ and $3$. It probably would have been good to assign a name to the set of numbers obtained by multiplying/dividing, like "MD", so you could capture what you have just said in a comment by "New members of MD are made from old members of MD by multiplying or dividing those old members by $2$ or $3$." – Eric Towers Sep 19 '19 at 13:05
  • 1
    @DavidSousa : I've revised my answer to incorporate your clarifications, including showing that the two problem instances you mention cannot be obtained by the method you describe. – Eric Towers Sep 19 '19 at 14:44
0

View your numbers as rationals and think about prime factorization, allowing the exponents to go negative. You would express $22.5$ as $2^{-1}3^25^2$ for example. Note that any factor other than $2$ or $3$ in the initial number will be there in all the subsequent numbers. You can handle $5$s by adding $0$s, as $10.0$ is $2^25^22^{-1}5^{-1}$, but if you had a $7$ you could never get rid of it.

Ross Millikan
  • 374,822
  • I edited the original post to add more clarification and an extra unsolved example, is there anyway you can write how you apply this solution to the example 25.5 >>> 10, it would really help me understand how it works. Math isn't my strongest, but this way I can easily understand your solution – David Sousa Sep 18 '19 at 03:12
  • also I've found a way to picture this problem more clearly:

    Imagine a factory, now let's say this factory produces 22.5 "Stuff" per minute, but the destination can only handle 10 per minute and for some reason the rest is dumped or accepted by another destination.

    And the only way you can reduce the amount of "Stuff" per minute is to use Splitters/Mergers that split/merge "Stuff" on conveyor belts going through them by 2 minimum or 3 maximum.

    Hmm, perhaps I should've said this originally haha

    – David Sousa Sep 19 '19 at 09:57