Swapping the genders does not change the number of meetings. Let and choose the cells occupied by the less numerous gender. If , either gender may be chosen.
Define the degree of a cell as the number of cells sharing an edge with it. Interior cells have degree , boundary cells other than corners have degree , and corners have degree .
Color the grid as a checkerboard. No two cells of the same color share an edge. If we choose cells of just one color, the number of meetings is exactly the sum of their degrees. For each color, choose its cells of largest degree, and use whichever color gives the larger sum. Either color is allowed in a tie. Each color contains at least cells, so both candidates are feasible.
No sorting is necessary. Count the cells of degrees in each color, and determine how many to select in that order. After choosing a color and the counts for each degree, scan the grid again and place the less numerous gender in the required number of cells. Fill all remaining cells with the other gender. This also handles by filling the entire grid with one gender.
The grid is scanned a constant number of times, giving time. Constructing and outputting one row at a time uses space.
Proof
We must show that restricting the chosen cells to one checkerboard color can attain a global optimum. In an arbitrary arrangement, call the cells occupied by the less numerous gender selected. Let be the number of meetings, the number of selected interior cells, the number of selected corners, and the number of edges whose two endpoints are selected. Summing the degrees of selected cells and subtracting such internal edges twice gives
Solution written by GPT6
Since every degree is at most , we also have .
Let . The largest set of pairwise nonadjacent cells in the interior grid has size . To see the upper bound, follow a snake path through all interior cells, reversing direction in each row. No two consecutive cells on this path can both be chosen, so at most can be chosen. The larger checkerboard color attains . For , the interior is empty and .
Let count the edges whose endpoints are both selected interior cells. Removing one endpoint of each such edge leaves at least pairwise nonadjacent interior cells. Therefore . Since , we obtain
First suppose is even. Partition the grid into disjoint squares. If a square contains selected cells, at most of its four edges join different genders. Thus, at least of its edges join the same gender. Summing over the squares shows that the whole grid contains at least edges joining the same gender. There are edges in total, so
For even , each checkerboard color contains degree- cells, degree- cells, and two degree- cells. Selecting cells in decreasing degree order gives the sum
This attains the smallest of the three upper bounds, proving optimality.
Now suppose is odd, and write , so . Equality requires in the preceding inequalities. Since , this forces and hence .
The interior contains cells. On its snake path, the only way to choose pairwise nonadjacent cells is to choose every other cell, starting from the first. Consequently, the interior has a unique maximum independent set: the checkerboard color containing its corners. This is also the color of the four corners of the whole grid.
Once those interior cells are selected, every boundary cell of the opposite color is adjacent to a selected interior cell. Such cells cannot be added because , and corners cannot be added because . Only the noncorner boundary cells of the same color remain available. Thus, equality implies . For , integrality therefore gives the stronger bound
The color containing the four corners has cells of degrees , respectively. The other color has such cells. Selecting in decreasing degree order attains all the relevant bounds:
When , the second range is empty; the other cases still apply. Hence the better of the two candidates also attains a global upper bound when is odd, completing the proof.
