pigeon hole principle [arrangement] [duplicate]
$begingroup$
This question already has an answer here:
Minimizing Gender Regularity in a linear arrangement of boys and girls
2 answers
There are G girl students and B boy students in a class that is about to graduate. You need to arrange them in a single row for the graduation. To give a better impression of diversity, you want to avoid having too many girls or too many boys seating consecutively. You decided to arrange the students in order to minimize the gender regularity. The gender regularity of an arrangement is the maximum number of students of the same gender (all girls or all boys) that appear consecutively. Given G and B, calculate the minimum gender regularity among all possible arrangements.
can someone give me the intuitive approach of solving this problem by using pigeon hole principle?
Link to problem GIRLS AND BOYS
combinatorics discrete-mathematics pigeonhole-principle
asked Jan 7 at 21:57
humblefoolhumblefool
61
$endgroup$
marked as duplicate by Mike Earnest, KReiser, Leucippus, mrtaurho, Lord Shark the Unknown Jan 8 at 6:36
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Minimizing Gender Regularity in a linear arrangement of boys and girls
2 answers
There are G girl students and B boy students in a class that is about to graduate. You need to arrange them in a single row for the graduation. To give a better impression of diversity, you want to avoid having too many girls or too many boys seating consecutively. You decided to arrange the students in order to minimize the gender regularity. The gender regularity of an arrangement is the maximum number of students of the same gender (all girls or all boys) that appear consecutively. Given G and B, calculate the minimum gender regularity among all possible arrangements.
can someone give me the intuitive approach of solving this problem by using pigeon hole principle?
Link to problem GIRLS AND BOYS
combinatorics discrete-mathematics pigeonhole-principle
asked Jan 7 at 21:57
humblefoolhumblefool
61
$endgroup$
marked as duplicate by Mike Earnest, KReiser, Leucippus, mrtaurho, Lord Shark the Unknown Jan 8 at 6:36
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
@lulu While many Readers may not want to help, I doubt this exercise fits the parameters of the Contest Problem policy. It appears this problem, which calls for a coding solution, was posted in 2010.
$endgroup$
– hardmath
Jan 7 at 22:20
1
$begingroup$
@hardmath Ah, didn't spot the date. Of course you are right. I'll delete my first comment (and this one in a few minutes).
$endgroup$
– lulu
Jan 7 at 22:21
add a comment |
$begingroup$
This question already has an answer here:
Minimizing Gender Regularity in a linear arrangement of boys and girls
2 answers
There are G girl students and B boy students in a class that is about to graduate. You need to arrange them in a single row for the graduation. To give a better impression of diversity, you want to avoid having too many girls or too many boys seating consecutively. You decided to arrange the students in order to minimize the gender regularity. The gender regularity of an arrangement is the maximum number of students of the same gender (all girls or all boys) that appear consecutively. Given G and B, calculate the minimum gender regularity among all possible arrangements.
can someone give me the intuitive approach of solving this problem by using pigeon hole principle?
Link to problem GIRLS AND BOYS
combinatorics discrete-mathematics pigeonhole-principle
asked Jan 7 at 21:57
humblefoolhumblefool
61
$endgroup$
This question already has an answer here:
Minimizing Gender Regularity in a linear arrangement of boys and girls
2 answers
There are G girl students and B boy students in a class that is about to graduate. You need to arrange them in a single row for the graduation. To give a better impression of diversity, you want to avoid having too many girls or too many boys seating consecutively. You decided to arrange the students in order to minimize the gender regularity. The gender regularity of an arrangement is the maximum number of students of the same gender (all girls or all boys) that appear consecutively. Given G and B, calculate the minimum gender regularity among all possible arrangements.
can someone give me the intuitive approach of solving this problem by using pigeon hole principle?
Link to problem GIRLS AND BOYS
This question already has an answer here:
Minimizing Gender Regularity in a linear arrangement of boys and girls
2 answers
combinatorics discrete-mathematics pigeonhole-principle
combinatorics discrete-mathematics pigeonhole-principle
asked Jan 7 at 21:57
humblefoolhumblefool
61
asked Jan 7 at 21:57
humblefoolhumblefool
61
asked Jan 7 at 21:57
humblefoolhumblefool
61
asked Jan 7 at 21:57
humblefoolhumblefool
61
asked Jan 7 at 21:57
humblefoolhumblefool
61
61
marked as duplicate by Mike Earnest, KReiser, Leucippus, mrtaurho, Lord Shark the Unknown Jan 8 at 6:36
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Mike Earnest, KReiser, Leucippus, mrtaurho, Lord Shark the Unknown Jan 8 at 6:36
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
@lulu While many Readers may not want to help, I doubt this exercise fits the parameters of the Contest Problem policy. It appears this problem, which calls for a coding solution, was posted in 2010.
$endgroup$
– hardmath
Jan 7 at 22:20
1
$begingroup$
@hardmath Ah, didn't spot the date. Of course you are right. I'll delete my first comment (and this one in a few minutes).
$endgroup$
– lulu
Jan 7 at 22:21
add a comment |
$begingroup$
@lulu While many Readers may not want to help, I doubt this exercise fits the parameters of the Contest Problem policy. It appears this problem, which calls for a coding solution, was posted in 2010.
$endgroup$
– hardmath
Jan 7 at 22:20
1
$begingroup$
@hardmath Ah, didn't spot the date. Of course you are right. I'll delete my first comment (and this one in a few minutes).
$endgroup$
– lulu
Jan 7 at 22:21
$begingroup$
@lulu While many Readers may not want to help, I doubt this exercise fits the parameters of the Contest Problem policy. It appears this problem, which calls for a coding solution, was posted in 2010.
$endgroup$
– hardmath
Jan 7 at 22:20
$begingroup$
@lulu While many Readers may not want to help, I doubt this exercise fits the parameters of the Contest Problem policy. It appears this problem, which calls for a coding solution, was posted in 2010.
$endgroup$
– hardmath
Jan 7 at 22:20
1
1
$begingroup$
@hardmath Ah, didn't spot the date. Of course you are right. I'll delete my first comment (and this one in a few minutes).
$endgroup$
– lulu
Jan 7 at 22:21
$begingroup$
@hardmath Ah, didn't spot the date. Of course you are right. I'll delete my first comment (and this one in a few minutes).
$endgroup$
– lulu
Jan 7 at 22:21
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Think of the set with the smaller number of students as dividing the row into pigeonholes. If the smaller number is $B$, then there are $B+1$ pigeonholes--one each to the right of each student, plus one at the left end of the row.
So if $G=B+1$ (or $G=B$), girls and boys can alternate, and the regularity is $1$. The regularity is 2 for $(B+1) < G leq 2(B+1)$, and so on.
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Think of the set with the smaller number of students as dividing the row into pigeonholes. If the smaller number is $B$, then there are $B+1$ pigeonholes--one each to the right of each student, plus one at the left end of the row.
So if $G=B+1$ (or $G=B$), girls and boys can alternate, and the regularity is $1$. The regularity is 2 for $(B+1) < G leq 2(B+1)$, and so on.
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
$endgroup$
add a comment |
$begingroup$
Think of the set with the smaller number of students as dividing the row into pigeonholes. If the smaller number is $B$, then there are $B+1$ pigeonholes--one each to the right of each student, plus one at the left end of the row.
So if $G=B+1$ (or $G=B$), girls and boys can alternate, and the regularity is $1$. The regularity is 2 for $(B+1) < G leq 2(B+1)$, and so on.
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
$endgroup$
add a comment |
$begingroup$
Think of the set with the smaller number of students as dividing the row into pigeonholes. If the smaller number is $B$, then there are $B+1$ pigeonholes--one each to the right of each student, plus one at the left end of the row.
So if $G=B+1$ (or $G=B$), girls and boys can alternate, and the regularity is $1$. The regularity is 2 for $(B+1) < G leq 2(B+1)$, and so on.
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
$endgroup$
Think of the set with the smaller number of students as dividing the row into pigeonholes. If the smaller number is $B$, then there are $B+1$ pigeonholes--one each to the right of each student, plus one at the left end of the row.
So if $G=B+1$ (or $G=B$), girls and boys can alternate, and the regularity is $1$. The regularity is 2 for $(B+1) < G leq 2(B+1)$, and so on.
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
answered Jan 7 at 22:50
Rick GoldsteinRick Goldstein
40125
40125
add a comment |
add a comment |
$begingroup$
@lulu While many Readers may not want to help, I doubt this exercise fits the parameters of the Contest Problem policy. It appears this problem, which calls for a coding solution, was posted in 2010.
$endgroup$
– hardmath
Jan 7 at 22:20
1
$begingroup$
@hardmath Ah, didn't spot the date. Of course you are right. I'll delete my first comment (and this one in a few minutes).
$endgroup$
– lulu
Jan 7 at 22:21