PUMaC 2017 · 组合（A 组） · 第 2 题

PUMaC 2017 — Combinatorics (Division A) — Problem 2

Call a number unremarkable if, when written in base 10, no two adjacent digits are equal. For example, 123 is unremarkable, but 122 is not. Find the sum of all unremarkable 3-digit numbers. (Note that 012 and 007 are not 3-digit numbers.)

解析

First, we will find the sum N of all unremarkable numbers with at most k digits. If n k is unremarkable, then we may subtract each digit from 9 and obtain a new unremarkable k 10 − 1 number, so the average of all the unremarkable numbers with at most k digits is . The 2 k − 1 number of unremarkable numbers with at most k digits is 10 × 9 , so ( ) k ( ) 10 − 1 k − 1 N = 10 × 9 . k 2 We compensate for the fact that the single-digit numbers have been excluded (since their complements are of the form 99 ), so we add back 45. Thus, the desired number is 999 99 N − N + 45 = (810) − (90) + 45 = 400185 . 3 2 2 2 Problem written by Matt Tyler 1