2019 AMC 10A Problem 20
The numbers are randomly placed into the squares of a grid. Each square gets one number, and each of the numbers is used once. What is the probability that the sum of the numbers in each row and each column is odd?
Show solution without answering
Key insight
Only odd or even matters. The five odd numbers must fill one whole row and one whole column, a cross shape. There are 9 crosses out of 126 odd-even patterns.
Solution
Whether a sum is odd depends only on how many odd numbers are in it. So forget the actual numbers and just mark each square O (odd) or E (even).
- How many patterns? There are five odd numbers () and four even ones. A pattern is a choice of which squares get the odds. There are such choices, and every one is equally likely.
- What makes a row sum odd? A row of three numbers has an odd sum when it has or odd numbers (an odd count of odds).
- Rows. The three rows each have or odds, and together they hold all odds. The only way: . So one row is all odd, and each other row has exactly one odd.
- Columns. The all-odd row already puts one odd in every column. The other two odds (one in each remaining row) must not make any column's count even. If they were in different columns, those two columns would have odds each, an even sum. So they must be in the same column, which then has odds.
- The shape. The good patterns are exactly a full row plus a full column of odds, like a plus sign or cross:
| O | O | O |
|---|---|---|
| E | O | E |
| E | O | E |
It uses squares, as it should. Check: every row and column has or odds.
6. Count the crosses. Choose the row ( ways) and the column ( ways): crosses.
7. Probability. .
The answer is .
Why this works
When a question is only about sums being odd or even, the only thing that matters is where the odd numbers go. Swapping the full arrangements for the odd-even patterns, which are all equally likely, makes the count small enough to reason about. Then counting odds row by row forces the cross shape.
Alternative approach
Count full arrangements instead. There are crosses; the odd numbers can be placed on a cross in ways and the even numbers in the other squares in ways. Out of arrangements, the probability is
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Only the parity of each entry matters. There are five odd numbers () and four even ones, and every choice of which cells hold the odd numbers is equally likely: patterns.
A row sum is odd exactly when the row contains or odd numbers. The three row counts are odd and add to , so they must be in some order: one row is entirely odd and each other row has exactly one odd entry. The all-odd row gives every column one odd number; the two remaining odd entries must keep each column count odd, so they cannot land in different columns (that would make two columns even). They therefore sit in the same column, making that column all odd.
So a good pattern is a full row plus a full column of odds, a "cross," and any cross uses exactly cells. There are crosses, and each does work (the full row and column have sums of three odds; the other rows and columns have exactly one odd).
Probability: .
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 7: Introduction to Probability
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
- Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
- Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.