2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I understand the problem to concern 365 male inhabitants who must be shaved every day of the year. Moreover the extra condition is not about existence of a day $D$, but a condition satisfied for every day $D$. $\endgroup$ – hardmath Nov 19 '18 at 6:28
  • 1
    $\begingroup$ @hardmath We don't even need that each man be shaved every day (unless it's another consequence of the constraints, which I didn't check as it's not necessary in this problem). $\endgroup$ – Jean-Claude Arbaut Nov 19 '18 at 7:29
  • $\begingroup$ @hardmath If I’m understanding your comment correctly, each man must be shaved each day? That would be sufficient in itself to prove that at least one man shaved himself each day (namely the official barber). $\endgroup$ – Billy the Kid Nov 19 '18 at 14:26
  • $\begingroup$ I don't think it is that simple. While the official barber for a day must shave at least one man that day, that does not imply the barber shaves himself. But @Jean-ClaudeArbaut proposes that my assumption that each man is shaved every day is unnecessary, so my interpretation may be wrong on that point. $\endgroup$ – hardmath Nov 19 '18 at 14:45
1
$\begingroup$

Your 2-person counterexample does not work. We have B2*=B1*=B1. Take D as day 2. Then there must be a day E satisfying the given condition. But neither day does:

If E is day 1, then since B1 shaved B1 on day 1, we would need B1*=B1 to shave B1 on day 2, which does not occur.

If E is day 2, then since B2 shaved B1 on day 2, we would need B2*=B1 to shave B1 on day 2, which does not occur.

$\endgroup$
  • $\begingroup$ @HenningMakholm The question gave a toy counterexample of the parallel problem with 2 days instead of 365, then suggested the pattern of the toy counterexample could be extended to a counterexample to the 365-day problem. Here I show the toy counterexample doesn't work; the same argument could show the 365-day counterexample won't work either. $\endgroup$ – BallBoy Nov 19 '18 at 14:57
  • $\begingroup$ That makes sense, I think I was completely misinterpreting that condition. Thanks! $\endgroup$ – Billy the Kid Nov 19 '18 at 15:16
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Sorry, I’m not sure I fully understand your comment. If my counterexample were valid (i.e. meets the given constraints), then doesn’t that prove we can schedule the barbers in a way that each day does not contain at least one barber shaving himself? $\endgroup$ – Billy the Kid Nov 19 '18 at 14:32
  • 1
    $\begingroup$ @BillytheKid: I don't think your answer describes a complete example; you only say what B1 and B2 do on the two days, but nothing about what the other 363 people are doing on those days. Unless you have a complete example where nobody shaves themself on those days, it is not a counterexample to the claim. $\endgroup$ – Henning Makholm Nov 19 '18 at 14:53
  • $\begingroup$ @hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion. $\endgroup$ – Jean-Claude Arbaut Nov 20 '18 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.