A man and a woman were the only two people walking along a beach. "I'm a man," said the one with the black hair. "I'm a women," said the one with the red hair. At least one of them was lying. What was the color of the woman's hair?
How do I know this? Well you know there is a man and a woman. You also know that at least one of them is lying.
That means that if the one with black hair is a lier than it's a woman, but that would mean the red haired one is a man.
What if the red-haired one was lying, that means that he's a man, which means that the other one must be a woman.
In both cases, the one with black hair is the woman.
Which means they're both lying.