Mixing
To Mock a Mockingbird: The Barber of Seville 3 (logic puzzle)
up vote
2
down vote
favorite
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
asked 19 hours ago
Billy the Kid
133
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
2
down vote
favorite
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
asked 19 hours ago
Billy the Kid
133
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
19 hours ago
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
18 hours ago
@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
11 hours ago
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
11 hours ago
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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
asked 19 hours ago
Billy the Kid
133
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
asked 19 hours ago
Billy the Kid
133
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 19 hours ago
Billy the Kid
133
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 10 hours ago
asked 19 hours ago
Billy the Kid
133
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 19 hours ago
Billy the Kid
133
asked 19 hours ago
Billy the Kid
133
133
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Billy the Kid is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
19 hours ago
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
18 hours ago
@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
11 hours ago
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
11 hours ago
add a comment |
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
19 hours ago
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
18 hours ago
@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
11 hours ago
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
11 hours ago
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
19 hours ago
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
19 hours ago
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
18 hours ago
@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
18 hours ago
@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
11 hours ago
@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
11 hours ago
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
11 hours ago
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
11 hours ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
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.
answered 10 hours ago
Y. Forman
11.3k423
@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
10 hours ago
That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
10 hours ago
add a comment |
up vote
1
down vote
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$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ 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$.
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
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
11 hours ago
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
10 hours ago
I think there is a minor misphrasing in the proof. You wrote that "since $X$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ on day $D$." But the wording of the original problem claims "if $X$ shaved $Y$ on day $E$, then $X^*$ shaved $Y$ on day $D$." So as phrased you have the relation backwards on day $D$.
– hardmath
3 hours ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
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.
answered 10 hours ago
Y. Forman
11.3k423
@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
10 hours ago
That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
10 hours ago
add a comment |
up vote
1
down vote
accepted
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.
answered 10 hours ago
Y. Forman
11.3k423
@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
10 hours ago
That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
10 hours ago
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
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.
answered 10 hours ago
Y. Forman
11.3k423
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.
answered 10 hours ago
Y. Forman
11.3k423
answered 10 hours ago
Y. Forman
11.3k423
answered 10 hours ago
Y. Forman
11.3k423
answered 10 hours ago
Y. Forman
11.3k423
11.3k423
@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
10 hours ago
That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
10 hours ago
add a comment |
@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
10 hours ago
That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
10 hours ago
@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
10 hours ago
@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
10 hours ago
That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
10 hours ago
That makes sense, I think I was completely misinterpreting that condition. Thanks!
– Billy the Kid
10 hours ago
add a comment |
up vote
1
down vote
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$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ 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$.
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
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
11 hours ago
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
10 hours ago
I think there is a minor misphrasing in the proof. You wrote that "since $X$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ on day $D$." But the wording of the original problem claims "if $X$ shaved $Y$ on day $E$, then $X^*$ shaved $Y$ on day $D$." So as phrased you have the relation backwards on day $D$.
– hardmath
3 hours ago
add a comment |
up vote
1
down vote
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$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ 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$.
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
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
11 hours ago
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
10 hours ago
I think there is a minor misphrasing in the proof. You wrote that "since $X$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ on day $D$." But the wording of the original problem claims "if $X$ shaved $Y$ on day $E$, then $X^*$ shaved $Y$ on day $D$." So as phrased you have the relation backwards on day $D$.
– hardmath
3 hours ago
add a comment |
up vote
1
down vote
up vote
1
down vote
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$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ 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$.
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
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$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ 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$.
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
edited 15 hours ago
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
answered 18 hours ago
Jean-Claude Arbaut
14.3k63361
14.3k63361
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
11 hours ago
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
10 hours ago
I think there is a minor misphrasing in the proof. You wrote that "since $X$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ on day $D$." But the wording of the original problem claims "if $X$ shaved $Y$ on day $E$, then $X^*$ shaved $Y$ on day $D$." So as phrased you have the relation backwards on day $D$.
– hardmath
3 hours ago
add a comment |
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
11 hours ago
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
10 hours ago
I think there is a minor misphrasing in the proof. You wrote that "since $X$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ on day $D$." But the wording of the original problem claims "if $X$ shaved $Y$ on day $E$, then $X^*$ shaved $Y$ on day $D$." So as phrased you have the relation backwards on day $D$.
– hardmath
3 hours ago
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
11 hours ago
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
11 hours ago
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
10 hours ago
@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
10 hours ago
I think there is a minor misphrasing in the proof. You wrote that "since $X$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ on day $D$." But the wording of the original problem claims "if $X$ shaved $Y$ on day $E$, then $X^*$ shaved $Y$ on day $D$." So as phrased you have the relation backwards on day $D$.
– hardmath
3 hours ago
I think there is a minor misphrasing in the proof. You wrote that "since $X$ shave $Y$ on day $E$, the condition means that $Y$ shaves $X^*$ on day $D$." But the wording of the original problem claims "if $X$ shaved $Y$ on day $E$, then $X^*$ shaved $Y$ on day $D$." So as phrased you have the relation backwards on day $D$.
– hardmath
3 hours ago
add a comment |
Billy the Kid is a new contributor. Be nice, and check out our Code of Conduct.
Billy the Kid is a new contributor. Be nice, and check out our Code of Conduct.
Billy the Kid is a new contributor. Be nice, and check out our Code of Conduct.
Billy the Kid is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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
19 hours ago
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
18 hours ago
@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
11 hours ago
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
11 hours ago