wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Number of possible Licence Numbers
        
(Message started by: inexorable on May 20^th, 2008, 10:52pm)

Title: Number of possible Licence Numbers
Post by inexorable on May 20^th, 2008, 10:52pm

A state wants to issue 6-digit license numbers, with the digits from 0 to 9. If every number has to differ from every other number in at least 2 places, what is the maximum number of licenses that it can issue?

Title: Re: Number of possible Licence Numbers
Post by Wardub on May 21^st, 2008, 3:35am

I probably didn't interpret this correctly. This is just asking for every combination that doesn't have the same number at least 5 times, correct?

For example the number 1 1 1 1 2 2 is ok because each 1 differs in the 2's places. And 111115 would fail because they only differ in the one 5's place.

Anyway I get [hide]999450[/hide]

Title: Re: Number of possible Licence Numbers
Post by william wu on May 21^st, 2008, 3:47am

Hi Wardub,
I think the constraint has to do with comparing pairs of license numbers. For instance:

111111
and
111112

are license numbers that cannot both be produced because they only differ in one slot -- namely, the last slot. However,

111111
and
111122

are license numbers that differ in at least two slots, and so they can both be issued by the state.

So basically, any two license numbers must be different in at least two slots.

Title: Re: Number of possible Licence Numbers
Post by Grimbal on May 21^st, 2008, 9:49am

[hide]For instance, if you take only license numbers where the digits sum to a multiple of 10, two valid numbers can not differ in only one position.
[/hide]

Title: Re: Number of possible Licence Numbers
Post by Wardub on May 21^st, 2008, 4:42pm

OK that makes more sense, I was just comparing individual digits not the number as a whole.

I'll give it a little bit more thought.

EDIT: Alright I probably don't have it right but I get [hide]65440[/hide]
It probably isn't right. I just wrote a program that started at 000000, then found the next lowest number that would fit, which would be 000011, the next lowest would be 000022 and kept finding the next lowest. And I believe that is what I got, my program probably doesn't work right, it ran for an extremely long time so I don't feel like checking/running it again.

Also I am not sure finding the lowest number is most efficient, for example instead of making the second license plate 000011, why not 000012? I don't know how that would change things. I also have no idea how to prove it but that is what I got.

Title: Re: Number of possible Licence Numbers
Post by william wu on May 21^st, 2008, 10:13pm

The pigeonhole principle can give us a simple upper bound of 10^5, although I don't know how much this helps (e.g., particularly if we cannot achieve the bound). This doesn't contradict your program.

- Notice that there are 10^5 ways to fill up digits in the first five out of six slots.

- So, if we produced more than 10^5 license plates, then by the pigeonhole principle, there must exist at least two plates which are identical in their first five digits. So these two plates would only be able to differ in the sixth slot. But our constraint is that plates should differ in at least two slots, so such a collection of plates would be invalid.

- Hence, the number of plates must be no more than 10^5.

Title: Re: Number of possible Licence Numbers
Post by william wu on May 21^st, 2008, 10:53pm

I was thinking that maybe a recursive approach might work. Some initial thoughts here; maybe someone can work with this.

Define F(n,k) := # of license plates that can be produced with an alphabet of size n, and the number of digits on a plate is k

Then we have some simple base cases:

F(1,k) = 1, for all positive integers k.
(if i only have one symbol, i can only make one type of license plate.)

F(n,1) = 1, for all positive integers n.
(my license plates all have only one digit. but any two plates are supposed to differ in two places. so i can only make one plate.)

Now we'd like some kind of recurrence, expressing F(n+1,k+1) in terms of previously known entries in our 2D array.

Once you have the recurrence, fill up the array until you get F(10,6).

Title: Re: Number of possible Licence Numbers
Post by Wardub on May 21^st, 2008, 11:38pm

Using my program the first 25 license plates would be these:
0
11
22
33
44
55
66
77
88
99
101
110
123
132
145
154
167
176
189
198
202
213
220
231
246

You'll have to add the extra 0's to the beginning to get 6 digits, but you get the point.

It looks to me like it is working properly, heres hoping I got the right answer ;D.

The thing I was worrying about, ie 000012 instead of 000011, shouldn't matter because after the most amount of numbers starting with some XXXX, will be 10. What I mean the number of license plates starting with 0000-XY can only have 10 combinations at most.

I'll attach the program I wrote.

Title: Re: Number of possible Licence Numbers
Post by Eigenray on May 21^st, 2008, 11:49pm

on 05/21/08 at 22:13:04, william wu wrote:

The pigeonhole principle can give us a simple upper bound of 10^5, although I don't know how much this helps (e.g., particularly if we cannot achieve the bound).

on 05/21/08 at 09:49:39, Grimbal wrote:

[hide]
For instance, if you take only license number where the digits sum to a multiple of 10, two valid numbers can not differ in only one position.
[/hide]

Title: Re: Number of possible Licence Numbers
Post by Grimbal on May 22^nd, 2008, 12:47am

Thanks, Eigenray, I thought nobody did notice.

Title: Re: Number of possible Licence Numbers
Post by Barukh on May 22^nd, 2008, 4:35am

on 05/21/08 at 09:49:39, Grimbal wrote:

[hide]
For instance, if you take only license number where the digits sum to a multiple of 10, two valid numbers can not differ in only one position.
[/hide]

Very clever observation!

But can you easily count these?

Title: Re: Number of possible Licence Numbers
Post by Grimbal on May 22^nd, 2008, 5:12am

Of course I can.
[hide]The 5 first digits are free, the last digit is forced. Like a checksum.[/hide]

Title: Re: Number of possible Licence Numbers
Post by cool_joh on May 22^nd, 2008, 5:52am

on 05/22/08 at 05:12:09, Grimbal wrote:

Of course I can.
[hide]The 5 first digits are free, the last digit is forced. Like a checksum.[/hide]

What is checksum?
I have an idea about the forced digit: [hide]the last digit of the sum of the first 5 digits (e.g. 123455, 234526)[/hide].

Title: Re: Number of possible Licence Numbers
Post by Grimbal on May 22^nd, 2008, 7:37am

A checksum is a way to check the integrity of data. You compute some value from the data giving the "checksum" and append it to the end of the data. Upon reception of the data, the same computation is done and the result compared with the transmitted checksum. If they don't match you know an error occurred. If they match, it is likely the data was not corrupted.
One clever way to compute a checksum is to do checksum = -(sum of digits) mod 10*. That results in a number (concatenated data and checksum) such that the sum of digits is a multiple of 10. That makes the validation formula simpler to describe.

[hide]12345 would give 5 as last digit, 1+2+3+4+5+5 = 20,
but 23452 would give 4 as additional digit because 2+3+4+5+2+4 = 20[/hide]

*assuming a result in 0..9 even for negative numbers.

Title: Re: Number of possible Licence Numbers
Post by Sir Col on May 27^th, 2008, 5:59am

This is a very interesting problem.

However, there seems to be two separate discussions going on here with neither thread of conversation responding to what the other has said. Grimbal has described a valid solution that works for n-digits, albeit slightly cryptically, and Wardub has outlined an algorithm that, unfortunately, fails.

To bring things together...

Grimbal has explained how allowing the first five digits to remain free, the final digit can be chosen in such a way so as to ensure that at least two of the six digits differ.

Here is one possible explanation of how this can be achieved...

Consider counting through 00000 to 99999.
The final digit is determined by adding the digits and writing this modulo 10. Grimbal called this his checksum; although in his example he took his checksum from ten to ensure that the sum of all six digits is a multiple of ten.

Using this rule it is clear that all the digits cannot be equal, so there are two possibilities when comparing any two numbers:
(i) If at least two of the first five digits differ then the number is valid.

(ii) If only one of the first five digits differs then it is necessary for the final digits to differ.
Suppose that only the kth digit (from the first five) is different.
Clearly the difference between the final digits (checksum) will be equal to the difference between the sum of the digits (modulo 10). However, as all the digits are equal except for the kth then the difference between the final digits will be equal to the difference between the kth digits (modulo 10). And because this difference is not zero, we deduce that the final digits must differ. Hence at least two digits from the six will differ.

Thus for a 6-digit number there are 10⁵ valid licence plates.

Now the question is why doesn't Wardub's method work? It seems that counting through the integers and picking the next valid number is inefficient and precludes the possibility of optimising the total. For example, using this algorithm will only allow eight numbers from 200 to 299: 202, 213, 220, 231, 246, 257, 264, and 275, whereas it should be possible to pick ten in each century.

What if at least three digits must differ?

What if the licence plate is made up of two letters and four decimal digits in the form: [A-Z][A-Z][0-9][0-9][0-9][0-9], and at least two characters must differ?
What if the two letters and digits can be intermingled?

Title: Re: Number of possible Licence Numbers
Post by towr on May 27^th, 2008, 6:08am

on 05/27/08 at 05:59:13, Sir Col wrote:

Thus for a 6-digit number there are 10⁵ valid licence plates.

It is the least you can do, but I'm not convinced it's the best.

Title: Re: Number of possible Licence Numbers
Post by Sir Col on May 27^th, 2008, 6:16am

on 05/27/08 at 06:08:51, towr wrote:

It is the least you can do, but I'm not convinced it's the best.

Using this system there are 10⁵ valid plates and for each of these the first five digits are different 5-digit numbers: 00000 to 99999. If you create one more plate then it must be identical to the first five digits of another plate. As only the last digit can differ, it will not be valid. Hence there can be no more than 10⁵ valid plates.

Title: Re: Number of possible Licence Numbers
Post by rmsgrey on May 28^th, 2008, 6:50am

Under any plate numbering scheme, a given 6 digit number is either valid or invalid.

If it's valid, then the 54 numbers that differ from it in exactly one place are all invalid.

If it's invalid, then there are at most 6 valid numbers that differ from it in precisely one place - no two of them can differ from the original number in the same place as then they'd differ from each other in exactly one place.

So, if a given valid number renders 54 numbers invalid, and a given invalid number is rendered invalid by at most 6 valid numbers, then there must be at least 9 invalid numbers for each valid number, so no scheme can have more than 10⁵ valid plates.

[e]Or refer back to W.Wu's post using the pigeonhole principle to prove the same bound[/e]

Title: Re: Number of possible Licence Numbers
Post by Hippo on May 29^th, 2008, 3:26am

on 05/27/08 at 05:59:13, Sir Col wrote:

What if the licence plate is made up of two letters and four decimal digits in the form: [A-Z][A-Z][0-9][0-9][0-9][0-9], and at least two characters must differ?
What if the two letters and digits can be intermingled?

If on i-th position an arbitrary letter from alphabet of size s_i can be used, generate all possibilities on all except a position x of maximal s_i. On position x use the checksum mod s_x-th letter. ... So the same solution.

on 05/27/08 at 05:59:13, Sir Col wrote:

What if at least three digits must differ?

This is more complicated ... Let alphabet sizes are ordred s₁>=s₂>=...
an easy case is when there are primes p,q s₁>=p>=s₃. In that case use the checksum of l_i mod s₂ on position 2 and the checksum of l_i*qⁱ mod p on position 1. This construction requires qⁱ mod p be all different.

Now if only i-th digit differs on positions 3,..., the checksum diferences \delta_i, \delta_i*qⁱ respectively are nonzero.

If exactly i-th and j-th digits differ on positions 3,..., we must prove one of the checksum differences is nonzero. Suppose \delta_i+\delta_j=0 and qⁱ*(\delta_i+\delta_j*q^j-i)=0 ... it leads to (q^j-i-1)*qⁱ*\delta_i=0. As we are working mod prime p, this means (q^j-i-1)=0 ...

Title: Re: Number of possible Licence Numbers
Post by Altamira_64 on Jan 20^th, 2016, 9:13am

So, does this mean that for 8-digit plates (with the same restriction, minimum 2 different digits), the maximum number is 10^7?

on 05/28/08 at 06:50:17, rmsgrey wrote:

Title: Re: Number of possible Licence Numbers
Post by rmsgrey on Jan 21^st, 2016, 9:04am

on 01/20/16 at 09:13:31, Altamira_64 wrote:

So, does this mean that for 8-digit plates (with the same restriction, minimum 2 different digits), the maximum number is 10^7?

Yes.

You could repeat my reasoning - for an n-digit number, each valid number invalidates 9n other numbers, while each invalid number differs in only one place from at most n valid numbers, so there are at least 9n/n = 9 invalid numbers per valid number, so at most 10^n-1 valid numbers.

Or you could repeat W.Wu's reasoning:

There are only 10^n-1 possible combinations of the first n-1 digits, so, since any two numbers that differ in at least 2 places must differ somewhere in the first n-1 places, you can't have more than 10^n-2 valid numbers.

Either way, this only provides an upper bound. To prove it's achievable, you need to offer a scheme that satisfies it. A simple check-digit scheme will do it.