# Find The Puppy

There are 5 boxes with lids kept in a row.

`[] [] [] [] []`

Let’s call them B[1…5].

There is a puppy P inside one of these boxes.

Our goal is to find the puppy.

`[?] [?] [?] [?] [?]`

Every morning you get a chance to open any one of the boxes. If you find the puppy: great, congrats!

If you don’t, tough luck, you have to wait again for the next day. Meanwhile, during the night, the Puppy will move to one of the neighbouring boxes.(can’t stay in same box). Eg:

`[] [P] [] [] [] -> [P] [] [] [] [] or [] [] [P] [] [].`

- Does there exist protocols (ways of opening boxes) in which I can guarantee that I can catch the puppy in a finite time?
- If yes, what is the smallest number of days I have to wait to catch the puppy (Which is the best protocol?)
- How does this protocol work?

Unresolved questions:

Can we do this in five days? Or can we show that it’s impossible to come up with a protocol that uses only five days?

What about six boxes? Or seven? Or n?

If the moves are equiprobable and the initial choice is uniformly random, what is the expected number of moves executed by either of the strategies above?

How much faster can we do this if we are allowed to open two boxes at once?

Question from Bireswar: If the puppy is allowed to stay put, then there’s no protocol to find the puppy even in the trivial setting with two boxes. What if we are allowed to open more than one box? How many more boxes do we need to be able to open per day to catch a potentially non-moving puppy amongst five boxes?