Fox Hunting

[•Cosmin]

http://infoarena.ro/blog/fox-hunting

[•wefgef]

Isn't this just a particular case for this problem: http://infoarena.ro/problema/boom?

[•Cosmin]

I said don't spoil it

That problem asks for the minimum number of steps while I ask for a strategy.
You can solve this one in your head and also generalize to higher n. In the problem you mention the solution is exponential.

[•freak93]

Isn't it just enough to check all holes from first to last twice?(Like 1 2 3 4  .... 11 1 2 3 ... 11)

[•mips]

If the holes are numbered from 0 to 10, first assume that the fox is in an odd numbered hole(let's call "F" the position of the fox). F switches between even and odd every step that the fox makes.
Since now F is odd, it can't be 0, so we check hole 1. If F != 1, F must have been one of 3,5...9, so in the next step we are certain that F will be at least 2. We check further in hole 2. If F!=2, then F certainly is one of 4,6,8,10 so F will be bigger than 2 in the next step. And so on until we reach hole 9. If F!=9 we have reached a contradiction( if our assumption was correct, in this point F should be odd, but we are also certain F >9). Then F must have been an even number initially. But 9 steps have passed, so F must be odd now. We repeat the whole process, being certain that this time we will find the fox.
18 steps are needed in worst-case.

[•PetcuIoan]

You made a error : it's feel free not fell free.

[•elfus]

Does the fox know what you checked last time? I mean does the fox chooses next possibility random or based of an optimal strategy depending of your last move?

[•klamathix]

@Florin. It doesn't really matter. You have to devise a strategy that will certainly succeed, which basically means that you should take into account any possible outcome, including the case in which the fox acts or seems to act based on your previous movements. It's not relevant if it's choice or randomness, it's a case you should consider anyway.

@Petcu You made an error. It's 'an' error, not 'a' error .

[•PetcuIoan]

@Mihai, are you shure? I think my english is in an fine state.

[•Cristy94]

I have made a small javascript app for those who want to check their solution in a visual way
Have fun: http://jsfiddle.net/hncnn/18/

[•teo2mirce]

@Budau Adrian

You'r method work only for 92% of the time i tried it 10 milion times in an application.

[•veleandu]

Adi's solution works fine
And you only need to check the holes from 2...10 and 2...10
It's the same solution that Mircea told ... But in a very short. I will come shortly with an example. You can generate all the positions that the fox could be possible in, in you will see that after going those steps the fox can't be anywhere

[•Jogu]

it's all about the parity of the fox position.

1) if you and the fox have the same parity then starting from 1 going to end(in one step), you will meet the fox surely somewhere.

2) if you have different parity from the fox, then going from 1 to end you will not meet the fox for sure. that means, at the end of the line, you will know the parity of the fox position(is different from your parity) and you will find it for sure(because now you use the first case).

[•crushack]

I think the solution is:
Suppose we have the holes numbered from 1 to N
so we check holes 2..N-1 then N-1..2
and it works

Tried it on paper

[•toranagah]

I have found the solution of iterating through hole 2-10 twice(I read the comments after and saw the other similar response). Don't know if it is truly correct but I tried it against 10 billion random tests and it worked for every single one.

[•Cosmin]

Testing on random movements is a bad idea.

For example the following hunting strategy:
1 1 1 1 ... 1 ..
catches the fox at some point because the probability of a point moving randomly to the left or right reaching the first position is 1.
But this strategy is obviously wrong because the fox can get away from the hunter if she just doesn't go to hole 1.

The people above mentioning the even odd strategy have the right solution.

[•crushack]

I admit the even odd solution to be correct, but you don't have to bother with that:
if you check all the holes from 2 to N-1 then you'll be left with the fox on an even number (if the number is odd) or on an odd number (if the number is even). But, if you take them from N-1 to 2 you don't have to bother with even odd case, because if N is even then N-1 is odd and the other way around.

Thank you for your patience