🇺🇸 AMC 8 ⇄ switch contest
1991 AJHSME

Problem 6

Problem 6 · 1991 AJHSME Hard
Logic & Word Problems array-search

Which number in the array below is both the largest in its column and the smallest in its row? (Columns go up and down, rows go right and left.)

10643211714108834591341512182593
Show answer
Answer: C — 7.
Show hints
Hint 1 of 3
Two conditions must hold at once, but they aren't equally cheap to check. One of them — being the SMALLEST in its row — only needs you to glance along a single row of five numbers. Which condition would you screen with first to throw out the most candidates fast?
Still stuck? Show hint 2 →
Hint 2 of 3
This is a search with two filters. Pick the filter that's quick to apply, run it to make a short list, then test only the survivors against the slower filter. Here: find each row's smallest, then check just those few against their column.
Still stuck? Show hint 3 →
Hint 3 of 3
There are 5 rows, so only 5 numbers can possibly be "smallest in its row." Find those 5, then check each one against its column for "largest in its column."
Show solution
Approach: screen with the cheap filter first, then test the survivors
  1. Two conditions must both hold, so use the faster one to shrink the search. Scan each row for its smallest entry — that gives just 5 candidates instead of all 25.
  2. Row by row the smallest entries are: 2 (top row), 7 (second row: 11, 7, 14, 10, 8), 3, 1, and 2.
  3. Now test each candidate against its column. The 7 sits in the second column (6, 7, 3, 4, 2), where it is the largest. The others fail the column test.
  4. So the number that is both smallest in its row and largest in its column is 7.
  5. Why this transfers: when something must satisfy two conditions, don't check both for every item — apply the condition that's quickest to evaluate first, then test only what survives. This "cheap filter first" idea saves work in counting and search problems everywhere.
  6. Worth knowing: a value that is the min of its row and the max of its column is called a saddle point — and there can be at most one such value in any grid.
Mark: · log in to save
↑