2011 AMC 10A Problem 23
Seven students count from 1 to 1000 as follows:
- Alice says all the numbers, except she skips the middle number in each consecutive group of three numbers. That is, Alice says 1, 3, 4, 6, 7, 9, ..., 997, 999, 1000.
- Barbara says all of the numbers that Alice doesn't say, except she also skips the middle number in each consecutive group of three numbers.
- Candice says all of the numbers that neither Alice nor Barbara says, except she also skips the middle number in each consecutive group of three numbers.
- Debbie, Eliza, and Fatima say all of the numbers that none of the students with the first names beginning before theirs in the alphabet say, except each also skips the middle number in each of her consecutive groups of three numbers.
- Finally, George says the only number that no one else says.
What number does George say?
Show solution without answering
Key insight
Each student gets an evenly spaced list. The numbers she skips start one step later and are spaced three times as far apart: 2, 5, 14, 41, 122, 365.
Solution
Listing numbers for each student would take forever. Instead, notice that each student gets an evenly spaced list, and describe each list by its first number and its gap.
- Alice. She groups and skips the middle of each group: . That list starts at with gap . It is what Barbara gets.
- Barbara. She groups her list in threes: and skips the middles: . That list starts at with gap .
- The pattern. A student who gets a list starting at with gap skips its 2nd, 5th, 8th, ... numbers. The 2nd number is . Between skipped numbers there are three steps of the old gap, so the new gap is . So:
new first number old first number old gap, and new gap old gap.
4. Apply it round by round. Each row shows the list a student passes on:
| Student | First number | Gap |
|---|---|---|
| Alice | ||
| Barbara | ||
| Candice | ||
| Debbie | ||
| Eliza | ||
| Fatima |
- Check Fatima by hand. She gets (the next one, , is past ). Her only full group of three is , and she skips the middle one, . The leftover is not the middle of any group, so she says it (just as Alice says ).
- So the list Fatima passes on is just (the next term, , is too big). George says .
The answer is .
Why this works
Instead of following every number, follow the shape of each list: an evenly spaced list is completely described by its first number and its gap. The skipping rule changes those two numbers in a simple way, so six students take six short lines of arithmetic. The gaps are , and since but , exactly one number is left for George.
Alternative approach
Test the answer choices against the first two students. The numbers Alice skips are the ones that leave remainder when divided by . The numbers Barbara skips () are the ones that leave remainder when divided by .
- leaves remainder when divided by , so Alice says it.
- , and each leave remainder when divided by , so Barbara says them.
- Only survives both tests ().
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Alice skips : an arithmetic progression with first term and common difference . These are the numbers handed to Barbara.
Now observe the general step. If a student receives the progression and groups it in threes, the middle numbers she skips are : again an arithmetic progression, with first term and difference . So the list passed on is described by the state
Iterate from Alice's leftover list :
- Barbara passes on ;
- Candice passes on ;
- Debbie passes on ;
- Eliza passes on ;
- Fatima receives and passes on .
The progression has only one term at most , so the unique number nobody before George says is . (Check with Fatima directly: her group of three is , so she skips ; the lone starts an incomplete group and is said, just as Alice says .)
The answer is .
Review in the AoPS books
- Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
- Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
- Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
- Intermediate Counting & Probability, Chapter 10: Recursion
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.