If you are guessing with an odd range (e.g. 5), always make sure that after you choose there are two even numbers ranges left for your opponent. There will be in total 4 numbers left, but you can split them oddly (1-3) or evenly (0-4 or 2-2). Make sure you choose the even split.
For an even range, both players have 50% chance of winning with optimal play.
Proof:
There is a guaranteed 50% strategy for player 1: if you always take the penultimate number in the range N, either this number is correct (you win), the final number in the range is correct (you lose with same probability), or you get to go again with an even range, and can repeat the tactic.
There is also a guaranteed 50% strategy for player 2: choose the neighbour of the number taken by player 1 to leave two even ranges. For example, with 1-10, if player 1 takes nr. 3, you take nr. 4 (with same probability of winning directly), leaving ranges 1-2 and 5-10, both which are even, and you can repeat the tactic to always have 50% chance.
There is also a guaranteed 50% strategy for player 1: if you always take the penultimate number in the range N, either this number is correct (you win), the final number in the range is correct (you lose with same probability), or the game continues with an even range, with the other player to move, at which point you can use the player 2 strategy to ensure a 50% chance.
By guessing a number that forces your opponent into one of two even ranges you get one free guess, and after that, given optimal play, it's a coin toss (apologies for the mixed metaphor).
For your case with a range of 5, you can choose:
- 21 : 0-4 split (good: even/even)
- 22: 1-3 split (bad: odd/odd)
- 23: 2-2 split (good)
- 24: 3-1 split (bad)
- 25: 4-0 split (good)
So if the range is N and an an odd number, and you leave your opponent two even ranges, then your probability of winning overall is
$$P = 1/N + (1-1/N) * 1/2$$ $$P = 1/2 + 1/(2N)$$
So for the range of 5, that gives $P= 1/2 + 1/10 = 3/5$, as found by Emrakul and f''.