[Guest]

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?

[Guest]

probably not right but...

12⁵

[superprismatic]

probably not right but...

12⁵

I exhausted on 4-long duodecimal numbers. I get 1344=2⁶*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.

[roolstar]

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 October 28, 2009 by roolstar

[roolstar]

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=2⁶*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 October 28, 2009 by roolstar

[Guest]

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 12⁵ combinations. I'm not sure if this is the maximum though.

[roolstar]

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 12⁵ 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 October 29, 2009 by roolstar

[superprismatic]

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.

[roolstar]

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 October 29, 2009 by roolstar

[Guest]

I have come up with a proof that

12⁹

combinations can be made.

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 d^n-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 d^2-1.

Now consider a k digit ID which we assume to have d^k-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 d^k-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 * d^k-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 October 29, 2009 by psychic_mind

[roolstar]

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!!

Still this doen't mean I am not convinced of your answer...

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 October 29, 2009 by roolstar

[Guest]

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 October 29, 2009 by psychic_mind

[roolstar]

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 October 29, 2009 by roolstar

[Guest]

For a 10 digit duodecimal number, in all 12¹⁰ 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 12⁸ 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:

12⁹ x 11

[Guest]

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 October 29, 2009 by mmiguel1

[Guest]

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.

[Guest]

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.