## Sunday, June 26, 2011

### liars and honest villagers

In a village, there are $n$ people who each has an ID number from 1 to $n$. Each person is either completely honest or a total liar. One day, a detective came to visit and interviewed them. This is what they told him:

If a person had an ID number $x$ where $x$ is even, he said:
"The person whose ID number is $x/2$ is honest"

If a person had an ID number $x$ where $x$ is odd and greater than one, he said:
"The person whose ID number is $(x-1)/2$ is a liar"

Person with ID number of 1 did not say anything.

If $L$ is the number of liars and $H$ is the number of honest villagers, find all possible values of $L-H$