Math Is Fun Forum

uzurpatorul

Member

Registered: 2009-06-25

Posts: 11

confusable IDs

The University is considering issuing new student ID cards (again!). Each student will be assigned a 5 digit identification number from 00000 to 99999. For ease in record keeping, the registrar has requested that any two ID numbers differ in at least two places. How many ID's could the registrar issue?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: confusable IDs

Hi uzurpatorul;

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Fruityloop

Member

Registered: 2009-05-18

Posts: 143

Re: confusable IDs

Bobbym's answer is given as being correct on the website but it doesn't seem correct.
I guess the reasoning is that if we have five numbers and if we cycle through all combinations for three of them and multiply that by the different combinations of three out of five we will have the answer.   So we have 1000(000-999)*5C3 = 10,000.
So 123XX will be different from XX311, but we can choose 11 for the first number and 12 for the second number and we have the same number!
Each number selected eliminates 45 other numbers, so the total number of possible IDs is only 1/46 of the total. So 100000/46 = 2173 possible IDs.  I'm not totally sure my answer is correct.
Anybody else have any ideas?

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: confusable IDs

I agree with 10,000.

One way of doing this would be to have the first four digits counting from 0 to 9999, then have the last digit as their sum mod 10.

00000
00011
00022
...
00099
00101
00112
00123
...
00987
00998
01001
...
99974
99985
99996

These IDs have been set up so that no two different IDs can have their first four digits matching.
So to violate the condition, the first four digits would have to differ in one place and the last digits would have to match. But if the first four differ in one place then the last digits must also be different.

10,000 is also the maximum amount because if there were 10,001 IDs then there must be two of them whose first four digits match up (Pigeonhole Principle)

Therefore, if I've made no mistakes, 10000 is the correct answer.

---

Why did the vector cross the road?
It wanted to be normal.

Fruityloop

Member

Registered: 2009-05-18

Posts: 143

Re: confusable IDs

Mathyperson,
     That is brilliant!  I will study this and learn from it.