2007 AMC 10B Problem 9

P1-10~3 minPrint

Modular Arithmetic Sequences & Series Set up the equation/formula and compute; no special trick needed

A cryptographic code is designed as follows. The first time a letter appears in a given message it is replaced by the letter that is $1$ place to its right in the alphabet (asumming that the letter $A$ is one place to the right of the letter $Z$ ). The second time this same letter appears in the given message, it is replaced by the letter that is $1+2$ places to the right, the third time it is replaced by the letter that is $1+2+3$ places to the right, and so on. For example, with this code the word "banana" becomes "cbodqg". What letter will replace the last letter $s$ in the message $\text{"Lee's sis is a Mississippi miss, Chriss!"?}$

Show solution without answering

Key insight

The last s is the 12th s, so it moves 1 + 2 + ... + 12 = 78 places, exactly three trips around the alphabet.

Solution

Two jobs: find which appearance of $s$ the last one is, then work out how far it moves.

Count the $s$ 's word by word:

word	Lee's	sis	is	a	Mississippi	miss	Chriss
number of $s$	1	2	1	0	4	2	2
running total	1	3	4	4	8	10	12

The last $s$ is the $12$ th one.
2. The $12$ th appearance moves $1 + 2 + 3 + \cdots + 12$ places. Pair the numbers from the outside in: $1 + 12$ , $2 + 11$ , and so on, six pairs of $13$ . So the shift is
$6 \times 13 = 78 \text{ places}.$
3. The alphabet has $26$ letters, and moving $26$ places brings a letter back to itself. Since $78 = 3 \times 26$ , the letter goes around three full times and stops where it started.
4. So the last $s$ becomes $s$ .

The answer is $\boxed{\textbf{(D)}\ s}$ .

Why this works

With a wrap-around alphabet, only the leftover after taking out full trips of $26$ matters. Figure out the total shift first and remove the full trips, rather than stepping letter by letter. Most of the danger in this problem is simply counting the $s$ 's correctly, so a table is worth the few seconds.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

First count how many times the letter $s$ appears, word by word:

word	Lee's	sis	is	a	Mississippi	miss	Chriss
number of $s$	1	2	1	0	4	2	2

Running total: $1, 3, 4, 4, 8, 10, 12$ . The final $s$ is the $12$ th occurrence.

The $k$ th occurrence of a letter moves $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ places to the right. For $k = 12$ this is $\frac{12 \cdot 13}{2} = 78$ .

Since the alphabet has $26$ letters, a shift of $78 = 3 \cdot 26$ brings the letter all the way around three full times and back to where it started. The last $s$ is replaced by $s$ itself.

The answer is $\boxed{\textbf{(D)}\ s}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Introduction to Number Theory, Chapter 10: Units Digits
Intermediate Algebra, Chapter 17: More Sequences and Series (§17.1, §17.2)