Maths Olympiad Prep

Library / /234 of 462

Combinatorics Difficulty 5.8 AIME, harder Prove it Ireland

How many 4-digit numbers ABCDABCD are there with the property that
AB=BC=CD? |A - B| = |B - C| = |C - D|?
Note that the first digit AA of a four-digit number ABCDABCD cannot be zero.

Solutions — 3

Solution 1

16.
Let d=AB=BC=CDd = |A - B| = |B - C| = |C - D| then dd can take the values 0,1,2,3,4,5,6,7,8,90, 1, 2, 3, 4, 5, 6, 7, 8, 9. For d=0d = 0 we find 9 numbers 1111,2222,3333,4444,5555,6666,7777,8888,99991111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999. For other values of dd, we take each of the eight sequences
+++,++,++,+,+++,+,+, +++, ++-, +−+, +−−, −+++, −+−, −−+, −−−
and find possible starting points to produce numbers with that particular sequence indicating for each digit whether the next digit is smaller or larger.

Case 1. `+++` (9 solutions)
d=1d = 1 gives 1234,2345,3456,4567,5678,67891234, 2345, 3456, 4567, 5678, 6789
d=2d = 2 gives 1357,2468,35791357, 2468, 3579
d=3,4,5,6,7,8,9d = 3, 4, 5, 6, 7, 8, 9 do not give further solutions.

Case 2. `++−` (16 solutions)
d=1d = 1 gives 1232,2343,3454,4565,5676,6787,78981232, 2343, 3454, 4565, 5676, 6787, 7898
d=2d = 2 gives 1353,2464,3575,4686,57971353, 2464, 3575, 4686, 5797
d=3d = 3 gives 1474,2585,36961474, 2585, 3696
d=4d = 4 gives 15951595

Case 3. `+-+` (36 solutions)

ddNumbers
111212,2323,3434,4545,5656,6767,7878,89891212, 2323, 3434, 4545, 5656, 6767, 7878, 8989
221313,2424,3535,4646,5757,6868,79791313, 2424, 3535, 4646, 5757, 6868, 7979
331414,2525,3636,4747,5858,69691414, 2525, 3636, 4747, 5858, 6969
441515,2626,3737,4848,59591515, 2626, 3737, 4848, 5959
551616,2727,3838,49491616, 2727, 3838, 4949
661717,2828,39391717, 2828, 3939
771818,29291818, 2929
8819191919

Case 4. `+--` (20 solutions)
ddNumbers
111210,2321,3432,4543,5654,6765,7876,89871210, 2321, 3432, 4543, 5654, 6765, 7876, 8987
222420,3531,4642,5753,6864,79752420, 3531, 4642, 5753, 6864, 7975
333630,4741,5852,69633630, 4741, 5852, 6963
444840,59514840, 5951

Case 5. `-++` (20 solutions)
ddNumbers
111012,2123,3234,4345,5456,6567,7678,87891012, 2123, 3234, 4345, 5456, 6567, 7678, 8789
222024,3135,4246,5357,6468,75792024, 3135, 4246, 5357, 6468, 7579
333036,4147,5258,63693036, 4147, 5258, 6369
444048,51594048, 5159

Case 6. `-+-` (45 solutions)
ddNumbers
111010,2121,3232,4343,5454,6565,7676,8787,98981010, 2121, 3232, 4343, 5454, 6565, 7676, 8787, 9898
222020,3131,4242,5353,6464,7575,8686,97972020, 3131, 4242, 5353, 6464, 7575, 8686, 9797
333030,4141,5252,6363,7474,8585,96963030, 4141, 5252, 6363, 7474, 8585, 9696
444040,5151,6262,7373,8484,95954040, 5151, 6262, 7373, 8484, 9595
555050,6161,7272,8383,94945050, 6161, 7272, 8383, 9494
666060,7171,8282,93936060, 7171, 8282, 9393
777070,8181,92927070, 8181, 9292
888080,91918080, 9191
9990909090

Case 7. +--+ (20 solutions)
d=1d=1 gives 2101,3212,4323,5434,6545,7656,8767,98782101, 3212, 4323, 5434, 6545, 7656, 8767, 9878
d=2d=2 gives 4202,5313,6424,7535,8646,97574202, 5313, 6424, 7535, 8646, 9757
d=3d=3 gives 6303,7414,8525,96366303, 7414, 8525, 9636
d=4d=4 gives 8404,95158404, 9515
d=5,6,7,8,9d=5, 6, 7, 8, 9 do not give further solutions.

Case 8. --- (12 solutions)
d=1d=1 gives 3210,4321,5432,6543,7654,8765,98763210, 4321, 5432, 6543, 7654, 8765, 9876
d=2d=2 gives 6420,7531,8642,97536420, 7531, 8642, 9753
d=3d=3 gives 96309630

Adding the 9 with d=0d=0 to the count for each ++- pattern, we obtain
9+9+16+36+20+20+45+20+12=1879 + 9 + 16 + 36 + 20 + 20 + 45 + 20 + 12 = 187.

Solution 2

Let d=BAd = B - A so dd can take integer values from 9-9 to 99 inclusive. If d=0d = 0 then there are 99 cases. So let us consider d0d \neq 0. We will first count the cases including those where A=0A = 0 is permitted and then subtract those cases starting with zero.
When d0d \neq 0, there are four possible patterns for the three differences, namely
* Case (d,d,d)(d, -d, d). This requires two distinct digits separated by a gap d|d|, with 10d10 - |d| cases.
* Cases (d,d,d)(d, d, -d) and (d,d,d)(d, -d, -d). This requires three distinct digits in arithmetic progression, with 102d10-2|d| cases if d4d \le 4 and none otherwise.
* Case (d,d,d)(d, d, d). This requires four digits in arithmetic progression with gap of d|d|, i.e. the smallest digit aa must satisfy a+3d9a+3|d| \le 9, which gives 103d10-3|d| cases if d3|d| \le 3 and no cases otherwise.
Now let us enumerate the cases with initial digit A=0A = 0 and d0d \neq 0. There are no examples with d<0d < 0. If d>0d > 0, the difference pattern (d,d,d)(d, -d, -d) is impossible as it results in a negative final digit. The pattern (d,d,d)(d, -d, d) has solutions for any 1d91 \le d \le 9, the pattern (d,d,d)(d, d, -d) has solutions for any 1d41 \le d \le 4, the pattern (d,d,d)(d, -d, -d) has no solutions as the final digit cannot be negative, while the case (d,d,d)(d, d, d) has a solution if 1d31 \le d \le 3.

We can now summarise all the cases according to the value of d|d| in the following table.

$d$d<0d < 0d>0d > 0A0A \neq 0
09
13232-3
22424-3
31616-3
41010-2
555-1
644-1
733-1
822-1
911-1
Total187

The solution to the problem then is 187 cases.

Solution 3

Let d=AB=BC=CDd = |A - B| = |B - C| = |C - D|.
For each value of dd from 0 to 9, set up a tableau with 4 rows (numbered 1 to 4) and 10 columns (numbered 0 to 9). The number n(r,c)n(r, c) in row rr and column cc is the number of rr-digit numbers, ending in the digit cc, that have an absolute difference of dd between adjacent digits.

In row 1, for all dd we have n(1,0)=0n(1,0) = 0 because there is no 1-digit number ending in zero, while n(1,c)=1n(1,c) = 1 for 1c91 \le c \le 9. In subsequent rows, by considering appending a final digit to a number of r1r-1 digits, n(r,c)n(r,c) is the sum of n(r1,cd)n(r-1,c-d) and n(r1,c+d)n(r-1,c+d) when d>0d > 0. These summands are taken to be zero if the reference overspills the tableau, i.e. if cd<0c - d < 0 or cd>9c - d > 9. In the special case d=0d = 0, the rows are all equal to the first row. The tableaux are shown below.

d=0d = 0c=c =0123456789Total
r=1r = 10111111111
r=2r = 20111111111
r=3r = 30111111111
r=4r = 401111111119

The total of the totals is 187.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.