2

We start with the stet $\left\{1,4,32,128,256\right\}$. In each step we may divide one number by $2$ and multiply another number by $2$. We may repeat this step as many times as we want. Is it possible to reach the set $\left\{512,32,16,16,2\right\}$?

My solution was to let $(1,4,32,128,256)=(a,b,c,d,e)$ to help organize the moves.

  1. Divide e and multiply a by $2$ to get $(2,4,32,128,128)$
  2. Divide e and multiply b by $2$ to get $(2,8,32,128,64)$
  3. Divide c and multiply b by $2$ to get $(2,16,16,128,64)$
  4. Divide d and multiply b by $2$ to get $(2,32,16,64,64)$
  5. Divide d and multiply a by $2$ to get $(4,32,16,32,64)$
  6. Repeat step $5$ to get $(8,32,16,16,64)$
  7. Repeat step $1$ to get $(16,32,16,16,32)$
  8. Repeat step $1$ to get $(32,32,16,16,16)$
  9. Repeat step $1$ again to get $(64,32,16,16,8)$ 10.Repeat step $1$ to get $(128,32,16,16,4)$
  10. Repeat step $1$ to get $(256,32,16,16,2)$ Thus can't reach the desired goal.

Now is there a easier way to go about problems like this instead of going through various steps?

HighSchool15
  • 2,061
  • 14
  • 35
  • 2
    In your original post you went through a series of 10 steps, got to $(256,32,16,16,2)$, and concluded "can't reach the desired goal". But if you're just trying steps, how can you be sure? Maybe there's a $37$ step pathway that you just haven't tried yet that'll get you where you want to be. The problem with just "going through various steps" is that you can never be sure. What you did is a good starting point in terms of getting a feel for the problem and looking for patterns. But in the end you need to find a general rule, a reason no path will ever get you to the desired sequence... – Kevin P. Costello Nov 02 '17 at 19:15
  • 2
    ...(continued). That's the idea behind what the answerers did in their solution. They looked for general properties, a.k.a. "invariants" that never change no matter how many steps you go through. The idea is that these invariants can be used to say things about every sequence of steps, not just the ones you tried. For example, carmichael561's argument can be worded "initially the 5 numbers multiply to $2^{22}$. The product never changes, no matter how many steps you go through. So you can never reach any sequence having product $2^{23}$, including the sequence you want. – Kevin P. Costello Nov 02 '17 at 19:18

3 Answers3

4

Note that the permitted operation preserves the product of the $5$ numbers. And since $1\cdot4\cdot32\cdot128\cdot256=2^{22}$ and $512\cdot32\cdot16\cdot16\cdot 2=2^{23}$, it is not possible to transform the first list into the second.

carmichael561
  • 53,688
1

No. The sum of the $\log_2$ values is unchanged by the given operation and it doesn't match in your two sets.

lulu
  • 70,402
1

The starting set has the following indices for the powers of two $\{0, 2, 5, 7, 8\}$. Looking at whether they are odd $o$ or even $e$ we have $\{e, e, o, o, e\}$.

The number of even indices is 3, i.e. there are an odd number of even indices.

The operation will either change $(o,o) \rightarrow (e,e)$, $(e,e) \rightarrow (o,o)$, or $(e,o) \rightarrow (e,o)$. In each case, there will still be an odd number of even indices after applying the operation..

For the target set, the indices of two are $\{9, 5, 4, 4, 1\}$, we have the pattern of index parities as $\{o, o, e, e, o\}$. I.e. there are an even number of even indices.

Therefore we cannot reach the target set with the given operation.

Paul Aljabar
  • 1,519