Finding numbers having exactly two distinct digits

Question

We have $10^K$ road signs (numbered 0 through $10^K−1$).
For each valid $i$, the sign with number $i$ has the integer $i$ written on one side and $10^K−i−1$ written on the other side.

We need to find how many road signs have exactly two distinct decimal digits written on them (on both sides in total)?

For example, if $K=3$, the two integers written on the road sign $363$ are $363$ and $636$, and they contain two distinct digits 3 and 6, but on the road sign $362$, there are integers $362$ and $637$, which contain four distinct digits — $2, 3, 6, 7$. On the road sign $11$, there are integers $11$ and $988$, which contain three distinct digits — $1, 9, 8$.

Devise a procedure to find the number of road signs for any given value of $K$.

______

Source: https://www.codechef.com/JUNE19B/problems/RSIGNS

Answer 1

Fix $K$. We will find conditions on $i$ for the road sign numbered $i$ to be as desired.

Write $i$ as a $K$-digit number, say $i=i_1i_2i_3\dots i_K$ where each $i_k$ may be any digit from zero to nine. (Thus, we account for numbers with fewer digits as well as those with the maximal number $K$, by allowing leading zeros.)

The front of the sign has the digits $i_k$ for $1\leq k\leq K$ and the back of the sign has the digits $9-i_k$ for $1\leq k\leq K$.

So there are two possible cases:

• Case 1: all the $i_k$ are equal (10 possibilities).

• Case 2: each $i_k$ is one of exactly two fixed digits which sum to nine. There are five choices for this pair of digits ($\{0,9\},\{1,8\},\{2,7\},\{3,6\},\{4,5\}$), and then $2^K-2$ possible numbers $i$ using each pair of digits (two choices for each of the $K$ digits making $2^K$, minus the two numbers already counted which only use one of the pair).

Total number of possibilities:

$(10)+5\times(2^K-2)=5\times2^K$.

Answer 2

After running the below script through K=5, I devised the following formula:

$K_n = K_{n-1} + 10 \times 2^{k-1}$

Quickly whipped together this R script, adjust K as desired.

library(stringr)

k<-4

roadsign<-data.frame(cbind(rep(NA,10^k),rep(NA,10^k)))

for(i in 1:(10^k-1)){
  roadsign[i,]<-c(as.character(i),as.character(10^k-i-1))
}

roadsign<-paste(roadsign$X1,roadsign$X2)

stringmatrix<-data.frame(matrix(ncol=10,nrow=10^k))

for(i in 1:length(roadsign)){
stringmatrix[i,]<-str_count(roadsign[i],c('0','1','2','3','4','5','6','7','8','9'))
}


for (i in 1:(10^k)) {
  for(j in 1:10){
if(stringmatrix[i,j]>0){stringmatrix[i,j]<-1}
  }
}
stringmatrix$sum<-rowSums(stringmatrix)

nrow(subset(stringmatrix,stringmatrix$sum==2))

K=2 gives 19, K=3 gives 39, K=4 gives 79