Unique Licence Plates

Question

Note: This is a Mathematical puzzle, not a Mathematical problem. Although the answer could be solved with mathematics, lots of problems on Puzzling SE could be solved with mathematics, and the problem itself is not that mathematical. The math-puzzle tags are simply because, as I said, the puzzle could be solved mathematically.

Imagine you have 500 cars lined up in a parking lot that a buyer would like. You are the license plate creator who has to create custom plates for the buyer's 500 cars. The buyer makes a strange request. He wants you to create 4-digit numbers on each license plate in such a way that the first three digits and the last three digits cannot be used again for any other cars. (If somebody could improve that explanation, go for it.)

Here's an example: Say you make this license plate:

2465

The license plate's first three digits are 246 and the last three digits are 465. That means that when you are creating the other 499 license plates, these numbers, 246 and 465 cannot be used . Say you were making another license plate:

8246

The 824 wold be fine, but the buyer would not accept this license plate because the 246 was used previously in another car's license plate.

Info: There are 1,000 different three-digit numbers that could go in the first slot and the second slot of the license plate. This means that if each car needs two numbers, then there would need to be 500 cars, which is how many that is in this puzzle.

Diclaimer: I do not know the answer to this puzzle, but was curious what the answer is, and how you would explain it. I thought this up while calculating the odds that a certain three-digit number would appear in a four-digit number section on a license plate. I am asking for answer which explains why or why not meeting the buyer's needs are possible.

If you need any help understanding, ask in the comments.

Answer 1

Another answer: start the license plate making process by making all possible 500 three-digit plates, where the three digits have even sum. Now to each add a last digit as so: If the first digit on the plate is $n$, use $n+1$ as the last digit (and if the first digit is $9$, use a $0$ as the last digit).

The first three digits of any plate can't be the same as any other first three digits by design. The first three of any plate can't be the same as any last three, because the first three always has even sum and the last three always has odd sum. Finally, the last three of any plate can't overlap with any other plate, since that would imply the first three would be the same (i.e. if two plates end in $340$, both plates must be $9340$).

Answer 2

An answer does exist in terms of a De Bruijn sequence. An order-$n$ De Bruijn sequence $B(A,n)$ on an alphabet $A$ (of size $k$) contains all length-$n$ strings in $A$ exactly once. One example of $B(0\ldots9,3)$ looks like this:

$$ 9,7,9,8,7,8,7,7,7,0,7,6,0,7,5,0,7,4,0,7\ldots 7,8,8,7,9 $$

Each license plate will have length $n+1$ (in this case $4$). We can obtain a list of licence plates by taking every other length-$(n+1)$ substring of the sequence. That way, the last length-$n$ substring of each plate does not completely overlap the first substring of the next. Since each length-$n$ substring is guaranteed to be unique, this gives us a list of $500$ plates (the length of the sequence, $1000$, divided by 2) that satisfy the criteria. For example, the list of plates from the above sequence looks something like this:

$$ 9,7,9,8\\ 9,8,7,8\\ 7,8,7,7\\ 7,7,7,0\\ 7,0,7,6\\ \vdots\\ 9,7,8,8\\ 8,8,7,9\\ 7,9,9,7 $$

(Note that we take the plates from the sequence cyclically, such that the last plate consists of the last two elements, then the first two.)

I tested this using the following Mathematica code:

Needs["Combinatorica`"]
seq = DeBruijnSequence[Range[10] - 1, 3];
plates = Partition[seq, 4, 2, 1];
Length[plates] (* == 500 *)
DuplicateFreeQ[Join[Most /@ plates, Rest /@ plates]] (* == True *)

This shows that plates contains $500$ numbers (lists of digits) such that there are no duplicates among the first three and last three digits of each plate.