2000 AMC 10 Problem 13

P11-15~4 minPrint

Arrangements with Restrictions Consider the largest/smallest element or boundary case Use an invariant, parity, or coloring argument

There are 5 yellow pegs, 4 red pegs, 3 green pegs, 2 blue pegs, and 1 orange peg to be placed on a triangular peg board. In how many ways can the pegs be placed so that no (horizontal) row or (vertical) column contains two pegs of the same color?

Show solution without answering

Key insight

Five yellow pegs need five different rows and five different columns, and the board has exactly five of each. That forces their places, and every other color's too.

Solution

Look at the board. It has $5$ rows with $5, 4, 3, 2, 1$ holes, and $5$ columns with $1, 2, 3, 4, 5$ holes. That is $15$ holes for $15$ pegs, so every hole gets a peg.
Start with the color that has the most pegs, because it is the hardest to fit. There are $5$ yellow pegs and they need $5$ different rows and $5$ different columns. With only $5$ rows and $5$ columns, every row and every column gets exactly one yellow peg.
Take the column with only $1$ hole. It needs a yellow peg, and there is only one place for it. That also uses up the yellow peg for that hole's row.
Now take the column with $2$ holes. One of its holes is in the row already used, so its yellow peg has only one place left. Keep going column by column: each time exactly one spot is left. The yellow pegs end up along the long slanted edge of the triangle, and there was only one way to place them.
Cover up those $5$ holes. What is left is a smaller triangle with rows of $4, 3, 2, 1$ holes and columns of $1, 2, 3, 4$ holes. The $4$ red pegs are now in exactly the same situation, so they are forced too.
Repeat for green ( $3$ pegs), blue ( $2$ ) and orange ( $1$ ). Each color is forced.

So there is exactly one way to place the pegs.

The answer is $\boxed{\textbf{(B)}\ 1}$ .

Why this works

When you have as many identical pegs as there are rows and as there are columns, "one in each row and column" leaves no freedom on a triangle-shaped board. Start with the tightest condition. Each forced step leaves the same shape one size smaller, so the same argument repeats all the way down.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The board has $5$ rows (lengths $5, 4, 3, 2, 1$ ) and $5$ columns (lengths $1, 2, 3, 4, 5$ ), fifteen holes in all, one per peg.

Start with the most constrained color. The five yellow pegs must occupy five different rows and five different columns. The single-hole column has one spot, so a yellow peg goes there; that uses its row too. The two-hole column now has one spot left outside that row, so its yellow peg is forced; and so on. Yellow is placed in exactly one way, along the "long diagonal."

Remove those holes. What remains is a board with rows of lengths $4, 3, 2, 1$ and columns of lengths $1, 2, 3, 4$ , and the four red pegs face the identical situation, so they are forced as well. Repeating for green, blue and orange fills the board uniquely.

The answer is $\boxed{\textbf{(B)}\ 1}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)