Problem 14 · 2021 Math Kangaroo
Hard
Counting & Probability
casework
The first 1000 positive integers are written in a row in some order and all sums of any three adjacent numbers are calculated. What is the greatest number of odd sums that can be obtained?
Show answer
Answer: A — 997
Show hints
Hint 1 of 2
A sum of three numbers is odd exactly when an odd count of them is odd.
Still stuck? Show hint 2 →
Hint 2 of 2
Think about how arranging the 500 odd and 500 even numbers controls the parity of each window of three.
Show solution
Approach: track parities; a window's sum is odd when it holds an odd count of odd numbers
- Only parity matters: write O for an odd number and E for an even one. There are 500 of each, and a window of three has an odd sum exactly when it contains one or three O's.
- There are 998 windows of three. The repeating block OOEOOE… gives an odd sum in every window except those straddling a break, and a short check shows you cannot make all 998 odd.
- Arranging the 500 O's and 500 E's carefully leaves exactly one window even, so the greatest number of odd sums is 997.
Mark:
· log in to save