This is the "Barber for a Day" problem from Raymond Smullyan's To Mock a Mockingbird.
A certain town contained exactly 365 male inhabitants. During one year, which was not a leap year, it was agreed that on each day one man would be official barber for the day. No man served as official barber for more than one day. Also, the official barber on a given day was not necessarily the only person who shaved people on that day; nonbarbers could also do some shaving.
Now, it is given that on any day, the official barber for that day–call him X–shaved at least one person. Let X* be the first person shaved by X on the day when X was official barber. We are also given that for any day D, there is a day E such that for any male inhabitants X and Y, if X shaved Y on day E, then X* shaved Y on day D.
Now, the above conditions certainly lead to no paradox, but they do lead to an interesting conclusion, namely that on each day at least one person shaved himself. How do you prove this?
Wouldn't a counterexample for the proof be simply that one barber gets shaved every single day of the year? For example, if the first official barber was shaved every day, this would, as far as I can tell, meet all of the given conditions: at least one person is shaved and there exists a day D for each day E where X* shaves Y (the first day).
As an example, consider the case of two barbers on two days (let -> indicate person on left cuts hair of person on right):
Day 1:
B1 -> B1
Day 2:
B2 -> B1
For each day D, there exists some day E where x* shaved all the people of that day. For both days, that is Day 1. Day 2 does not contain a person who shaved himself. This pattern holds for any equal number of barbers and days which invalidates what we are trying to prove.
Best Answer
Your counterexample does not rule out the possibility that each day a man shaves himself: you only want the official barber to be shaved, but what about the other men? We know nothing about them with your example. But we still know the official barber has to shave at least one man.
Take any day $D$ and a corresponding day $E$ (guaranteed to exist by the constraint). The condition is valid for all $X,Y$ on day $E$ (such that $X$ shaves $Y$), so take $X$ to be the official barber of day $E$: we know he shaves at least one person. And take $Y$ to be the first such person.
Then since $X$ shaves $Y$ on day $E$, the condition means that $X^*$ shaves $Y$ on day $D$. But $X^*$ is obviously $Y$ (since a person is the official barber exactly one day of the year, and we chose $X$ to be the official barber of day $E$), so $Y$ shaves $Y$ on day $D$.
That is, on each day $D$, we can find an $Y$ such that $Y$ shaves himself on day $D$.