Help me find my favourite DVD

Question

I have an admission to make: I very rarely put my DVDs back in the case they came from. Whenever I watch a new DVD I just put whatever DVD is the player in the new case. I put the cases back on the shelf wherever they'll fit without worrying about any sort of order. My collection is very disorganised! Now I want to watch my favourite movie The Life of Pi but I have no idea which case I put it back in! The right case has The Fifth Element in it. I've tried opening a few cases at random but I have so many it's going to take me forever! I know I've watched it fairly recently, I just can't remember which case I put it back into or all of the DVDs I have recently watched. The DVD currently in the player is Four Weddings and a Funeral and its case is empty (it happened to be in the right case before I watched it).

Sometimes, when people come over, I tidy the house, which means I take the DVD out of the player, stick it into the empty case and put it back on the shelf. And sometimes I put the DVD into the already empty case regardless of whether it's the right one or not (when I select a new DVD I briefly have two empty cases. The old DVD might end up in either of them, but usually the new case). I don't really have a system which is why they're so jumbled.

I'm not going to buy another copy, I don't belong to a video library, none of my friends have it and my internet is too slow to download it. I only have one DVD player. I know the DVD is in the wrong case somewhere on my shelf. I must find it in my own collection as quickly as possible! How can I do it?

This is a logic puzzle. It is not a trick question. It does not rely on an obscure interpretation of certain words or lateral thinking to get around any conditions. I believe I have given sufficient clues to be able to answer the question but I will be happy to clarify any points. I don't believe I need to provide any extra clues.

Answer 1

All of your DVDs are in n rings, where n >= 2 (Four Weddings And a Funeral is in a ring of length 1). So if you open a DVD at random, it may or may not be in the ring that contains The Life Of Pi.
However, we do know one movie that is in the same ring as The Life Of Pi. It is The 5th Element. So if you start with The 5th Element's case, you are guaranteed to be in the ring that contains The Life Of Pi.

You should really consider getting yourself a NAS and a copy of Plex (or other similar software), so that you can stream your movies locally and avoid this problem in the future.

Answer 2

Take the DVD cases to be indices of the array elements in the following explanation. Let the DVDs themselves to be the values in the array elements.

Let us establish the means by which this problem may be solved:

Take the array $C = [1,\cdots,n]$. It contains each integer from $1$ to $n$ and is of size $n$. Consider any permutation of the elements of $C$. There are $n!$ ways $C$ can be shuffled. We have a searching algorithm which is to find $1$.

Start with checking in $C[1]$.
If $C[1] = 1$ then we have found $1$ in $1$ check.
If $C[1] = x$ where $x\not=1$ then we check $C[x]$. If $C[x] = 1$ then we have found $1$ in $2$ checks.
If $C[x] = y$ where $y\not=1$ then we check $C[y]$. If $C[y] = 1$ then we have found $1$ in $3$ checks.
If $C[y] = z$ where $z\not=1$ then we check $C[z]$.
This process can be continued and it forms a chain. Clearly, $x \not= y \not= z$ - so long as $C[i] \not= 1$, no number previously encountered will be repeated ($Lemma1$). The claim is that this chain will include $1$ because we started with $C[1]$.

The proof is by contradiction. Assume that $1$ is somewhere outside the chain.

Recall that $|C|=n$. Start from $C[1]$. Clearly, any chain including every element of $C$ will include $1$. We must be looking for a chain of size less than $n$. Such a chain must moreover be a loop - otherwise it must continue and consume all elements of $C$, and $n$ is finite. Therefore, we know that we are looking for a loop starting from $C[1]$ which does not contain $1$. A loop is a chain of length $z$ where the last element visited contains the value contained in the first element visited. By $Lemma1$ given a loop of length $z$, the loop must involve $z$ elements and only the values being the indices of the elements. So, a loop, in order to arrive again at $C[1]$ must have included $1$. Contradiction.

As to the concerns of efficiency, in particular, to defeating randomly checking:

If we add one constraint (which may exist in many forms), that the loop in which the target, $1$, can be found, is smaller than $n$, then we can guarantee better than random chance performance.

Randomly checking has a worst-case runtime of $n$ checks.

We can constrain the loop housing $1$, $L$, which will be of size $z$, to have $z < n$ by simple asserting that there is a guarantee that some of the elements have not been moved - or that there exists a loop outside $L$. NB: These constraints/guarantees are equivalent since is an element has not been moved then it is a loop of size $1$.

Checking $L$ as described above has a worst-case runtime of $z$ checks.

Since $z < n$ this strategy is "better".

Answer 3

It's a matter of Derangements (arrangements that map each dvd to a case ,other than its own) It is an "NP-complete" problem (that means HARD) to determine whether a given permutation group (described by a given set of permutations that generate it n! for n cases and n DVD's) contains any derangements http://en.wikipedia.org/wiki/Derangement

Answer 4

I know this is a logical puzzle so the following answer is not what you're looking for, but I think it is a valid answer if lateral thinking is allowed.

Put the following announcement into a (free) newspaper / online-blog etc.:
"Free video rental for the curious! Feel bored? Are your ready to try something unexpected ? I'm giving out (lending!) DVDs for free - for a limited time only. And this is how it works: You come by my place (see Google-map below) and I'll hand you out a random DVD case with a random DVD inside! No guarantees whatsoever about the content - but all my films are best quality mainstream films (no porn). You've a 24hrs period to watch and return the DVD, and the only condition: You have to tell the title of the film you've watched.

Now simply wait and the problem will solve itself. Is it the fastest solution? I don't know yet as no other answer has been posted. It will depend on the size of you library though, because it scales. The bigger your library, the better my solution in comparison!

Of course there would be a faster alternative:

Invite all your friends (or trustworthy people you know) for a "picke & watch" DVD evening. Everybody may come and take (borrow!) as many DVD as he likes except the one you want to watch for yourself. Condition: Open the DVD case at once and check.