Equivalence classes of the relation that the largest digit of integer a = largest digit of integer b.

Question

Define the relation $\mathcal{R}$ on the set of all positive integers by: for all positive integers $a$ and $b$, $a\,\mathcal{R}\,b$ if and only if the largest digit of $a$ is equal to the largest digit of $b$. for example, $271\,\mathcal{R}\,770$ because the largest digit of $271$ is $7$ which is also the largest digit of $770$.

a) Find the number of equivalence classes of $\mathcal{R}$.

b) Find and simplify the number of positive integers between $100$ and $1000$ which are in the equivalence class $[271]$.

I have an idea of where to begin but I think I am wrong. For (a) would there be $9$ equivalence classes? And for (b) I got my answer to be $56$.

Answer 1

Your answer to (a) is correct. There is one equivalence class for each possible largest digit, and since you’re looking only at positive integers, the largest digit must be non-zero.

For (b) you need to count the three-digit numbers whose largest digit is $7$. One of these is $777$. How many are there with exactly two sevens? There are $3$ places to put the digit that isn’t $7$, and it must be one of the seven digits $0,1,2,3,4,5,6$, so there are $3\cdot7=21$ such numbers. OOPS: one of those is $077$, which isn’t in the required range. Thus, there are really only $20$ of them. Now how many are there with exactly one $7$? If the $7$ is the first digit, there are $7^2=49$ ways to fill out the other two places with digits less than $7$. Otherwise the first digit must be one of the six digits $1,2,3,4,5,6$. There are then $2$ places to put the $7$ and $7$ choices for the other digit, for a total of $6\cdot2\cdot7$ possibilities. Thus, there are $49+84=133$ numbers with exactly one $7$. The grand total for (b) is therefore $1+20+133=154$.

Answer 2

Part (a) sounds about right to me. In part (b), your count is a bit too low:

• There are 49 numbers of the form $7XY$ with $0\leq X,Y<7$
• Another 7 are of the form $77X$ (with $0\leq X<7$)
• There is certainly number $777$

This already adds up to $49+7+1=57$ and we didn't include all the possible forms yet.

Answer 3

Hint: You are correct for a. For b, it would be easier if you explain how you got $56$. There are more than that. How many are in the range $700-799?$ Intuitively, class $9$ must be the largest and there are a total of $901$ so $56$ seems small.

Answer 4

a) is fine as for each digit except $0$ we have an equivalence class

b) It is easy to count all numbers between $100\le n<1000$ which have only digits $\le 7$: There are $7\cdot 8\cdot 8$. However, some of them have all digits strictly less than $7$, namely those with all digits $\le 6$: There are $6\cdot 7\cdot 7$ of these. Take the difference.

Answer 5

You're right on target for (a).

You can find the answer to (b) as follows:

Let's start by taking care of the numbers in $[271]$ whose first digit is $7$. The last two digits of such a number will need to be at most $7$, so we have $8$ options for each of the last two digits, and so there are $8\cdot 8=64$ ways we can pick the last two digits of such a number. Thus, there are $64$ numbers in $[271]$ between $100$ and $1000$ whose first digit is $7$.

Now, if the second digit is $7$ and the first digit is not $7$, then how many options are there for the first digit? How many options for the last? Multiply these together to get the number of elements of $[271]$ between $100$ and $1000$ with second digit $7$ and first digit not $7$.

If the last digit is $7$ and neither the first two digits is $7$, then how many options are there for the first digit? How many for the second? Multiply these two numbers together to get the number of elements of $[271]$ between $100$ and $1000$ with last digit $7$ and first two digits not equal to $7$.

You should be able to show that every element of $[271]$ between $100$ and $1000$ is of exactly one of the three types we discussed above, so we just add up the numbers of each type of element to get the answer.