Ι will reduce my choice to two sequences. One is from 1 to 8 and the other from 9 to 16. By choosing one of the two my chances are 7/8. If I choose the whole sequence my chances are 7/16 so I will go for one sequence.

First I am going to separate the numbers into two groups. The first group has numbers from 1 to 8 and the second group has numbers from 9 to 16. My first question is ″ Does your number belong to group 1 or 2?″ If the answer is ″group 1″, then I will ask if the number is odd or even. If he says it is odd, then I know he lies because I have to ask 3 more questions to find the chosen number. So in total I asked 5 questions instead of 7. The alternative is that he tells me group 1 and won't say whether the number is even or odd, saying he will only answer for one number at a time: is it 1, is it 2, is it 3...? Then I have to ask 7 questions to find the chosen number. So in all I asked 7+1=8 questions. In both cases the man is lying.