Let $N = \{1,2,3,4,5,6,7,8,9\}$ and $L = \{a,b,c\}$.
Statements
(29) Suppose we arrange the 12 elements of $L \cup N$ in a line such that all three letters appear consecutively (in any order). The number of such arrangements is less than $10! \times 5$. (30) More than half of the functions from $N$ to $L$ have the element $b$ in their range. (31) The number of one-to-one functions from $L$ to $N$ is less than 512. (32) The number of functions from $N$ to $L$ that do not map consecutive numbers to consecutive letters is greater than 512. (e.g., $f(1) = b$ and $f(2) = a$ or $c$ is not allowed. $f(1) = a$ and $f(2) = c$ is allowed. So is $f(1) = f(2)$.)

Suppose that cards numbered $1, 2, \ldots, n$ are placed on a line in some sequence (with each integer $i \in [1,n]$ appearing exactly once). A move consists of interchanging the card labeled 1 with any other card. If it is possible to rearrange the cards in increasing order by doing a series of moves, we say that the given sequence can be rectified.
Statements
(37) The sequence 912345678 can be rectified in 8 moves and no fewer moves. (38) The sequence 134567892 can be rectified in 8 moves and no fewer moves. (39) The sequence 134295678 cannot be rectified. (40) There exists a sequence of 99 cards that cannot be rectified.

[12 points] Let $N = \{ 1,2,3,4,5,6,7,8,9 \}$ and $L = \{ a , b , c \}$.
(i) Suppose we arrange the 12 elements of $L \cup N$ in a line such that no two of the three letters occur consecutively. If the order of the letters among themselves does not matter, find the number such arrangements.
(ii) Find the number of functions from $N$ to $L$ such that exactly 3 numbers are mapped to each of $a , b$ and $c$.
(iii) Find the number of onto functions from $N$ to $L$.

There are $n$ students in a class and no two of them have the same height. The students stand in a line, one behind another, in no particular order of their heights.
(a) How many different orders are there in which the shortest student is not in the first position and the tallest student is not in the last position?
(b) The badness of an ordering is the largest number $k$ with the following property. There is at least one student $X$ such that there are $k$ students taller than $X$ standing ahead of $X$. Find a formula for $g _ { k } ( n ) =$ number of orderings of $n$ students with badness $k$.
Example: The ordering $64\,61\,67\,63\,62\,66\,65$ (the numbers denote heights) has badness 3 as the student with height 62 has three taller students (with heights 64, 67 and 63) standing ahead in the line and nobody has more than 3 taller students standing ahead.
Possible hints for (b): It may be useful to first count orderings of badness 1 and/or to find $f _ { k } ( n ) =$ the number of orderings of $n$ students with badness less than or equal to $k$.

Among 12-character strings made using all eight $a$'s and four $b$'s, how many strings satisfy all of the following conditions? [4 points] (가) $b$ cannot appear consecutively. (나) If the first character is $b$, then the last character is $a$.
(1) 70
(2) 105
(3) 140
(4) 175
(5) 210

A bag contains 5 red balls, 4 yellow balls, 2 blue balls, and 9 white balls. A ball is drawn from the bag, its color is noted, and then it is returned. This procedure is repeated 3 times. What is the probability of drawing one red ball, one yellow ball, and one blue ball, regardless of the order? [3 points]
(1) $\frac { 1 } { 200 }$
(2) $\frac { 3 } { 100 }$
(3) $\frac { 7 } { 100 }$
(4) $\frac { 11 } { 100 }$
(5) $\frac { 11 } { 20 }$

When arranging $1, 2, 2, 4, 5, 5$ in a line to form a six-digit natural number, find the number of natural numbers greater than 300000. [4 points]

As shown in the figure, a rectangular solid is made from 12 transparent glass boxes in the shape of identical cubes. If 4 of these glass boxes are replaced with glass boxes of the same size but black in color such that the rectangular solid viewed from above looks like (가) and viewed from the side looks like (나), how many ways can this be done? [4 points]
(1) 54
(2) 48
(3) 42
(4) 36
(5) 30

As shown in the figure, a rectangular solid is made from 12 transparent glass boxes in the shape of cubes of equal size. When 4 of these glass boxes are replaced with black glass boxes of the same size, and the view from above looks like (가) and the side view looks like (나), how many ways can this be done? [4 points]
(1) 54
(2) 48
(3) 42
(4) 36
(5) 30

Two adults and three children go to an amusement park to ride a certain ride. This ride has 2 chairs in the front row and 3 chairs in the back row. When each child must sit in the same row as an adult, find the number of ways for all 5 people to sit in the chairs of the ride. [4 points]

Let $a _ { n }$ be the sum of all natural numbers such that when divided by a natural number $n$ ($n \geqq 2$), the quotient and remainder are equal. For example, when divided by 4, the natural numbers with equal quotient and remainder are $5, 10, 15$, so $a _ { 4 } = 5 + 10 + 15 = 30$. Find the minimum value of the natural number $n$ satisfying $a _ { n } > 500$. [4 points]

There is a walking path in a rectangular lawn. As shown in the figure, this walking path consists of 8 circles with equal radii that are externally tangent to each other.
Starting from point A and arriving at point B along the walking path by the shortest distance, find the number of possible routes. (Note: The points marked on the circles represent the points of tangency between the circles and the rectangle or between the circles.) [4 points]

A company employee has 6 types of tasks to handle, including tasks $\mathrm { A }$ and $\mathrm { B }$. The employee wants to handle 4 types of tasks today, including $\mathrm { A }$ and $\mathrm { B }$, and task $\mathrm { A }$ must be handled before task $\mathrm { B }$. What is the number of ways to select the tasks to handle today and determine the order of handling the selected tasks? [3 points]
(1) 60
(2) 66
(3) 72
(4) 78
(5) 84

A company employee has 6 tasks to handle in total, including A and B. The employee wants to handle 4 tasks including A and B today, and A must be handled before B. What is the number of ways to select the tasks to handle today and determine the order of handling the selected tasks? [3 points]
(1) 60
(2) 66
(3) 72
(4) 78
(5) 84

At a certain event venue, there are 5 locations where one banner can be installed at each location. There are three types of banners: A, B, and C, with 1 banner of type A, 4 banners of type B, and 2 banners of type C. When selecting and installing 5 banners at the 5 locations to satisfy the following conditions, how many possible outcomes are there? (Note: banners of the same type are not distinguished from each other.) [3 points]
(a) Banner A must be installed.
(b) Banner B is installed in at least 2 locations.
(1) 55
(2) 65
(3) 75
(4) 85
(5) 95

Find the natural number $n$ that satisfies the equation $2 \times {}_{n}\mathrm{C}_{3} = 3 \times {}_{n}\mathrm{P}_{2}$. [3 points]

As shown in the figure, there is a road network connected in a diamond shape. Starting from point A and traveling the shortest distance to point B without passing through point C or point D, how many ways are there? [3 points]
(1) 26
(2) 24
(3) 22
(4) 20
(5) 18

Among the numbers $1,2,3,4,5$, if we select four numbers with repetition allowed and arrange them in a row to form a four-digit natural number that is a multiple of 5, how many cases are there? [3 points]
(1) 115
(2) 120
(3) 125
(4) 130
(5) 135

Find the value of ${ } _ { 5 } \mathrm { P } _ { 2 } + { } _ { 5 } \mathrm { C } _ { 2 }$. [3 points]

Find the total number of ordered triples $( a , b , c )$ of non-negative integers satisfying the following conditions. [4 points]
(a) $a + b + c = 7$
(b) $2 ^ { a } \times 4 ^ { b }$ is a multiple of 8.

Find the number of ways to partition the natural number 11 into natural numbers between 3 and 7 (inclusive). [3 points]
(1) 2
(2) 4
(3) 6
(4) 8
(5) 10

When distributing 4 distinct balls into 4 distinct boxes without remainder, how many ways are there to distribute them such that there is at least one box containing exactly 1 ball? (Here, there may be boxes with no balls.) [4 points]
(1) 220
(2) 216
(3) 212
(4) 208
(5) 204

The following is a process for finding the number of functions $f : X \rightarrow X$ where $X = \{ 1,2,3,4,5,6 \}$ such that the range of the composite function $f \circ f$ has 5 elements. Let the ranges of functions $f$ and $f \circ f$ be $A$ and $B$, respectively. If $n ( A ) = 6$, then $f$ is a bijection, and $f \circ f$ is also a bijection, so $n ( B ) = 6$. Also, if $n ( A ) \leq 4$, then $B \subset A$, so $n ( B ) \leq 4$. Therefore, we only need to consider the case where $n ( A ) = 5$, that is, $B = A$.
(i) The number of ways to choose a subset $A$ of $X$ with $n ( A ) = 5$ is (가).
(ii) For the set $A$ chosen in (i), let $k$ be the element of $X$ that does not belong to $A$. Since $n ( A ) = 5$, the number of ways to choose $f ( k )$ from set $A$ is (나).
(iii) For $A = \left\{ a _ { 1 } , a _ { 2 } , a _ { 3 } , a _ { 4 } , a _ { 5 } \right\}$ chosen in (i) and $f ( k )$ chosen in (ii), since $f ( k ) \in A$ and $A = B$, we have $A = \left\{ f \left( a _ { 1 } \right) , f \left( a _ { 2 } \right) , f \left( a _ { 3 } \right) , f \left( a _ { 4 } \right) , f \left( a _ { 5 } \right) \right\} \cdots ( * )$. The number of cases satisfying (*) is equal to the number of bijections from set $A$ to set $A$, so it is (다). Therefore, by (i), (ii), and (iii), the number of functions $f$ we seek is (가) $\times$ (나) $\times$ (다). When the numbers corresponding to (가), (나), and (다) are $p$, $q$, and $r$, respectively, what is the value of $p + q + r$? [4 points]
(1) 131
(2) 136
(3) 141
(4) 146
(5) 151

Find the value of ${ } _ { 6 } \mathrm { P } _ { 2 } - { } _ { 6 } \mathrm { C } _ { 2 }$. [3 points]

Find the value of ${}_{6}\mathrm{P}_{2} - {}_{6}\mathrm{C}_{2}$. [3 points]