DVDs moves

1-0

2-0

3-1

4-2

**Edited by BMAD, 22 July 2013 - 05:33 AM.**

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

Guest Message by DevFuse

Started by BMAD, Jul 20 2013 05:43 AM

39 replies to this topic

Posted 22 July 2013 - 05:31 AM

Consider completing the table, maybe a pattern will form:

DVDs moves

1-0

2-0

3-1

4-2

DVDs moves

1-0

2-0

3-1

4-2

**Edited by BMAD, 22 July 2013 - 05:33 AM.**

Posted 22 July 2013 - 08:29 AM

Spoiler for Totally guessing now

**Edited by gavinksong, 22 July 2013 - 08:31 AM.**

Posted 22 July 2013 - 01:30 PM

Spoiler for Totally guessing now

Are you sure we are rounding up? and of course we are ignoring the trivial cases of 1 dvd and 2 dvds.

**Edited by BMAD, 22 July 2013 - 01:31 PM.**

Posted 23 July 2013 - 04:17 AM

Spoiler for Totally guessing now

Are you sure we are rounding up? and of course we are ignoring the trivial cases of 1 dvd and 2 dvds.

Yeah, it doesn't match the pattern for 1 to 3 DVDs.

But here, try to reorder this in less than six moves:

BADCFKEHGJI

If you can, then maybe we are supposed to round down. The problem is that I don't know whether it is a lack of skill on my part that I can't unscramble in less than ceil(N/2) or if that is the true answer.

I am curious as to how this turns out. Hopefully, some of the great minds of Brainden put their heads together and come up with a solution.

**Edited by gavinksong, 23 July 2013 - 04:25 AM.**

Posted 23 July 2013 - 05:13 AM

I never said you were wrong about rounding up. I was just pointing out an apparent contradiction in my chart and your answer. Perhaps Dvds 1-4 is trivial and the round up principle starts at five,,,

checking n=5, ABCDE

scrambled as BAEDC

AEDCB

EDCBA (two moves)

scrambled as BEADC

EADCB

EDCBA (two moves)

scrambled as BADEC

ABDEC

ABCDE (two moves)

scrambled as ABEDC

ABCED

ABCDE (two moves)

now i did not exhaust all of the possible arrangements of five nor do i claim that i found the worst case scenario but it does appear to only take two moves. So is there a point where it switches from n/2 (round down if decimal) to n/2 (round up if decimal) or is eleven purely unique? and if it is unique, why is it unique?

**Edited by BMAD, 23 July 2013 - 05:15 AM.**

Posted 23 July 2013 - 05:25 AM

Spoiler for one possible approach

Posted 24 July 2013 - 03:37 AM

I never said you were wrong about rounding up. I was just pointing out an apparent contradiction in my chart and your answer. Perhaps Dvds 1-4 is trivial and the round up principle starts at five,,,

checking n=5, ABCDE

scrambled as BAEDC

AEDCB

EDCBA (two moves)

scrambled as BEADC

EADCB

EDCBA (two moves)

scrambled as BADEC

ABDEC

ABCDE (two moves)

scrambled as ABEDC

ABCED

ABCDE (two moves)

now i did not exhaust all of the possible arrangements of five nor do i claim that i found the worst case scenario but it does appear to only take two moves. So is there a point where it switches from n/2 (round down if decimal) to n/2 (round up if decimal) or is eleven purely unique? and if it is unique, why is it unique?

You are absolutely right.

In fact, I do remember trying to arrange 5 in a way that would require 3 moves when we were trying to reach the n-2 upper bound.

I suppose it changes starting at 6, but I am hard pressed to find an acceptable explanation.

We may have to resort to a programming solution as you said.

One idea would include create an array of length n! which is to contain the fastest possible solutions (# of steps) corresponding to each lexical permutation of 123...n, and a function which hashes permutations to the correct indices on the array. Then, iterate through the permutations, conducting a breadth first search on each unsolved item which terminates when 1234 or 4321 is found, and then filling in the solutions array for the current permutation as well as for all permutations encountered in the intermediate steps. Finally, take the max value of the solutions array.

We can do this!

It would be nice if this problem got the other members' attention. It is a rather challenging problem.

**Edited by gavinksong, 24 July 2013 - 03:37 AM.**

Posted 24 July 2013 - 04:47 AM

If it were to change it would have to change at an odd like 7 since 6 being even would result in n/2 changes, correct?

Posted 24 July 2013 - 04:50 AM

I find this question ironically intriguing as I was honestly just sorting 22 DVDs on two shelves and wondered, as I hope I am not the only nerd who does this, "is there an efficient algorithm for doing this?"

Posted 24 July 2013 - 07:42 PM

OP asks, what is the greatest number of moves?

The number of moves depends on the original degree of disorder and the choice of algorithm.

So it sounds like asking, for any starting order, what is the least efficient algorithm?

Or, what starting order is the most challenging for the best choice of algorithm?

I don't have an answer, but I found this page very interesting while thinking about it:

http://www.sorting-algorithms.com/

The number of moves depends on the original degree of disorder and the choice of algorithm.

So it sounds like asking, for any starting order, what is the least efficient algorithm?

Or, what starting order is the most challenging for the best choice of algorithm?

I don't have an answer, but I found this page very interesting while thinking about it:

http://www.sorting-algorithms.com/

*Vidi vici veni.*

0 members, 0 guests, 0 anonymous users