2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Jim this was a fun little puzzle. Seems to me there could be more questions that have to do with these road signs that might be fun... were you thinking of asking more? $\endgroup$ – Dark Thunder Jun 7 at 14:07
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I think you've double counted. For example, the sign with 3s on one side and 6s on the other is the same as the one with 6s on one side and 3s on the other, imo. $\endgroup$ – hexomino Jun 7 at 13:28
  • 2
    $\begingroup$ @hexomino The OP says there are a full $10^K$ road signs - that must include both (front 333, back 666) and (front 666, back 333) as two separate signs. $\endgroup$ – Rand al'Thor Jun 7 at 13:30
  • $\begingroup$ Ah, yes, my mistake, sorry. $\endgroup$ – hexomino Jun 7 at 13:31
  • $\begingroup$ I did the same thing, so I'm guessing you also feel a little silly for separating out those ten "case 1" signs only to see your equation in "case 2" would have accounted for them. $\endgroup$ – Dark Thunder Jun 7 at 13:42
  • $\begingroup$ @DarkThunder I did consider putting both cases together, but decided to keep them separate because it's easier this way to be sure there's no double-counting. $\endgroup$ – Rand al'Thor Jun 7 at 13:43
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Your answer differs from Rand al’Thor’s by one. Which of you is miscounting? $\endgroup$ – Rubio Jun 7 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.