2004 AIME I Problem 6

Below is the professionally curated solution for Problem 6 of the 2004 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2004 AIME I solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:arrangements with restrictionsdigitscasework

Difficulty rating: 2510

6.

An integer is called snakelike if its decimal representation a1a2a3aka_1 a_2 a_3 \ldots a_k satisfies ai<ai+1a_i \lt a_{i+1} if ii is odd and ai>ai+1a_i \gt a_{i+1} if ii is even. How many snakelike integers between 10001000 and 99999999 have four distinct digits?

Solution:

A four-digit snakelike number satisfies a1<a2>a3<a4.a_1 \lt a_2 \gt a_3 \lt a_4. First count the arrangements of any four distinct digits w<x<y<zw \lt x \lt y \lt z into this pattern. The largest digit zz must sit in position 22 or 4.4. If zz is in position 4,4, the other three form a1<a2>a3,a_1 \lt a_2 \gt a_3, so the largest of them takes position 22 and the remaining two can go in either order: 22 ways. If zz is in position 2,2, any of the other three digits can be a1,a_1, and then a3<a4a_3 \lt a_4 fixes the rest: 33 ways. So each set of four digits admits exactly 55 snakelike orders.

If 00 is not among the digits, all 55 orders give valid numbers: (94)5=630.\binom{9}{4} \cdot 5 = 630. If 00 is among them, note 00 must occupy position 11 or 33 (positions 22 and 44 must exceed a neighbor), and position 11 is forbidden. With 00 in position 3,3, any of the other three digits can be a4,a_4, and a1<a2a_1 \lt a_2 fixes the rest, so 33 of the 55 orders survive: (93)3=252.\binom{9}{3} \cdot 3 = 252.

The total is 630+252=882.630 + 252 = 882.

← Problem 5Full ExamProblem 7

Problem 6 in Other Years