Maths Olympiad Prep

Track / Stage 5 / 194 of 400 #794 of 1964

Problem 794

AIME late
Combinatorics Difficulty 5.5 Find the answer

Example 2 (2000 National High School Competition Question) If: (1) a,b,c,da, b, c, d all belong to {1,2,3,4}\{1,2,3,4\}; (2) aba \neq b, bc,cd,dab \neq c, c \neq d, d \neq a; (3) aa is the smallest value among a,b,c,da, b, c, d. Then the number of different four-digit numbers abcd\overline{a b c d} that can be formed is \qquad

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

Solve by filling in 28. Reason: (1) When abcd\overline{a b c d} contains 4 different digits, it is clear that a=1a=1. There are 3!=63!=6 such four-digit numbers.
(2) When abcd contains only 3 different digits, choosing 3 different digits from 1,2,3,41,2,3,4 has C43C_{4}^{3} methods. At this time, the value of aa is uniquely determined (aa is the smallest of the 3 chosen numbers). When a=ca=c, b,db, d have 2! ways to be arranged; when aca \neq c, b=d,cb=d, c have 2 ways to be arranged, with b=db=d being the remaining number. Therefore, the number of four-digit numbers at this time is C43(2+2)=16C_{4}^{3}(2+2)=16.
(3) When abcd\overline{a b c d} contains only 2 digits, choosing 2 digits from 1,2,3,41,2,3,4 has C42C_{4}^{2} methods. At this time, a=ca=c is the smaller of the chosen numbers, with only one way to choose, and b=db=d is the remaining number, hence the number of four-digit numbers at this time is C4211=6C_{4}^{2} \cdot 1 \cdot 1=6.
In summary, by the principle of addition, the number of different four-digit numbers that meet the conditions is 6+16+6=286+16+6=28.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.