HMMT 二月 2005 · GEN1 赛 · 第 5 题

HMMT February 2005 — GEN1 Round — Problem 5

In how many ways can 4 purple balls and 4 green balls be placed into a 4 × 4 grid such that every row and column contains one purple ball and one green ball? Only one ball may be placed in each box, and rotations and reflections of a single configuration are considered different.

解析

In how many ways can 4 purple balls and 4 green balls be placed into a 4 × 4 grid such that every row and column contains one purple ball and one green ball? Only one ball may be placed in each box, and rotations and reflections of a single configuration are considered different. Solution: 216 There are 4! = 24 ways to place the four purple balls into the grid. Choose any purple ball, and place two green balls, one in its row and the other in its column. There are four boxes that do not yet lie in the same row or column as a green ball, and at least one of these contains a purple ball (otherwise the two rows containing green balls would contain the original purple ball as well as the two in the columns not containing green balls). It is then easy to see that there is a unique way to place the remaining green balls. Therefore, there are a total of 24 · 9 = 216 ways.