Maths Olympiad Prep

Library / /209 of 213

, 2025

Combinatorics Difficulty 4.9 AIME Find the answer Canada

The list 1111, 1212, 1414, 2323, 3131, 4444, 4545, 4646, 5656, 6464, 6767, 7474 can be arranged so that the units
digit of each number matches the tens digit of the number that follows
it. For example, 1212, 2323, 3131, 1111, 1414, 4444, 4545, 5656, 6767, 7474, 4646, 6464 is one such arrangement. How many such
arrangements of the given list are possible?

Pick one

Solution

We begin by recognizing that in the given list, each of the
digits 11 through 77 occurs at least once as a units digit,
and at least once as a tens digit.

For example, the digit 11 occurs
twice as a units digit (1111 and
3131), and three times as a tens
digit (1111, 1212 and 1414).

Counting the number of times each of the digits 11 through 77 occurs as a units digit and as a tens
digit, we get:

Digit
11
22
33
44
55
66
77

Number of times occurring as a units digit
22
11
11
44
11
22
11

Number of times occurring as a tens digit
33
11
11
33
11
22
11

The units digit of each number in the list matches the tens digit of
the number that follows it.

This tells us that if we ignore the tens digit of the first number in
the list and the units digit of the last number in the list, then the
number of times that each digit occurs as a units digit must be equal to
the number of times that it occurs as a tens digit.

Looking back to the table above, we see that this is true for all digits
except 1 and 4.

Since the digit 1 occurs twice as a units digit and three times as a
tens digit, then the tens digit of the first number in the list must be
equal to 1.

Similarly, the digit 4 occurs four times as a units digit and three
times as a tens digit, and so the units digit of the last number in the
list must be equal to 4.

Ignoring the number 14 for a moment, we separate the 11 remaining
numbers into two distinct lists, which we call AA and BB. A:11,12,23,31      B:44,45,46,56,64,67,74A: 11,12,23,31 \ \ \ \ \ \ B: 44,45,46,56,64,67,74 Each digit in
AA is less than or equal to 33, and each digit in BB is greater than or equal to 44.

Since 1414 is the only number given
that does not appear in AA or BB, and 1414 has a digit that appears in AA and a digit that appears in BB, then 1414 is the only number that can ’connect’
the numbers in AA to those in BB.

Further, this tells us that the numbers in AA must be arranged and then placed before
an arrangement of the numbers in BB,
with 1414 appearing between the two
arrangements.

Also, the arrangement of the numbers in AA must begin and end with a 11, and the arrangement of the numbers in
BB must begin and end with a 44 (since 1414 occurs between the two lists).

Next, we count the number of different ways to arrange the numbers in
AA, starting and ending with 11.

We begin by recognizing that each of the digits 22 and 33 occurs exactly once as a units digit
and once as a tens digit, and so 1212, 2323, 3131 must appear together in this order
(the two 22s must occur together and
the two 33s must occur
together).

The list must begin and end with a 11, and so there are 22 possible locations for the 1111 and thus 22 possible arrangements of the numbers in
AA: $11,
12, 23, 31,and, and 12, 23, 31,
11$.

Next, we count the number of different ways to arrange the numbers in
BB, starting and ending with 44.

We begin by recognizing that each of the digits 55 and 77 occurs exactly once as a units digit
and once as a tens digit, and so 4545, 5656 must appear together in this order
(the two 55s must occur together),
and 6767, 7474 must appear together in this order
(the two 77s must occur
together).

The arrangement ends with a 44, and
thus cannot end with 4545, 5656, and so at least one more number must
immediately follow 4545, 5656.

There are two such possibilities: $45, 56,
64,and, and 45, 56, 67, 74$
(recall that 67,7467, 74 must remain
together), which leads to exactly two distinct cases to consider.

Case 1: 45,56,64\boldsymbol{45, 56, 64} occur
together in this order.

In this case, the remaining numbers are 4444, 4646, 6767, and 7474.

Since 4444 has two equal digits, its
location in the arrangement of the BB list cannot change the first digit in
the list (which must be 44), and
cannot change the last digit in the list (which must also be 44), and thus we ignore 4444 for the moment.

The remaining numbers, 4646, 6767, 7474 must occur together in this order. Can
you see why?

Since the blocks 45,56,6445, 56, 64 and
46,67,7446, 67, 74 must each occur together
in their respective orders, this gives two possible arrangements of the
BB list (ignoring the 4444).

These are: 45,56,64,46,67,7445, 56, 64, 46, 67, 74,
and 46,67,74,45,56,6446, 67, 74, 45, 56, 64.

Next, we determine the number of different ways to place 4444 into each of these arrangements.

In the 45,56,64,46,67,7445, 56, 64, 46, 67, 74
arrangement, the 4444 may appear at
the start, at the end, or between the 6464 and 4646, which gives 33 different arrangements of the BB list. (These are: 44,45,56,64,46,67,7444, 45, 56, 64, 46, 67, 74, and 45,56,64,46,67,74,4445, 56, 64, 46, 67, 74, 44, and 45,56,64,44,46,67,7445, 56, 64, 44, 46, 67, 74.)

In the 46,67,74,45,56,6446, 67, 74, 45, 56, 64
arrangement, the 4444 may appear at
the start, at the end, or between the 7474 and 4545, which gives 33 more arrangements of the BB list, or 66 in total for Case 1.

Case 2: 45,56,67,74\boldsymbol{45, 56, 67, 74}
occur together in this order.

In this case, the remaining numbers are 4444, 4646, and 6464.

We again begin by ignoring 4444 for
the moment.

The remaining numbers, 46,6446, 64 must
occur together in this order.

Since the blocks 45,56,67,7445, 56, 67, 74 and
46,6446, 64 must each occur together in
their respective orders, this gives two possible arrangements of the
BB list (ignoring the 4444).

These are: 45,56,67,74,46,6445, 56, 67, 74, 46, 64
and 46,64,45,56,67,7446, 64, 45, 56, 67, 74.

In the 45,56,67,74,46,6445, 56, 67, 74, 46, 64
arrangement, the 4444 may appear at
the start, at the end, or between the 7474 and 4646, which gives 33 more different arrangements of the
BB list.

In the 46,64,45,56,67,7446, 64, 45, 56, 67, 74
arrangement, the 4444 may appear at
the start, at the end, or between the 6464 and 4545, which gives 33 more arrangements of the BB list, or 66 in total for Case 2.

Thus, there are a total of 6+6=126+6=12 different ways to arrange the
BB list.

There are 22 different ways to
arrange the numbers in list AA,
1212 different ways to arrange the
numbers in list BB, and exactly
11 way to place the number 1414 between arrangements of each of the
two lists. Thus, the total number of arrangements of the given list is
2×12×1=242\times12\times1=24.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.