Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let us consider that there are G girl students and B boy students in a class, we need to arrange them in a single row, but arrangement of students should be in order to minimize the gender regularity*. Find the minimum gender regularity among all possible arrangements.

*The gender regularity of an arrangement is the maximum number of students of the same gender (all girls or all boys) that appear consecutively.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

I will try to show the solution is ceil(M / N+1) where M is the larger of B and G, N is the lesser.

Best case is M = N, where we need merely arrange the genders alternately, and regularity = ceil(M / M+1) = 1. Worst case is a single-gender class, i.e N=0 in which regularity = ceil(M/1) = M, i.e. the whole class size. In all other cases, clearly 1 < regularity < M+N.

Now work quasi-inductively. If N = 1, then we place the singleton in the center of the line, with half of the others to each side. If the larger group is even, there are M/2 to each side (the ceil of a whole number is itself.) If the larger group is odd, there will be one more on one side of the single, and it is this group that gives regularity = ceil(M/2).

If N = 2, do a similar process, divide the M into three groups, placing the two in between them (picture ---------- where the * are the small group, - the larger). If the larger group is divisible by 3, there are M/3 in each division. If not, distribute the 1 or 2 remainder over distinct divisions, and the largest will contain ceil(M/3) students.

As N increases toward M, repeat the concept, dividing the larger group into M/N+1 divisions, place the N between them, and distribute the remainder.

share|improve this answer
add comment

Assume that there are B boys and G girls. Let us say (Without loss of generality) that B is no smaller than G. Let us make the arrangement by lining up the girls and then lining up the boys among them. In this arrangement, there are G+1 places the boys can be (before girl 1, between girl 1 and 2, ... , between girl G-1 and G, and after girl G). By the pigeonhole principal principle, you will have at least ceil(B / G+1) boys in one of these locations, and since there are no other conditions, this minimum is achievable.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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