11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are you sure that this has an unique solution? $\endgroup$ – Victor Stafusa Dec 7 '14 at 9:50
  • 1
    $\begingroup$ Ok then, sorry for that. $\endgroup$ – Victor Stafusa Dec 7 '14 at 9:59
  • 1
    $\begingroup$ OK.... so then why isn't the answer just to check each case except the ones you've already checked (checking them in any order, so long as you only check each case once) until you find it? $\endgroup$ – A E Dec 7 '14 at 10:20
  • 1
    $\begingroup$ @CJDennis Just to check I haven't gotten this wrong, say you watched the first movie you ever watched. Then DVD 1 is in the player and case 1 is empty. Then when you watch the second movie, DVD 1 goes into case 2, DVD 2 goes into the player and case 1 is still empty. As far as I can tell, won't case 1 always remain empty? $\endgroup$ – Sp3000 Dec 7 '14 at 11:14
  • 1
    $\begingroup$ It affects what I was going to post. If you didn't specify that I had a post prepared saying Four Weddings and a Funeral was the first thing you ever watched (and more) ;) $\endgroup$ – Sp3000 Dec 7 '14 at 11:27
15
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ But then I'd have to put the file back in the right directory after I'd watched it... $\endgroup$ – CJ Dennis Dec 8 '14 at 1:27
  • 1
    $\begingroup$ Why is this faster than opening cases is any other order (until you find The Life of Pi)? $\endgroup$ – Julian Rosen Dec 8 '14 at 4:36
  • $\begingroup$ @JulianRosen I have created a chat room to discuss this: chat.stackexchange.com/rooms/info/19275/… $\endgroup$ – CJ Dennis Dec 8 '14 at 6:42
  • $\begingroup$ It's a clever solution. Worst case the amount of cases to be opened is still close to n (or even N) but the odds of that worst case are severely limited. $\endgroup$ – Weckar E. Nov 16 '16 at 10:01
2
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ In this problem, we only know about one disc that's in another loop, so $z=n-1$. It's not clear that this strategy is faster than checking all of the cases except Four Weddings and a Funeral (and if the other discs are distributed randomly among the cases, this won't be any faster) $\endgroup$ – Julian Rosen Dec 8 '14 at 16:10
  • $\begingroup$ @JulianRosen Indeed, I did not intend to contest that what you say is not true. In fact, what I say out right implies this. Notice that the accepted answer is the same as this strategy. Now, the point is that it's better than random because z < n (note: $z=n-1 \rightarrow z<n$), but yes, if you know what the loop is (and in this case you DO, by excluding Four Wedding and a Funeral) then you may as well check them in any order you like $\endgroup$ – d'alar'cop Dec 8 '14 at 16:15
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This is not a derangement because I mentioned that Four Weddings and a Funeral was in the right case before I watched it. $\endgroup$ – CJ Dennis Dec 7 '14 at 9:58
-4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I don't give downvotes but I would explain them like so: 1. I specifically said no lateral thinking, logic only. 2. The amount of time required to organise your solutions would not be optimal! $\endgroup$ – CJ Dennis Dec 8 '14 at 1:26
  • $\begingroup$ @CJDennis fair enough. Point 1 is clear and having read the accepted answer I agree to 2 as well. $\endgroup$ – BmyGuest Dec 8 '14 at 6:03

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.