Question

Consider the set S of all integers between and including 1000 and 99999. Call two integers x and y in S to be in the same equivalence class if the digits appearing in x and y are the same. For example, if x = 1010, y = 1000 and z = 1201, then x and y are in the same equivalence class, but y and z are not. Find the number of distinct equivalence classes that can be formed out of S.

Answer 1

@Kainui

Answer 2

@ganeshie8

Answer 3

HI!!

Answer 4

do you know what you are really looking for?

Answer 5

Well, I am sort of confused with the question.

Answer 6

Since it states clearly that 1010 and 1000 are in the same equivalence class.Whence, I can assume that by equivalence class it means the digits present in the number. But no sure about anything.

Answer 7

For example 1111 is the equaivlence class 1, similarly 2222 is 2 and so on. so, to get that we can have 10C1 that for a single digit equivalence class. Continuing in the same fashion we can find for like 2121 and 2211 are in the same equivalence class 21 which means like two digit classes are 10C2.

Answer 8

Aha! I think you must only generate a single representative from the equivalence classes to find them all!

Answer 9

What contradictory is the fact about the class where equivalence is 11.

Answer 10

Oh ok I see you are already doing this, my mistake

Answer 11

Then are we just looking for combinations of distinct digits?
would it be something like 9 + 10*9 + 10*9*8 + 10*9*8*7 + 10*9*8*7*6?

Answer 12

1000 ~ 1010 ~ 01

Answer 13

I can have atmost 5 order equivalence class. Which means 10C1+10C2+10C3+10C4+10C5 - 1 the equivalence class where order is 0. But the contradiction arises about the equivalence class 11. Cause that is same as 1.

Answer 14

0 is still a digit, maybe I should have written

1000 ~ 1010 ~ 10

since 0s to the left of a number don't count as digits for counting in the equivalence class I think.

Answer 15

I don't think there is a contradiction, since factorials are counting unique choices you won't ever choose 11 in the 10C2 term.

Answer 16

10C2 = 10*9 different choices without repeats right? Or maybe I misunderstand haha

Answer 17

10C2 = (10*9)/2

Answer 18

Oh ok, then that doesn't seem right. I'm thinking the ways of picking the representatives of the equivalence classes must then be:

9+10*9+10*9*8+10*9*8*7

Answer 19

Ah so
9 + 10C2 + 10C3 + 10C4 + 10C5

Answer 20

I think I'm totally off actually I have actually answered a completely different question that I accidentally got in my mind than the real question at hand... 3_#

Answer 21

I think 10C1+10C2+10C3+10C4+10C5-1 is the solution which is same as @LollyLau Stated. Whence, we can state that Any set of distinct digits with maximum order 5 is a equivalence class that can be formed except 0

Answer 22

Yeah ok I totally agree and I understand why no after I worked it out on my paper a little I see why! Cool

Answer 23

Cheers

Answer 24

This reminds me of a thing called the 'complexity function' C(n). If you're given some set of symbols, \(\{0,1,2,3,4,5,6,7,8,9,+, *, \text{^}\}\) then the complexity of a number is the smallest possible combination of all the symbols to create your number. For instance,

C(16384)=4
because although naively we could say it might be 5 because it has 5 digits, it has representation with 4 symbols,

2^14

Anywho, just thought I'd share a fun thing.

Answer 25

@Kainui : I sorry I might sound dumb, but how is it 2^14. Please explain.