1
$\begingroup$

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.

2 Answers 2

4

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.

0

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.