Problem 26 · 2009 Math Kangaroo
Stretch
Counting & Probability
sum-constraintcareful-counting
Robert wants to place stones on a 4 × 4 game board so that the number of stones in each row and in each column is different; that is, there are 8 different amounts. To do this he can place one or several stones in any one field, or even leave single fields empty. What is the minimum number of stones needed?
Show answer
Answer: A — 14
Show hints
Hint 1 of 2
The four row totals and four column totals are eight different whole numbers.
Still stuck? Show hint 2 →
Hint 2 of 2
The smallest eight distinct totals are 0–7; the stones are the sum of either the rows or the columns.
Show solution
Approach: minimise the shared row/column total
- The eight totals must be eight distinct non-negative integers; the smallest set is 0,1,2,3,4,5,6,7.
- Total stones equals the sum of the four row totals, which must equal the sum of the four column totals.
- Split 0–7 into two equal-sum fours, e.g. rows {0,1,6,7} and columns {2,3,4,5}, each summing to 14.
- Such a board is realisable, so the minimum number of stones is 14.
Mark:
· log in to save