BrainDen.com - Brain Teasers
• 0

## Question

Planet Realmnoir uses the duodecimal system in its every day transactions. The federal government of Realmnoir has decided to issue new ID cards to its citizens. Under this scheme, each citizen will be assigned a different 10 digit duodecimal identification (ID) number. Any given ID number may contain leading zeroes.

For ease of record keeping, it has been decided that any two ID numbers must differ in at least two places.

What is the maximum number of ID cards that can be issued under this scheme?

## Recommended Posts

• 0

probably not right but...

125

##### Share on other sites
• 0

probably not right but...

125

I exhausted on 4-long duodecimal numbers. I get 1344=26*3*7, not a power of 12.

I'm very intrigued by this problem and I have no clue as to how to attack it. I'll be working on it and checking back frequently. I've tried to find info about such things on the web with no luck.

##### Share on other sites
• 0

10^10 = Total possiblilities with 10 digits

Now for each one of the above IDs, the number of similar IDs (ones with only 1 digit changed) is 9*10 (each digit can be changed 9 different ways ALONE, either that digit OR another, so 9*10 and not 9^10)

Therefore:

TOTAL DIFFERENT IDs = 10^10/9*10 = 10^9/9

I just realized the duodecimal thing so:

12^10 = Total possiblilities with 10 digits of duodecimal thing

Now for each one of the above IDs, the number of similar IDs (ones with only 1 digit changed) is 11*10 (each digit can be changed 11 different ways ALONE, either that digit OR another, so 11*10 and not 11^10)

Therefore:

TOTAL DIFFERENT IDs = 12^10/11*10

Not a power of 12 I might add...

Hope I'm right...

Edited by roolstar
##### Share on other sites
• 0

JMust realized an error in my previous post and too late to change it.

Corrections in RED:

10^10 = Total possiblilities with 10 digits

Now for each one of the above IDs, the number of similar IDs (ones with only 1 digit changed) is 10*10 (each digit can be changed 10 different ways ALONE, either that digit OR another, so 10*10 and not 10^10)

Therefore:

TOTAL DIFFERENT IDs = 10^10/10*10 = 10^8

I just realized the duodecimal thing so:

12^10 = Total possiblilities with 10 digits of duodecimal thing

Now for each one of the above IDs, the number of similar IDs (ones with only 1 digit changed) is 12*10 (each digit can be changed 12 different ways ALONE, either that digit OR another, so 12*10 and not 12^10)

Therefore:

TOTAL DIFFERENT IDs = 12^10/12*10 = 12^9/10

Not a power of 12 I might add...

Hope I'm right...

As for the below

I exhausted on 4-long duodecimal numbers. I get 1344=26*3*7, not a power of 12.

The numbers of IDs should be 12^4/12*4 = 432

Are you sure you're not counting similar IDs more than once? More than 3 times even?

Edited by roolstar
##### Share on other sites
• 0

This was my system

Simply group consecutive pairs of digits (i.e the 1st & 2nd, 3rd & 4th etc) and these pairs will always have the same digit as each other. This would make it like a five digit number but it would actually have 10 digits and there would always be 2 differences from every other number. This gives 125 combinations. I'm not sure if this is the maximum though.

##### Share on other sites
• 0

This was my system

Simply group consecutive pairs of digits (i.e the 1st & 2nd, 3rd & 4th etc) and these pairs will always have the same digit as each other. This would make it like a five digit number but it would actually have 10 digits and there would always be 2 differences from every other number. This gives 125 combinations. I'm not sure if this is the maximum though.

At least one of us has misunderstood the OP

The way I saw it was that

ID#1: 1234567890

and

ID#2: 1234567891

and

ID#3: 2234567890

ID# 1,2 & 3 are accepted as one same ID (they only differ at 1 place!)

So,

You did find some identical IDs but not all of them, in fact you only studied one particular case instead of the millions others...

Example:

ID#1: 1122334455

and

ID#2: 2222334455

are actually different

but so is

ID#3: 1212334455 with 2 differences!

and your 12^5 does not cover the likes of ID#3

In my formula, the 12^10 possibilities are grouped into 10*12 groups of identical IDs => Number = 12^10/(10*12)

BTW I MISSED THE PARENTHISIS IN MY LAST POSTS...

Please remember that this is based on how I understood the OP...

Edited by roolstar
##### Share on other sites
• 0

JMust realized an error in my previous post and too late to change it.

Corrections in RED:

As for the below

The numbers of IDs should be 12^4/12*4 = 432

Are you sure you're not counting similar IDs more than once? More than 3 times even?

Yes, I am sure. I checked all pairs of the 1344 and they all differ by at least 2. I tried to attach the file but it just sat there spinning a wheel -- nothing was uploaded. I tried the basic uploader, but I couldn't figure out how to use it -- there was no mention of uploading when I tried to use it.

##### Share on other sites
• 0

I think I underestimated the number there...

In fact, in my method, every ID# was removed 12 times!!!!

and so the final formula would be multiplied by 12:

(12^10/(12*10))*12 = 12^10/10

or 12^n/n n being the length of the ID#

in the 4-long ID# it's:

(12^4/(12*4))*12 = 12^4/4 = 5184

But still didn't get the 1344 Number there...

It seems I'm missing something...

Better sleep on it!

Edited by roolstar
##### Share on other sites
• 0

I have come up with a proof that

129

The proof is for a more general case if you have a d-base system with an n digit ID. I have used an inductive method to show that dn-1 combinations can be made so that there will always be 2 differences with every other number.

It is easy to show that for a 2 digit ID (n=2) then you only have d possibilities. Which agrees with d2-1.

Now consider a k digit ID which we assume to have dk-1 combinations that have 2 or more differences from each other. If we increase the left digit by 1 (or cycle it back to 0) for each combinations, then this new set of dk-1 IDs will also be different in 2 places from each other. Similarly if we increase this digit by 2 we will have another set. We can therefore generate d sets of such IDs by changing the left digit like this.

Any ID in a set will have at least 2 differences with any other in the set.

Any ID in a set will have at least 1 difference with any ID from another set.

Now consider an ID with k+1 digits. Assume this new digit is placed on the left (not really important though). We have d sets of k digit IDs. For each set make this new digit a different number and combine them. Hence where there was only 1 difference between any two IDs from different sets there will now be 2 because this new digit-will be different. There are therefore d * dk-1 = d(k+1)-1 and therefore this formula still holds for n=k+1.

This proof/method can be used to generate such sets of IDs.

For example the 27 4-digit base 3 IDs you can make are:

```0000 1100 2200

0011 1111 2211

0022 1122 2222

0110 1210 2010

0121 1221 2021

0102 1202 2002

0220 1020 2120

0201 1001 2101

0212 1012 2112

```

Feel free to check any of this. If I have made a mistake I'd like to know.

Edited by psychic_mind
##### Share on other sites
• 0

For example the 27 4-digit base 3 IDs you can make are:

```0000 1100 2200

0011 1111 2211

0022 1122 2222

0110 1210 2010

0121 1221 2021

0102 1202 2002

0220 1020 2120

0201 1001 2101

0212 1012 2112

```

Feel free to check any of this. If I have made a mistake I'd like to know.

Man do I wish you picked another example:

In this particular example, our 2 different formulas yield the same result!!!

Psychic N = d^(n-1) = 3^3 = 27

Rool's N = d^n/n = 3^4/3 = 3^3 = 27

What a coincidence!!

So if you've already written a program, can you please develop a 4-digit number base 5??

In fact I'm rather sckeptical about my formula since we cannot guarantee it's going to be a whole number in every case!!!!!!!!! And even more sckeptical about the spelling of the word skeptical!

I'm just trying to figure out the error in my , usually flawless, logic... and humility....

Edited by roolstar
##### Share on other sites
• 0

Unfortunately I haven't written a program but I think it would be quicker to do by hand anyway.

```
0000 1100 2200 3300 4400

0011 1111 2211 3311 4411

0022 1122 2222 3322 4422

0033 1133 2233 3333 4433

0044 1144 2244 3344 4444

0110 1210 2310 3410 4010

0121 1221 2321 3421 4021

0132 1232 2332 3432 4032

0143 1243 2343 3443 4043

0104 1204 2304 3404 4004

0220 1320 2420 3020 4120

0231 1331 2431 3031 4131

0242 1342 2442 3042 4142

0203 1303 2403 3003 4103

0214 1314 2414 3014 4114

0330 1430 2030 3130 4230

0341 1441 2041 3141 4241

0302 1402 2002 3102 4202

0313 1413 2013 3113 4213

0324 1424 2024 3124 4224

0440 1040 2140 3240 4340

0401 1001 2101 3201 4301

0412 1012 2112 3212 4312

0423 1023 2123 3223 4323

0434 1034 2134 3234 4334

```

Wow that took a while. Maybe I should write a program after all.

Also have you inputted the numbers correctly into your formula? It looks like the denominator should be 4.

Edited by psychic_mind
##### Share on other sites
• 0

Unfortunately I haven't written a program but I think it would be quicker to do by hand anyway.

```
0000 1100 2200 3300 4400

0011 1111 2211 3311 4411

0022 1122 2222 3322 4422

0033 1133 2233 3333 4433

0044 1144 2244 3344 4444

0110 1210 2310 3410 4010

0121 1221 2321 3421 4021

0132 1232 2332 3432 4032

0143 1243 2343 3443 4043

0104 1204 2304 3404 4004

0220 1320 2420 3020 4120

0231 1331 2431 3031 4131

0242 1342 2442 3042 4142

0203 1303 2403 3003 4103

0214 1314 2414 3014 4114

0330 1430 2030 3130 4230

0341 1441 2041 3141 4241

0302 1402 2002 3102 4202

0313 1413 2013 3113 4213

0324 1424 2024 3124 4224

0440 1040 2140 3240 4340

0401 1001 2101 3201 4301

0412 1012 2112 3212 4312

0423 1023 2123 3223 4323

0434 1034 2134 3234 4334

```

Wow that took a while. Maybe I should write a program after all.

Also have you inputted the numbers correctly into your formula? It looks like the denominator should be 4.

I'm forgetting something. It seems there's something I'm not counting, or more precisely, removing more than once! See, my final formula in post#7 was: d^n/n. Very close to yours, but where did I go wrong?

Eureka! I simply multiplied by "d" instead of "n"... This would've got me the same results.

I am now sure that your formula stands... Great job...

Thanks for the effort...

Edited by roolstar
##### Share on other sites
• 0

For a 10 digit duodecimal number, in all 1210 diferent numbers can be made (different in at least 1 place)

For two places to be different:

Consider a 8 digit number. Then there exist 128 numbers where at least one digit is different.

Now, on these 8 digit numbers place 2 more digits such that atleast one of them is different. This can be done in 12*11 ways (just like 10x9 2-digit numbers in base 10)

So, the total numbers where atleast 2 digits are different are:

129 x 11

##### Share on other sites
• 0

Duodecimal = Base 12

Must differ in two places:

8 digits can be the same: 12^8 possibilities

3 cases

If two digits are the same, this can apply for 12 types of digits, and these can exist at 10 choose 2 (45) positions

If 1 digit is the same, this can apply for 12 types of digits at positions 10 choose 1 (10), the remaining digit must differ between the two ID numbers and it can differ in 12*11 ways at 9 choose 1 (9) positions

If 0 digits are the same, then the first digit can differ in 12*11 ways at 10 choose 1 (10) positions and the second can differ in 12*11 ways at 9 choose 1 (9) positions

Totalling:

12^8 * (12*45 + 12*10 * 12*11*9 + 12*11*10*12*11*9 )

735810477096960 numbers

Factoring out a 12

12^9 (45 + 12*11*10*9 + 12*11*11*10*9)

It is easy to make a mistake in this sort of reasoning.

So if I am wrong, let me know.

Edited by mmiguel1
##### Share on other sites
• 0

I'm sorry DeeGee but I agree with Psychic

basically straight counting will have only the lowest digit change for = number of times as the base you are counting in so you must use an extra digit to make sure there are 2 differences so the best you can do is 12^9 for a 10 digit number using base 12. Next we have to consider cases when the 9 digit number (excluding the extra digit required) can differ by only 1 digit in 2 dimensions. It can differ by the 1st digit, or by one of the 8 digits above, but luckily we have base 12 so there are more than enough digits in the 'extra' digit that can be used to keep counting where 2 digits differ.

##### Share on other sites
• 0

12^9

In general, I get b^(k-1) qualifying IDs, where b is the base and k is the number of digits.

Looks like that’s a vote for psychic_mind’s post.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.