Doubling/tripling puzzle: make 1 from 1536 in as few steps as possible











up vote
4
down vote

favorite












You start with the number 1536. Your mission is to get to 1 in as few steps as possible. At each step, you may either multiply or divide the number you have, by either 2 or 3; but, only if the result is a whole number whose first digit is 1, 3, 4, or 9. That is all.










share|improve this question






















  • "first digit" meaning the ones digit, or "first digit" meaning most significant digit?
    – Hugh
    4 hours ago








  • 1




    @Hugh - most significant.
    – deep thought
    4 hours ago










  • I wonder if the fact that the prime factorization of 1536 is $2^9 times 3$. That puts a lower bound of at least 10 operations, but it must be more since just trying possibilities shows that there must be some multiplications in there.
    – Hugh
    4 hours ago

















up vote
4
down vote

favorite












You start with the number 1536. Your mission is to get to 1 in as few steps as possible. At each step, you may either multiply or divide the number you have, by either 2 or 3; but, only if the result is a whole number whose first digit is 1, 3, 4, or 9. That is all.










share|improve this question






















  • "first digit" meaning the ones digit, or "first digit" meaning most significant digit?
    – Hugh
    4 hours ago








  • 1




    @Hugh - most significant.
    – deep thought
    4 hours ago










  • I wonder if the fact that the prime factorization of 1536 is $2^9 times 3$. That puts a lower bound of at least 10 operations, but it must be more since just trying possibilities shows that there must be some multiplications in there.
    – Hugh
    4 hours ago















up vote
4
down vote

favorite









up vote
4
down vote

favorite











You start with the number 1536. Your mission is to get to 1 in as few steps as possible. At each step, you may either multiply or divide the number you have, by either 2 or 3; but, only if the result is a whole number whose first digit is 1, 3, 4, or 9. That is all.










share|improve this question













You start with the number 1536. Your mission is to get to 1 in as few steps as possible. At each step, you may either multiply or divide the number you have, by either 2 or 3; but, only if the result is a whole number whose first digit is 1, 3, 4, or 9. That is all.







calculation-puzzle formation-of-numbers






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 4 hours ago









deep thought

2,231529




2,231529












  • "first digit" meaning the ones digit, or "first digit" meaning most significant digit?
    – Hugh
    4 hours ago








  • 1




    @Hugh - most significant.
    – deep thought
    4 hours ago










  • I wonder if the fact that the prime factorization of 1536 is $2^9 times 3$. That puts a lower bound of at least 10 operations, but it must be more since just trying possibilities shows that there must be some multiplications in there.
    – Hugh
    4 hours ago




















  • "first digit" meaning the ones digit, or "first digit" meaning most significant digit?
    – Hugh
    4 hours ago








  • 1




    @Hugh - most significant.
    – deep thought
    4 hours ago










  • I wonder if the fact that the prime factorization of 1536 is $2^9 times 3$. That puts a lower bound of at least 10 operations, but it must be more since just trying possibilities shows that there must be some multiplications in there.
    – Hugh
    4 hours ago


















"first digit" meaning the ones digit, or "first digit" meaning most significant digit?
– Hugh
4 hours ago






"first digit" meaning the ones digit, or "first digit" meaning most significant digit?
– Hugh
4 hours ago






1




1




@Hugh - most significant.
– deep thought
4 hours ago




@Hugh - most significant.
– deep thought
4 hours ago












I wonder if the fact that the prime factorization of 1536 is $2^9 times 3$. That puts a lower bound of at least 10 operations, but it must be more since just trying possibilities shows that there must be some multiplications in there.
– Hugh
4 hours ago






I wonder if the fact that the prime factorization of 1536 is $2^9 times 3$. That puts a lower bound of at least 10 operations, but it must be more since just trying possibilities shows that there must be some multiplications in there.
– Hugh
4 hours ago












2 Answers
2






active

oldest

votes

















up vote
5
down vote













Not sure if it is the quickest, but I found two ways to do it with 28 steps:





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/2 46656
*3 139968
*3 419904
*3 1259712
*3 3779136
/2 1889568
/2 944784
/3 314928
/3 104976
/3 34992
/3 11664
/3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1



and





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/3 31104
/3 10368
/3 3456
/3 1152
/3 384
/2 192
/2 96
/2 48
*3 144
*3 432
*3 1296
*3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1






share|improve this answer





















  • That looks pretty good—better than I've done, at least.
    – Hugh
    3 hours ago




















up vote
4
down vote













As Jo has already shown, this can be accomplished in




28 steps. This is minimal, and it can be proven.




To help visualize this problem, we can imagine:




A two-dimensional grid/chart where each point is a number of the form $3^x2^y$, with $(x,y)$ as the relevant co-ordinates. We want to find a path from $(1,9)$ to $(0,0)$ while making only one step up/down/left/right at a time, and ensuring that the numbers we step on have their most significant digit in the set {1,3,4,9}.

Here is what the chart looks like for the range $(0,0)$ to $(10,10)$. The dashes represent numbers that do not begin with {1,3,4,9}, and so are unusable in our path.
1024 3072 9216 ---- ---- ---- ---- ---- ---- ---- ---- .
---- 1536 4608 13824 41472 124416 373248 1119744 3359232 10077696 30233088 .
---- ---- ---- ---- ---- ---- 186624 ---- 1679616 ---- 15116544 .
128 384 1152 3456 10368 31104 93312 ---- ---- ---- ---- .
---- 192 ---- 1728 ---- 15552 46656 139968 419904 1259712 3779136 .
32 96 ---- ---- ---- ---- ---- ---- ---- ---- 1889568 .
16 48 144 432 1296 3888 11664 34992 104976 314928 944784 .
---- ---- ---- ---- ---- 1944 ---- 17496 ---- 157464 472392 .
4 12 36 108 324 972 ---- ---- ---- ---- ---- .
---- ---- 18 ---- 162 486 1458 4374 13122 39366 118098 .
1 3 9 ---- ---- ---- ---- ---- ---- 19683 ---- .

From here, we can see two different routes of 28 steps each: (1536->373248->93312->384->48->3888->972->36->9->1) and (1536->373248->46656->3779136->944784->3888->972->36->9->1).




Proving minimality:




Since a path of length 28 exists (we've found two), we can rule out anything that's too far away to be used in a shortest path.

Moving from (1,9) to (0,0) must take at least ten steps on its own, so we can move at most nine steps completely out of the way (and nine steps back) in a shortest route. That limits us to only considering x-coordinates up to 10; any further would require making at least ten '*3' steps, eleven '÷3' steps, and at least nine '÷2' steps, putting the route definitely longer than 28.

With our x-coordinate limited to [0,10], we now look at the bottlenecks.

It should be clear that any shortest route must start by going from 1536 to 93312 in seven steps, and must end by going from 3888 to 1 in nine steps. These are both forced by unique bottlenecks; there is only one way to step from $(x,7)$ to $(x,6)$ and only one way to step from $(x,3)$ to $(x,2)$ in this range.

This leaves at most twelve steps to go from 93312 to 3888. Either by observation or by pointing out that there are only two ways to go from $(x,6)$ to $(x,5)$, we can see that there are exactly two shortest routes from 93312 to 3888, and both require all twelve steps.

Therefore, the shortest route is 28 steps, and there are exactly two ways to do so, both of which are described in Jo's solution and below the chart.







share|improve this answer





















  • Very nice grid; I like it.
    – Jo.
    2 hours ago











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f76356%2fdoubling-tripling-puzzle-make-1-from-1536-in-as-few-steps-as-possible%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
5
down vote













Not sure if it is the quickest, but I found two ways to do it with 28 steps:





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/2 46656
*3 139968
*3 419904
*3 1259712
*3 3779136
/2 1889568
/2 944784
/3 314928
/3 104976
/3 34992
/3 11664
/3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1



and





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/3 31104
/3 10368
/3 3456
/3 1152
/3 384
/2 192
/2 96
/2 48
*3 144
*3 432
*3 1296
*3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1






share|improve this answer





















  • That looks pretty good—better than I've done, at least.
    – Hugh
    3 hours ago

















up vote
5
down vote













Not sure if it is the quickest, but I found two ways to do it with 28 steps:





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/2 46656
*3 139968
*3 419904
*3 1259712
*3 3779136
/2 1889568
/2 944784
/3 314928
/3 104976
/3 34992
/3 11664
/3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1



and





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/3 31104
/3 10368
/3 3456
/3 1152
/3 384
/2 192
/2 96
/2 48
*3 144
*3 432
*3 1296
*3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1






share|improve this answer





















  • That looks pretty good—better than I've done, at least.
    – Hugh
    3 hours ago















up vote
5
down vote










up vote
5
down vote









Not sure if it is the quickest, but I found two ways to do it with 28 steps:





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/2 46656
*3 139968
*3 419904
*3 1259712
*3 3779136
/2 1889568
/2 944784
/3 314928
/3 104976
/3 34992
/3 11664
/3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1



and





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/3 31104
/3 10368
/3 3456
/3 1152
/3 384
/2 192
/2 96
/2 48
*3 144
*3 432
*3 1296
*3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1






share|improve this answer












Not sure if it is the quickest, but I found two ways to do it with 28 steps:





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/2 46656
*3 139968
*3 419904
*3 1259712
*3 3779136
/2 1889568
/2 944784
/3 314928
/3 104976
/3 34992
/3 11664
/3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1



and





   1536
*3 4608
*3 13824
*3 41472
*3 124416
*3 373248
/2 186624
/2 93312
/3 31104
/3 10368
/3 3456
/3 1152
/3 384
/2 192
/2 96
/2 48
*3 144
*3 432
*3 1296
*3 3888
/2 1944
/2 972
/3 324
/3 108
/3 36
/2 18
/2 9
/3 3
/3 1







share|improve this answer












share|improve this answer



share|improve this answer










answered 3 hours ago









Jo.

2214




2214












  • That looks pretty good—better than I've done, at least.
    – Hugh
    3 hours ago




















  • That looks pretty good—better than I've done, at least.
    – Hugh
    3 hours ago


















That looks pretty good—better than I've done, at least.
– Hugh
3 hours ago






That looks pretty good—better than I've done, at least.
– Hugh
3 hours ago












up vote
4
down vote













As Jo has already shown, this can be accomplished in




28 steps. This is minimal, and it can be proven.




To help visualize this problem, we can imagine:




A two-dimensional grid/chart where each point is a number of the form $3^x2^y$, with $(x,y)$ as the relevant co-ordinates. We want to find a path from $(1,9)$ to $(0,0)$ while making only one step up/down/left/right at a time, and ensuring that the numbers we step on have their most significant digit in the set {1,3,4,9}.

Here is what the chart looks like for the range $(0,0)$ to $(10,10)$. The dashes represent numbers that do not begin with {1,3,4,9}, and so are unusable in our path.
1024 3072 9216 ---- ---- ---- ---- ---- ---- ---- ---- .
---- 1536 4608 13824 41472 124416 373248 1119744 3359232 10077696 30233088 .
---- ---- ---- ---- ---- ---- 186624 ---- 1679616 ---- 15116544 .
128 384 1152 3456 10368 31104 93312 ---- ---- ---- ---- .
---- 192 ---- 1728 ---- 15552 46656 139968 419904 1259712 3779136 .
32 96 ---- ---- ---- ---- ---- ---- ---- ---- 1889568 .
16 48 144 432 1296 3888 11664 34992 104976 314928 944784 .
---- ---- ---- ---- ---- 1944 ---- 17496 ---- 157464 472392 .
4 12 36 108 324 972 ---- ---- ---- ---- ---- .
---- ---- 18 ---- 162 486 1458 4374 13122 39366 118098 .
1 3 9 ---- ---- ---- ---- ---- ---- 19683 ---- .

From here, we can see two different routes of 28 steps each: (1536->373248->93312->384->48->3888->972->36->9->1) and (1536->373248->46656->3779136->944784->3888->972->36->9->1).




Proving minimality:




Since a path of length 28 exists (we've found two), we can rule out anything that's too far away to be used in a shortest path.

Moving from (1,9) to (0,0) must take at least ten steps on its own, so we can move at most nine steps completely out of the way (and nine steps back) in a shortest route. That limits us to only considering x-coordinates up to 10; any further would require making at least ten '*3' steps, eleven '÷3' steps, and at least nine '÷2' steps, putting the route definitely longer than 28.

With our x-coordinate limited to [0,10], we now look at the bottlenecks.

It should be clear that any shortest route must start by going from 1536 to 93312 in seven steps, and must end by going from 3888 to 1 in nine steps. These are both forced by unique bottlenecks; there is only one way to step from $(x,7)$ to $(x,6)$ and only one way to step from $(x,3)$ to $(x,2)$ in this range.

This leaves at most twelve steps to go from 93312 to 3888. Either by observation or by pointing out that there are only two ways to go from $(x,6)$ to $(x,5)$, we can see that there are exactly two shortest routes from 93312 to 3888, and both require all twelve steps.

Therefore, the shortest route is 28 steps, and there are exactly two ways to do so, both of which are described in Jo's solution and below the chart.







share|improve this answer





















  • Very nice grid; I like it.
    – Jo.
    2 hours ago















up vote
4
down vote













As Jo has already shown, this can be accomplished in




28 steps. This is minimal, and it can be proven.




To help visualize this problem, we can imagine:




A two-dimensional grid/chart where each point is a number of the form $3^x2^y$, with $(x,y)$ as the relevant co-ordinates. We want to find a path from $(1,9)$ to $(0,0)$ while making only one step up/down/left/right at a time, and ensuring that the numbers we step on have their most significant digit in the set {1,3,4,9}.

Here is what the chart looks like for the range $(0,0)$ to $(10,10)$. The dashes represent numbers that do not begin with {1,3,4,9}, and so are unusable in our path.
1024 3072 9216 ---- ---- ---- ---- ---- ---- ---- ---- .
---- 1536 4608 13824 41472 124416 373248 1119744 3359232 10077696 30233088 .
---- ---- ---- ---- ---- ---- 186624 ---- 1679616 ---- 15116544 .
128 384 1152 3456 10368 31104 93312 ---- ---- ---- ---- .
---- 192 ---- 1728 ---- 15552 46656 139968 419904 1259712 3779136 .
32 96 ---- ---- ---- ---- ---- ---- ---- ---- 1889568 .
16 48 144 432 1296 3888 11664 34992 104976 314928 944784 .
---- ---- ---- ---- ---- 1944 ---- 17496 ---- 157464 472392 .
4 12 36 108 324 972 ---- ---- ---- ---- ---- .
---- ---- 18 ---- 162 486 1458 4374 13122 39366 118098 .
1 3 9 ---- ---- ---- ---- ---- ---- 19683 ---- .

From here, we can see two different routes of 28 steps each: (1536->373248->93312->384->48->3888->972->36->9->1) and (1536->373248->46656->3779136->944784->3888->972->36->9->1).




Proving minimality:




Since a path of length 28 exists (we've found two), we can rule out anything that's too far away to be used in a shortest path.

Moving from (1,9) to (0,0) must take at least ten steps on its own, so we can move at most nine steps completely out of the way (and nine steps back) in a shortest route. That limits us to only considering x-coordinates up to 10; any further would require making at least ten '*3' steps, eleven '÷3' steps, and at least nine '÷2' steps, putting the route definitely longer than 28.

With our x-coordinate limited to [0,10], we now look at the bottlenecks.

It should be clear that any shortest route must start by going from 1536 to 93312 in seven steps, and must end by going from 3888 to 1 in nine steps. These are both forced by unique bottlenecks; there is only one way to step from $(x,7)$ to $(x,6)$ and only one way to step from $(x,3)$ to $(x,2)$ in this range.

This leaves at most twelve steps to go from 93312 to 3888. Either by observation or by pointing out that there are only two ways to go from $(x,6)$ to $(x,5)$, we can see that there are exactly two shortest routes from 93312 to 3888, and both require all twelve steps.

Therefore, the shortest route is 28 steps, and there are exactly two ways to do so, both of which are described in Jo's solution and below the chart.







share|improve this answer





















  • Very nice grid; I like it.
    – Jo.
    2 hours ago













up vote
4
down vote










up vote
4
down vote









As Jo has already shown, this can be accomplished in




28 steps. This is minimal, and it can be proven.




To help visualize this problem, we can imagine:




A two-dimensional grid/chart where each point is a number of the form $3^x2^y$, with $(x,y)$ as the relevant co-ordinates. We want to find a path from $(1,9)$ to $(0,0)$ while making only one step up/down/left/right at a time, and ensuring that the numbers we step on have their most significant digit in the set {1,3,4,9}.

Here is what the chart looks like for the range $(0,0)$ to $(10,10)$. The dashes represent numbers that do not begin with {1,3,4,9}, and so are unusable in our path.
1024 3072 9216 ---- ---- ---- ---- ---- ---- ---- ---- .
---- 1536 4608 13824 41472 124416 373248 1119744 3359232 10077696 30233088 .
---- ---- ---- ---- ---- ---- 186624 ---- 1679616 ---- 15116544 .
128 384 1152 3456 10368 31104 93312 ---- ---- ---- ---- .
---- 192 ---- 1728 ---- 15552 46656 139968 419904 1259712 3779136 .
32 96 ---- ---- ---- ---- ---- ---- ---- ---- 1889568 .
16 48 144 432 1296 3888 11664 34992 104976 314928 944784 .
---- ---- ---- ---- ---- 1944 ---- 17496 ---- 157464 472392 .
4 12 36 108 324 972 ---- ---- ---- ---- ---- .
---- ---- 18 ---- 162 486 1458 4374 13122 39366 118098 .
1 3 9 ---- ---- ---- ---- ---- ---- 19683 ---- .

From here, we can see two different routes of 28 steps each: (1536->373248->93312->384->48->3888->972->36->9->1) and (1536->373248->46656->3779136->944784->3888->972->36->9->1).




Proving minimality:




Since a path of length 28 exists (we've found two), we can rule out anything that's too far away to be used in a shortest path.

Moving from (1,9) to (0,0) must take at least ten steps on its own, so we can move at most nine steps completely out of the way (and nine steps back) in a shortest route. That limits us to only considering x-coordinates up to 10; any further would require making at least ten '*3' steps, eleven '÷3' steps, and at least nine '÷2' steps, putting the route definitely longer than 28.

With our x-coordinate limited to [0,10], we now look at the bottlenecks.

It should be clear that any shortest route must start by going from 1536 to 93312 in seven steps, and must end by going from 3888 to 1 in nine steps. These are both forced by unique bottlenecks; there is only one way to step from $(x,7)$ to $(x,6)$ and only one way to step from $(x,3)$ to $(x,2)$ in this range.

This leaves at most twelve steps to go from 93312 to 3888. Either by observation or by pointing out that there are only two ways to go from $(x,6)$ to $(x,5)$, we can see that there are exactly two shortest routes from 93312 to 3888, and both require all twelve steps.

Therefore, the shortest route is 28 steps, and there are exactly two ways to do so, both of which are described in Jo's solution and below the chart.







share|improve this answer












As Jo has already shown, this can be accomplished in




28 steps. This is minimal, and it can be proven.




To help visualize this problem, we can imagine:




A two-dimensional grid/chart where each point is a number of the form $3^x2^y$, with $(x,y)$ as the relevant co-ordinates. We want to find a path from $(1,9)$ to $(0,0)$ while making only one step up/down/left/right at a time, and ensuring that the numbers we step on have their most significant digit in the set {1,3,4,9}.

Here is what the chart looks like for the range $(0,0)$ to $(10,10)$. The dashes represent numbers that do not begin with {1,3,4,9}, and so are unusable in our path.
1024 3072 9216 ---- ---- ---- ---- ---- ---- ---- ---- .
---- 1536 4608 13824 41472 124416 373248 1119744 3359232 10077696 30233088 .
---- ---- ---- ---- ---- ---- 186624 ---- 1679616 ---- 15116544 .
128 384 1152 3456 10368 31104 93312 ---- ---- ---- ---- .
---- 192 ---- 1728 ---- 15552 46656 139968 419904 1259712 3779136 .
32 96 ---- ---- ---- ---- ---- ---- ---- ---- 1889568 .
16 48 144 432 1296 3888 11664 34992 104976 314928 944784 .
---- ---- ---- ---- ---- 1944 ---- 17496 ---- 157464 472392 .
4 12 36 108 324 972 ---- ---- ---- ---- ---- .
---- ---- 18 ---- 162 486 1458 4374 13122 39366 118098 .
1 3 9 ---- ---- ---- ---- ---- ---- 19683 ---- .

From here, we can see two different routes of 28 steps each: (1536->373248->93312->384->48->3888->972->36->9->1) and (1536->373248->46656->3779136->944784->3888->972->36->9->1).




Proving minimality:




Since a path of length 28 exists (we've found two), we can rule out anything that's too far away to be used in a shortest path.

Moving from (1,9) to (0,0) must take at least ten steps on its own, so we can move at most nine steps completely out of the way (and nine steps back) in a shortest route. That limits us to only considering x-coordinates up to 10; any further would require making at least ten '*3' steps, eleven '÷3' steps, and at least nine '÷2' steps, putting the route definitely longer than 28.

With our x-coordinate limited to [0,10], we now look at the bottlenecks.

It should be clear that any shortest route must start by going from 1536 to 93312 in seven steps, and must end by going from 3888 to 1 in nine steps. These are both forced by unique bottlenecks; there is only one way to step from $(x,7)$ to $(x,6)$ and only one way to step from $(x,3)$ to $(x,2)$ in this range.

This leaves at most twelve steps to go from 93312 to 3888. Either by observation or by pointing out that there are only two ways to go from $(x,6)$ to $(x,5)$, we can see that there are exactly two shortest routes from 93312 to 3888, and both require all twelve steps.

Therefore, the shortest route is 28 steps, and there are exactly two ways to do so, both of which are described in Jo's solution and below the chart.








share|improve this answer












share|improve this answer



share|improve this answer










answered 3 hours ago









ManyPinkHats

5,70012544




5,70012544












  • Very nice grid; I like it.
    – Jo.
    2 hours ago


















  • Very nice grid; I like it.
    – Jo.
    2 hours ago
















Very nice grid; I like it.
– Jo.
2 hours ago




Very nice grid; I like it.
– Jo.
2 hours ago


















draft saved

draft discarded




















































Thanks for contributing an answer to Puzzling Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f76356%2fdoubling-tripling-puzzle-make-1-from-1536-in-as-few-steps-as-possible%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

Calculate evaluation metrics using cross_val_predict sklearn

Insert data from modal to MySQL (multiple modal on website)