Bradley 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?
The following explanation is courtesy of this week's winner. Let's call two numbers confusable if they differ in only one digit.
We first observe that there can be at most 10,000 possible IDs issued. From any block of ten consecutive numbers sharing the first four digits, for example, from the numbers 61610 to 61619, you can assign at most one number, since any two numbers from this block would differ in only the last digit, making them confusable. T here are 10,000 such blocks of ten numbers, which gives the upper bound of 10,000 IDs.
To finish the job we have to come up with a way of choosing the final digit from each of the 10,000 blocks of ten digits so as to avoid confusable numbers. The easiest way to do this is:
Make the last digit the ones-digit of the sum of the first four digits. For example, if the first digits are 1241, make the last digit 8 (1+2+4+1=8), giving the ID 12418; while if the first four digits are 1582, make the last digit 6 (1+5+8+2=16, whose ones-digit is 6), giving the ID 15826.
Now let's check that this scheme works. We need to see that any two IDs differ in at least two places. Think of two ID's. We consider three cases:
If the first four digits are the same, then the rule for making up the last one makes the two IDs equal.
If the first four digits differ in only one place, and they differ there by k units, then the last digits will also differ by either k units or 10 - k units; in particular, the last two digits will definitely differ, thereby making the IDs differ in two places.
If the first four digits differ in at least two places, then they are not confusable no matter what the last digits might be.
This checks all possible pairs of numbers. If you would like to see a (long!) list, courtesy of John Dahlstrom, of 10,000 possible IDs differing in at least 2 places, click here. The rule for creating these was similar to that given above, but in this case the last digit is the ones-digit of one more than the sum of the first four digits.Problem by Alberto L Delgado, from the now extinct Bradley Problem of the Week.