To Mock a Mockingbird: The Barber of Seville 3 (logic puzzle)












2














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.






logic puzzle







share|cite|improve this question




















  • 1




    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$.
    – hardmath
    Nov 19 '18 at 6:28






  • 1




    @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).
    – Jean-Claude Arbaut
    Nov 19 '18 at 7:29












  • @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).
    – Billy the Kid
    Nov 19 '18 at 14:26










  • 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.
    – hardmath
    Nov 19 '18 at 14:45
















2














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.






logic puzzle







share|cite|improve this question




















  • 1




    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$.
    – hardmath
    Nov 19 '18 at 6:28






  • 1




    @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).
    – Jean-Claude Arbaut
    Nov 19 '18 at 7:29












  • @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).
    – Billy the Kid
    Nov 19 '18 at 14:26










  • 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.
    – hardmath
    Nov 19 '18 at 14:45














2












2








2







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.






logic puzzle







share|cite|improve this question















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.






logic puzzle




logic puzzle






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 19 '18 at 15:18

























asked Nov 19 '18 at 6:03









Billy the Kid

133




133








  • 1




    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$.
    – hardmath
    Nov 19 '18 at 6:28






  • 1




    @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).
    – Jean-Claude Arbaut
    Nov 19 '18 at 7:29












  • @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).
    – Billy the Kid
    Nov 19 '18 at 14:26










  • 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.
    – hardmath
    Nov 19 '18 at 14:45














  • 1




    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$.
    – hardmath
    Nov 19 '18 at 6:28






  • 1




    @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).
    – Jean-Claude Arbaut
    Nov 19 '18 at 7:29












  • @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).
    – Billy the Kid
    Nov 19 '18 at 14:26










  • 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.
    – hardmath
    Nov 19 '18 at 14:45








1




1




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$.
– hardmath
Nov 19 '18 at 6:28




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$.
– hardmath
Nov 19 '18 at 6:28




1




1




@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).
– Jean-Claude Arbaut
Nov 19 '18 at 7:29






@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).
– Jean-Claude Arbaut
Nov 19 '18 at 7:29














@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).
– Billy the Kid
Nov 19 '18 at 14:26




@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).
– Billy the Kid
Nov 19 '18 at 14:26












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.
– hardmath
Nov 19 '18 at 14:45




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.
– hardmath
Nov 19 '18 at 14:45










2 Answers
2






active

oldest

votes


















1














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.






share|cite|improve this answer





















  • @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.
    – Y. Forman
    Nov 19 '18 at 14:57










  • That makes sense, I think I was completely misinterpreting that condition. Thanks!
    – Billy the Kid
    Nov 19 '18 at 15:16



















2














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






share|cite|improve this answer























  • 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?
    – Billy the Kid
    Nov 19 '18 at 14:32






  • 1




    @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.
    – Henning Makholm
    Nov 19 '18 at 14:53










  • @hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion.
    – Jean-Claude Arbaut
    Nov 20 '18 at 4:44











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004581%2fto-mock-a-mockingbird-the-barber-of-seville-3-logic-puzzle%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









1














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.






share|cite|improve this answer





















  • @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.
    – Y. Forman
    Nov 19 '18 at 14:57










  • That makes sense, I think I was completely misinterpreting that condition. Thanks!
    – Billy the Kid
    Nov 19 '18 at 15:16
















1














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.






share|cite|improve this answer





















  • @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.
    – Y. Forman
    Nov 19 '18 at 14:57










  • That makes sense, I think I was completely misinterpreting that condition. Thanks!
    – Billy the Kid
    Nov 19 '18 at 15:16














1












1








1






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.






share|cite|improve this answer












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.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 19 '18 at 14:53









Y. Forman

11.4k523




11.4k523












  • @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.
    – Y. Forman
    Nov 19 '18 at 14:57










  • That makes sense, I think I was completely misinterpreting that condition. Thanks!
    – Billy the Kid
    Nov 19 '18 at 15:16


















  • @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.
    – Y. Forman
    Nov 19 '18 at 14:57










  • That makes sense, I think I was completely misinterpreting that condition. Thanks!
    – Billy the Kid
    Nov 19 '18 at 15:16
















@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.
– Y. Forman
Nov 19 '18 at 14:57




@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.
– Y. Forman
Nov 19 '18 at 14:57












That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
Nov 19 '18 at 15:16




That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
Nov 19 '18 at 15:16











2














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






share|cite|improve this answer























  • 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?
    – Billy the Kid
    Nov 19 '18 at 14:32






  • 1




    @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.
    – Henning Makholm
    Nov 19 '18 at 14:53










  • @hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion.
    – Jean-Claude Arbaut
    Nov 20 '18 at 4:44
















2














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






share|cite|improve this answer























  • 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?
    – Billy the Kid
    Nov 19 '18 at 14:32






  • 1




    @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.
    – Henning Makholm
    Nov 19 '18 at 14:53










  • @hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion.
    – Jean-Claude Arbaut
    Nov 20 '18 at 4:44














2












2








2






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






share|cite|improve this 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$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 20 '18 at 4:42

























answered Nov 19 '18 at 7:02









Jean-Claude Arbaut

14.7k63464




14.7k63464












  • 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?
    – Billy the Kid
    Nov 19 '18 at 14:32






  • 1




    @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.
    – Henning Makholm
    Nov 19 '18 at 14:53










  • @hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion.
    – Jean-Claude Arbaut
    Nov 20 '18 at 4:44


















  • 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?
    – Billy the Kid
    Nov 19 '18 at 14:32






  • 1




    @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.
    – Henning Makholm
    Nov 19 '18 at 14:53










  • @hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion.
    – Jean-Claude Arbaut
    Nov 20 '18 at 4:44
















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?
– Billy the Kid
Nov 19 '18 at 14:32




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?
– Billy the Kid
Nov 19 '18 at 14:32




1




1




@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.
– Henning Makholm
Nov 19 '18 at 14:53




@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.
– Henning Makholm
Nov 19 '18 at 14:53












@hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion.
– Jean-Claude Arbaut
Nov 20 '18 at 4:44




@hardmath That's right! Thanks for pointing this out. It's corrected, and thankfully this does not alter the conclusion.
– Jean-Claude Arbaut
Nov 20 '18 at 4:44


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004581%2fto-mock-a-mockingbird-the-barber-of-seville-3-logic-puzzle%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

AnyDesk - Fatal Program Failure

Image
up vote 0 down vote favorite Good day all. I have a window that pops up saying Fatal Program Failure (AnyDesk). This is what I have done so far: Uninstalled AnyDesk and reinstalled it. ( The window still appeared ) I disabled AnyDesk start up in Msconfig and the window seems to have disapeared. Lastly I made sure that AnyDesk worked by remoting into it, and it worked. Today the same window appeared. How do I get rid of this window? remote-desktop share | improve this question edited 10 hours ago Tomasz Jakub Rup 552 3 13 ...
Read more

How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

Image
up vote 0 down vote favorite I need help with an issue we're facing in a project where we are moving from a Windows-based POS environment to one running on CentOS7. The problem consists of a number of factors, please find the details below: The supplier of our POS application will only deliver an application that is hard-coded to run in a 1024:768 4:3 format. The hardware we are using is a POS unit from HP that has a built-in 16:9 touch-screen. The employees using this solution is not supposed to see nor have access to anything but the POS application. Our sales organization demands that touch is an available feature when going live with the new POS environment. Going further into this, allow me to explain what we have encountered on the way trying to achieve the goal of having a touch-screen: We've simply change...
Read more

QoS: MAC-Priority for clients behind a repeater

Image
1 1 I've setup a wireless network using a Linksys-Router (DD-WRT) as an AP and a TP-Link repeater for range extension. To manage bandwith for specific users, I've setup QoS-Rules on the AP (DD-WRT) using MAC-Priority: However the AP shows only the Repeater's MAC and the MACs of users inside the AP-Range. The MAC addresses of users behind the Repeater are not listed : The purple MAC is not listed in the AP-Clientlist. Its related to a device connected via the TP-Link repeater. Q: How can I setup MAC-Priority for repeater-clients? Do I simply add the purple MAC in AP-MAC priority list although it's not listed as a client? I want to setup specific priority instead of giving one priority for all clients behind the repeater by adding the repeater's MAC in the MAC priority list in the AP as ...
Read more