I need help in finding a solution procedure to these types of Problem conditions.

Question

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

Answer 1

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.

Answer 2

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.

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

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

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.

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