This Robotic Arm Can Do Many Things, But Is Unable To Think For Itself

At a warehouse, robotic arms are responsible for retrieving boxes when an order is received from a customer. In one area of the warehouse, there is a stack of 6 boxes. Each box is a cube, and all the boxes have different sizes. The boxes are stacked from largest to smallest, with the largest box on the bottom.

When doing an inventory check, the warehouse foreman realizes that this stack of boxes is in the wrong spot. There are two empty spots to the right of this stack, and the boxes are supposed to be in the rightmost spot. The foreman programs the robotic arm to move the boxes from where there are now into the new stack. The robotic arm is only able to pick up one box at a time, and for safety reasons, it is never allowed to place any box on top of a smaller box, since it might fall off.

What is the smallest number of moves that the robotic arm must make in order to move the stack of boxes from its present location to where it is supposed to be?

63 6 36 11

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

12 solutions

William Cui
Jan 18, 2014

This problem is very similar to the Tower of Hanoi.

Let's first start by experimenting a bit.

In order to move the first box, there must be one move - you just move the box to another spot. However, in order to move the second box, you must move it to a different spot first, since you cannot place it on top of a smaller box, and then put the first box on top. To move the third box, you put it on a separate spot from the first two, move the first box to a separate spot, move the second box onto the third box, and move the first box back onto the second box.

If we continue this process, we will find that to move the n t h n^{th} box, we need to perform 2 n 1 2^{n-1} moves, and if we want to move n n boxes, we will need to perform 2 n 1 + 2 n 2 + + 2 2 + 2 1 + 2 0 = 2 n 1 2^{n-1}+2^{n-2}+\ldots+2^2+2^1+2^0 = 2^n - 1 total moves.

In this problem, we must move six boxes, so the total number of necessary moves is equal to 2 6 1 = 63 2^6-1=\boxed{63}\ \blacksquare

It never said that you can't use the left of the stack as temporary sports. With this flaw of the problem, I assume that you have infinite set of spots.

Elvis John Europa - 7 years, 3 months ago

Nice proof, Willy.

Noah Singer - 7 years, 4 months ago

Log in to reply

Thanks.

(Do you Noah Singer?)

William Cui - 7 years, 3 months ago

COOL

vaishnav garg - 7 years, 3 months ago

in my opinion this is perfect approch

razi ur rehman - 7 years, 4 months ago

Log in to reply

Thanks!

William Cui - 7 years, 4 months ago
Rahman 007
Jan 17, 2014

Tower Of Hanoi Problem..... solution is easy.... rules is: ways=2^n-1

Can you give a more detailed answer so I can understand why that equation applies?

Blas Rodríguez Irízar - 7 years, 4 months ago

Log in to reply

Tower of Hanoi

Priyanka Banerjee - 7 years, 4 months ago

Explanation can be given using functional equation. If it takes f(n) steps to solve for n, then (n+1)st step is, move all the n boxes kept previously to the empty space (f(n) steps), move the upper most box in the original pile to the empty place (= 1 step), and move n blocks back to this place where the new biggest block is placed (f(n)) steps. So f(n+1) = f(n) + 1 + f(n) = 2f(n) + 1. Solve for the functional equation, answer is 2^n - 1. Let me know if you get stuck in solving this functional.

Parag Arora - 7 years, 4 months ago

yeah I did the same way found the minimum no. of ways to solve 6 blocks in tower of hanoi

Varun Vijay - 7 years ago
Nico Stirling
Jan 17, 2014

1 box = 1, 2 boxes = 3, 3 boxes = 7, 4 boxes = 15

We can clearly see that each one is one bigger than twice the previous one. So we just continue this until we reach 6 boxes

5 boxes = 2(15)+1= 31, 6 boxes = 2(31)+1= 63

So 63 is the answer.

Give some explanation

Kushagra Jain - 7 years, 4 months ago

Log in to reply

Explanation can be given using functional equation. If it takes f(n) steps to solve for n, then (n+1)st step is, move all the n boxes kept previously to the empty space (f(n) steps), move the upper most box in the original pile to the empty place (= 1 step), and move n blocks back to this place where the new biggest block is placed (f(n)) steps. So f(n+1) = f(n) + 1 + f(n) = 2f(n) + 1. Solve for the functional equation, answer is 2^n - 1. Let me know if you get stuck in solving this functional.

Parag Arora - 7 years, 4 months ago
Milly Choochoo
Jan 17, 2014

I did the solutions for the same situation but with 2, 3, and 4 boxes, and guessed that the solution (minimum number of moves to stack the boxes to the rightmost space) for N N boxes could be modeled as:

2 N 1 = M 2^N - 1 = M

Where M M is the minimum number of moves necessary to stack the boxes to the rightmost space.

2 6 1 = 63 2^6 - 1 = \boxed{63}

I guess I just got lucky.

why cud we use this rule? can u pls explain?

Anik Bhattacharjee - 7 years, 4 months ago

Log in to reply

http://en.wikipedia.org/wiki/Tower of Hanoi#Recursive_solution

Daniel Wang - 7 years, 4 months ago
Noah Singer
Jan 24, 2014

This is equivalent to the Tower of Hanoi problem, in which discs are moved from one column to another with an empty "intermediate" column. If you look at the description, you see that the solution for the problem with n n discs (or in this case, n n boxes) are moved from one spot to another is 2 n 1 2^n - 1 moves. In the case of 6 boxes, 2 6 1 = 63 2^6 - 1 = \boxed{63} moves are required.

Parag Arora
Jan 20, 2014

This is a standard tower of Hanoi problem, the answer being 2^n - 1.

Deco Nggakada
May 28, 2014

dilihat dari struktur deret bilangan yang memiliki fungsi 2^n-1, 2^n-2,2^n-3......... 2^1, 2^0 maka rumus fungsi menjadi 2^n - 1 & subtitusi 6 pada n jadi jawabannya 63

This is just the Towers of Hanoi puzzle with 6 disks. The solution is 2^6 -1

Manoj Majumdar
Jan 25, 2014

It is a "Tower of Hanoi" problem in a subject called Data structures. It says, if you have to arrange the disks from a source to a destination (with one temporary spot needed), then you can do it in 2^n - 1 moves, where n=no. of disks.

Here instead of no. of disks, boxes are given. So substitute the number of boxes as n in the formula and calculate the answer. Ans. = 63

Razi Ur Rehman
Jan 21, 2014

it is never allow to place any box on top of smaller box but we can use the second vacant location to keep temporarily big box= and then replace all boxes in right manner according to given condition if let three is one object number of move =2^1 - 1=1 if n=2 number of move=2^2 - 1=3 if n=3 number of move=2^3 - 1=7 ......... n=6 number of move=2^6 - 1=63

Jawwad Zakaria
Jan 20, 2014

Classic Towers of Hanoi problem

Minimum number of moves required to solve for n boxes = 2 n 1 2^{n} - 1

Source: http://en.wikipedia.org/wiki/Tower of Hanoi

Rindell Mabunga
Jan 19, 2014

This problem is like the Tower of Hanoi in which you need to move a stack of discs in a peg into another peg. There are three pegs used and the same conditions are given. The minimum number of moves that can be made to move this stack of discs is 2 n 1 2^n - 1 where n is the number of discs. Therefore n = 6 and 2 6 1 = 63 2^6 - 1 = 63

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...