Two years ago, a problem surfaced at the Romankachi Pharmaceuticals Ltd. – one of the many companies belonging to the huge Romankachi conglomerate.
We were devising a three digit id (non-zero first digit) for the employees such that no two employees can have id’s that are identical when written in the reverse order. For example, 123 and 321 are identical and hence only one of them can exist. Also, a 3-digit id starting with a 0 was invalid since the machine used for swiping does not recognize a 3-digit id starting with a 0.
After a lot of careful analysis and discussion, we were able to figure out the maximum number of employees that could use this system. Can you repeat the feat?
Answer
It has been mentioned that a 3-digit code starting with a 0 is invalid. Hence we cannot use codes from 001 to 099.
Hence the total number of valid 3-digit id’s is 900.
Out of these, three-digit numbers that are symmetrical will have the same first and the last digit. The first and the last digit in this case can be selected in 9 ways(any number from 1 to 9). The second digit can be selected in 10 ways(any number from 0 to 9). Therefore, the number of symmetrical three-digit numbers = 910 = 90. These 90 id’s will not have a corresponding number when written in reverse order. Secondly, numbers ending with a zero will also not have a corresponding 3-digit number when written in reverse order. For example, the reverse of 910 is 019 which is not a valid three-digit code due to the condition given that 3-digit codes starting with 0 are invalid. The number of such three-digit numbers = 910 = 90.
The rest of the (900-180) = 720 numbers can be classified into two groups of 360 numbers each, where corresponding pairs of numbers will be identical when written in reverse order. Hence consider only 360 of these numbers.
Therefore, the total number of valid employee id’s possible = 90 + 90 + 360 = 540.
