This is a fun question, and a great image. The paradox is, of course, that his nose only grows when he lies. So if his nose grows, then he was telling the truth, and his nose would not grow, so then he would be lying - and we're in an infinite loop of self-contradiction.
This question is an example of a famous paradox (question or situation that leads to an unsolvable contradiction) that is very important in the origins of post-modern philosophy. Kurt Goedel used this one: The barber of a small town shaves every man who does not shave himself. Who shaves the barber. If the barber shaves himself, then he is the barber, and he doesn't shave himself.
Goedel used this paradox to generate his famous Goedel's incompleteness theorem. This theorem was one of two philosophical events (along with the Heisenberg Uncertainty Principle) that brought an end to Modernism. It showed that we can never fully describe a consistent picture of the universe.
Now I know: Goedel could have used Pinocchio!