find osama hiding in a cave

I read this puzzle a while back but was unable to solve it.

I have recently been going on a string of interviews and chanced upon the same puzzle again.
This time I sat down with a pen and paper, this is what I've got.

The Puzzle:
Osama is hiding in a series of interconnected caves, there are 15 of them in all numbered
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

Every day you are allowed to go into any one cave of your choosing and find osama. If you do not find him, you may only try again the following day.

Every night osama will move either to the right or to the left of the current cave he is in, but if he were in cave 1 or cave 15 he may only move 1 cave towards the center.
Eg: 4 -> 5 or 4 -> 3
15 -> 14
1 -> 2

Objective:
Name a series of cave visits that will definitely find osama or if there exists no such series prove it.

This puzzle is challenging and you should try it before proceeding down to the solution.









Solution:
Suppose we reduce the problems down to 1 cave, the obvious solution is 1

2 cave
the solution would be 1,1

3 cave
the solution would be 2,2

4 cave
the solution would be 2,3,3,2

5 caves, this is where it became too challenging to do it mentally,
the solution required a pen and paper and some efficient form of representation
By the way the solution is 2,3,4,2,3,4


you might want to verify this solution and arrive at your own form of representation.





















This is my representation:

Day	Possible locations of osama	Our choice of cave	Possible locations of osama after visit
1	1,2,3,4,5	2	1,3,4,5
2	2,3,4,5	3	2,4,5
4	1,3,4,5	4	1,3,5
5	2,4	2	4
6	3,5	3	5
7	4	4	FOUND

what about the solution for 15 caves? Why don't you do it and tell me.


How about writing a generic algorithm for n caves?