4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ So what's the question? Can we prove that it's possible? $\endgroup$ – Engineer Toast Jun 20 '15 at 0:51
  • $\begingroup$ You have to explain why it is or isn't possible $\endgroup$ – Xandawesome Jun 20 '15 at 1:02
  • 2
    $\begingroup$ Can one license plate have the same first three digits and last three digits, for example like 2222? $\endgroup$ – mmking Jun 20 '15 at 1:52
  • $\begingroup$ No because then both would be 222 and 222, which is unallowed. $\endgroup$ – Xandawesome Jun 20 '15 at 1:52
16
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ Wow, I like this way better than my solution. Not only is it easy to see why it works, it also allows you to 'mechanically' list all the plates, without hardly thinking. $\endgroup$ – 2012rcampion Jun 20 '15 at 4:10
  • $\begingroup$ @2012rcampion: Hey, anytime you can link something to De Brujin sequences (and educate more people about them in the process), that's a big win. I thought about De Brujin sequences at one point but didn't see the connection and went a different direction. $\endgroup$ – Tyler Seacrest Jun 20 '15 at 4:25
  • $\begingroup$ @TylerSeacrest wow, with this method, you show there are at least 5^500 different possible lists. I'm now thinking whether any brute forced list not following this pattern would work. $\endgroup$ – Quark Jun 20 '15 at 15:31
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.