8
$\begingroup$

Our team has created 9 math puzzles with ranging difficulty. Let me share one of them.

At the beginning a number is given to you. Your objective is to get a different number by making choices. Here's the pseudo code.

Let's say your number is $3$ and you need to reach $56$.

Start

If your number is ODD.

  1. Mr. Black multiplies it by $3$

  2. Then you should add $2$ or add $3$

  3. Go back to Start with your new number

Else (your number is EVEN)

  1. Mrs. White offers you to divide it by $2$

  2. If you accept the offer

    1. Mrs. White divides your number by $2$

    2. Go back to Start with your new number

    Else

    1. Mr. Black multiplies your number by $3$

    2. Then you should add $2$ or add $3$

    3. Go back to Start with your new number

If you've managed to get $56$ in Start step of this algorithm, then puzzle is solved.

As an example, here's the evaluation

$3 \to 9 \to \text{by adding 2} \to 11 \to 33 \to \text{by adding 3} \to 36 \to \text{by accepting offer} \to 18 \to \text{by declining offer} \to 54 \to \text{by adding 2} \to 56$

Here are some puzzles for you to think $$3 \to 1$$ $$65 \to 9$$ $$15 \to 128$$

My hypothesis is: You can reach from any natural number to any other natural number (so there can be infinite pack of "interesting" puzzles). What I have noticed, the more these numbers are far from each other, the harder it is to reach to solution. The puzzle is inspired from well known problem :)

I have 3 questions:

  1. Can you solve all of them? :)

  2. Is there a strategy or an algorithm, by which you can always reach to solution with any given source and target numbers?

  3. Can you prove or disprove my hypothesis?

You can try this puzzle with a more interactive way here (since level 6)

P.S: This is my first puzzle question. Hopefully the formatting is correct.

$\endgroup$
  • 4
    $\begingroup$ I'm closing this question as off-topic because it's neither a puzzle nor a question about puzzles, but merely a link to puzzles elsewhere. That's not what PSE is for, I'm afraid. If you can revise this to be a self-contained question, then please go ahead and request that the question be reopened. $\endgroup$ – Gareth McCaughan Apr 4 at 16:17
  • 1
    $\begingroup$ The above is a little unfair (but there's only a limited number of characters per comment). Of course you're also asking some questions about those puzzles. But the questions aren't meaningful without the puzzles themselves, which are located elsewhere. Questions here need to be self-contained, unless there are extraordinary circumstances making that possible, so that e.g. they don't become meaningless on account of other sites changing or disappearing. $\endgroup$ – Gareth McCaughan Apr 4 at 16:19
  • $\begingroup$ @GarethMcCaughan sorry for wrong formatting. Let me know if the question still needs improvements. $\endgroup$ – shcolf Apr 4 at 18:53
  • 1
    $\begingroup$ Looks OK to me now. Reopened. Thanks, shcolf! $\endgroup$ – Gareth McCaughan Apr 4 at 19:05
  • $\begingroup$ The puzzle has a rather Collatz-y feel to it; if the answer is that you can get from anywhere to anywhere, it might be rather difficult to prove. $\endgroup$ – Gareth McCaughan Apr 4 at 19:09
6
$\begingroup$

[EDITED to add: When I wrote this, the original statement of the problem had an error in it. That's now been fixed and I've adjusted my answer accordingly.]

The most interesting of the questions originally asked is the third: is it possible to get from any number to any other number by this process?

The answer is

yes, you can get from anywhere to anywhere.

First, the easy bit.

You can get from 1 to anything. Proof: I claim that everything other than 1 can be reached from something smaller, which plainly suffices. That's certainly true for numbers of the form $3n+2$ or $3n+3$ (which can be reached from $n$). The number $3n+1$ can be reached from $6n+2$ (which is always even and therefore halveable), which in turn can be reached from $2n$, which is smaller than $3n+1$. The only positive integers we haven't covered yet are 2, which we can reach as follows: 1, 6, 20, 10, 32, 16, 8, 4, 2; and 3, which we can reach as follows: 1, 6, 3.

Now the not-so-easy bit.

You can reach 1 from everywhere. This is uncomfortably similar to the Collatz conjecture, but the fact that we have a choice of what to do seems like it should help. So, I claim that any number bigger than 1 can lead to something smaller than itself, which plainly suffices. Even numbers are immediately halveable. A number of the form $4n-1$ yields (via the $3x+3$ operation) $12n$, which we can halve twice to get $3n$, which is smaller. (Unless n=1, when it's equal, but direct search shows that 3 can in fact be reduced.) So let's suppose our number is $4n+1$.

Now

it will in fact be helpful to consider four separate cases: our number is $16n+1,5,9,13$. (Special small cases: brute force shows that 5 takes 9 steps to reduce, 9 takes 6 steps, and 13 takes 6 steps.) We will then split the first two a little further: $32n+1,17$ and $32n+5,21$. Here goes:
32n+1 96n+6 48n+3 144n+12 72n+6 36n+3 108n+12 54n+6 27n+3
32n+17 96n+54 48n+27 144n+84 72n+42 216n+128 108n+64 54n+32 27n+16
32n+5 96n+18 288n+56 144n+28 72n+14 36n+7 108n+24 54n+12 27n+6
32n+21 96n+66 288n+200 144n+100 72n+50 216n+152 108n+76 54n+38 27n+19
16n+9 48n+30 24n+15 72n+48 36n+24 18n+12 9n+6
16n+13 48n+42 144n+128 72n+64 36n+32 18n+16 9n+8
... and, phew, it turns out that every case is reducible. So everything bigger than 1 can be reduced in at most 9 steps (almost always in at most 8 steps), so everything eventually leads to 1. Since everything is obtainable from 1 as well, we're done.

This, of course, also answers the second question: whether there's a systematic way to get from one number to another.

I just described one, though surely one can usually do better.

Credit where due:

thanks to noedne for pointing out (in comments below) a gap: I hadn't shown that $1\rightarrow2$ is possible. (Now I have.)

$\endgroup$
  • $\begingroup$ Ohh.. I just noticed that I forgot 1 key step to put in the algorithm :( Really sorry about that. Now it is fixed. $\endgroup$ – shcolf Apr 4 at 20:03
  • $\begingroup$ I wondered :-). $\endgroup$ – Gareth McCaughan Apr 4 at 21:58
  • 1
    $\begingroup$ I was. Fixed now. Thanks! $\endgroup$ – Gareth McCaughan Apr 5 at 1:58
  • $\begingroup$ Well done! :) It took me some time to follow your proof, until I finally get it. That's the reason I'm accepting it now. Thank you for taking time and solving it. $\endgroup$ – shcolf Apr 5 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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