Jump to content
BrainDen.com - Brain Teasers
  • 0

Guest

Asked by Guest,

 Share

Question

Guest

Guest

Posted
Posted

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?

Link to comment
Share on other sites

16 answers to this question

Recommended Posts

  • 0
superprismatic Mentor

superprismatic

Posted
Posted
  On 10/28/2009 at 9:30 PM, psychic_mind said:

probably not right but...

  Reveal hidden contents

125

  Reveal hidden contents

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.

Link to comment
Share on other sites
  • 0
roolstar Community Regular

roolstar

Posted
Posted (edited)

  Reveal hidden contents

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

  Reveal hidden contents

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
Link to comment
Share on other sites
  • 0
roolstar Community Regular

roolstar

Posted
Posted (edited)

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

Corrections in RED:

  On 10/28/2009 at 9:55 PM, roolstar said:

  Reveal hidden contents

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

  Reveal hidden contents

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

  On 10/28/2009 at 9:53 PM, superprismatic said:

  Reveal hidden contents

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

  Reveal hidden contents

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
Link to comment
Share on other sites
  • 0
Guest

Guest

Posted
Posted

This was my system

  Reveal hidden contents

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.

Link to comment
Share on other sites
  • 0
roolstar Community Regular

roolstar

Posted
Posted (edited)
  On 10/28/2009 at 11:31 PM, psychic_mind said:

This was my system

  Reveal hidden contents

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

  Reveal hidden contents

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,

  Reveal hidden contents

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
Link to comment
Share on other sites
  • 0
superprismatic Mentor

superprismatic

Posted
Posted
  On 10/28/2009 at 10:47 PM, roolstar said:

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

Corrections in RED:

As for the below

  Reveal hidden contents

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.

Link to comment
Share on other sites
  • 0
roolstar Community Regular

roolstar

Posted
Posted (edited)

  Reveal hidden contents

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
Link to comment
Share on other sites
  • 0
Guest

Guest

Posted
Posted (edited)

I have come up with a proof that

  Reveal hidden contents

129

combinations can be made.

  Reveal hidden contents

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.

  Reveal hidden contents

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

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

Edited by psychic_mind
Link to comment
Share on other sites
  • 0
roolstar Community Regular

roolstar

Posted
Posted (edited)
  On 10/29/2009 at 2:28 PM, psychic_mind said:

  Reveal hidden contents

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

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

  Reveal hidden contents

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 by roolstar
Link to comment
Share on other sites
  • 0
Guest

Guest

Posted
Posted (edited)

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

  Reveal hidden contents

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
Link to comment
Share on other sites
  • 0
roolstar Community Regular

roolstar

Posted
Posted (edited)
  On 10/29/2009 at 3:40 PM, psychic_mind said:

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

  Reveal hidden contents

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
Link to comment
Share on other sites
  • 0
Guest

Guest

Posted
Posted

  Reveal hidden contents

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

Link to comment
Share on other sites
  • 0
Guest

Guest

Posted
Posted (edited)

  Reveal hidden contents

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
Link to comment
Share on other sites
  • 0
Guest

Guest

Posted
Posted

I'm sorry DeeGee but I agree with Psychic

  Reveal hidden contents

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.

Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

×
 Share
Go to question listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...