Author |
Topic: Willywutang and the Number Stamp (Read 14670 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Willywutang and the Number Stamp
« on: Sep 8th, 2003, 11:30pm » |
 Quote  Modify
|
Willywutang and the Number Stamp
After years of erratic employment as a blasé Burning Island tour guide, Willywutang finally lands a stable job as an engineer who designs assembly lines. His latest assignment involves the following scenario: Boxes are coming down an assembly line, and each one needs to be stamped with a 2-digit number ranging from 00 to 99. To place these numbers, Willy's boss wants to use a long rectangular strip of metal, onto which a long unbroken string of digits will be engraved to make a giant stamp. Then products will be stamped with the appropriate 2-digit number by simply shifting the stamp plate left or right, and then depressing the stamp onto the box. (The box's top face is exactly wide enough to be stamped with a 2-digit number, no more and no less.)
Willywutang now has the task of deciding the unbroken string of digits to be placed on this stamp. To minimize costs of purchasing and engraving metal, he wants the string to be as short as possible. In a perfect world, he would like a string that contains every possible 2-digit number exactly once, because it can't get any shorter than that. We will call such strings "superstrings."
a) Assume it is possible to find a superstring. Calculate what the length of such a string would have to be.
b) Prove that it is possible in this case to find a superstring! (Note that this doesn't necessarily mean you have to actually determine the string -- you just need to prove that the string exists.)
c) Now generalize your results. Instead of just considering 2-digit numbers composed from the numbers 0 through 9, what if Willy must make a stamp which contains exactly once every m-digit number composable from a set of n symbols? What conditions must the positive integers m and n satisfy for a superstring to exist?
d) Suppose Willy's boss changes the design specification at the last minute, and now wants to wrap the metal strip around a wheel, such that desired m-digit numbers are selected by rotating the wheel, and then the bottom part of the wheel is depressed onto the boxes. Can Willy always still use the superstrings he constructed for the original design specification, by simply removing a digit?
Hint for part (b) (medium-level, occupation-specific): For all you computer programmers/scientists out there, you can use a few concepts you better have studied to produce an extremely slick proof, which, if explained very thoroughly, any layperson should be able to appreciate!
Note 1: Author: William Wu, 11:29 PM 9/8/2003. But he's quick to note that the actual puzzle meat has been studied for at least a millenium.
Note 2: Willy thinks is a really neat and beautiful problem. Try it!
|
| « Last Edit: Sep 9th, 2003, 5:35pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Willywutang and the Number Stamp
« Reply #1 on: Sep 9th, 2003, 12:36am » |
Quote Modify
|
a is easy
::100 numbers, each of which shares one digit with it's neighbour except the ends, so 98/2+2 = 51
Or you start with one number, two digits, and every following number introduces one more digit, 2+49 = 51::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Willywutang and the Number Stamp
« Reply #2 on: Sep 9th, 2003, 12:50am » |
Quote Modify
|
eh no ... note that when you say 100 numbers, i assume you mean the number of 2-digit numbers you must hit; note that each of these numbers is 2-digits long.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Willywutang and the Number Stamp
« Reply #3 on: Sep 9th, 2003, 2:03am » |
Quote Modify
|
on Sep 9th, 2003, 12:50am, william wu wrote:| eh no ... note that when you say 100 numbers, i assume you mean the number of 2-digit numbers you must hit; note that each of these numbers is 2-digits long. |
|
euhm.. yes..
I mustn't have been fully awake yet.. Just add 50 and let's call it quits 
It's still easy, even though I got it wrong 
(getting something wrong is easier still)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Willywutang and the Number Stamp
« Reply #4 on: Sep 9th, 2003, 9:48am » |
Quote Modify
|
The shortest string that I can find consists of 101 digits:
::
I've broken the continuous string on to separate lines so you can view its construction.
002030405060708090
1131415161718191
22425262728292
335363738393
4464748494
55758595
668696
7797
88
99
876543210
::
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Willywutang and the Number Stamp
« Reply #5 on: Sep 9th, 2003, 10:40am » |
Quote Modify
|
a) The length would be 101 characters. Each character except for the last is the start of a two-digit number.
b) Consider the graph made with ten nodes, labelled 0 to 9. Draw two directed edges from each node to each other node (one in each direction). Each edge corresponds to one two-digit number.
The question is then equivalent to finding a traversal of the graph so that every edge is traversed exactly once. This is trivially easy--traverse the graph randomly, making sure you do not traverse the same edge twice, and that you do not visit your starting node n times before the sequence is complete. If you do this, you cannot help but traverse each edge exactly once.
The sequence is the list of nodes you visit (including the starting and ending nodes, which must be the same).
c) Considering our graph, we will construct n(m-1) nodes, and connect them with directed, labelled edges to n other nodes. Label these edges with the n symbols. The destination nodes of the n edges have the labels you get by appending the edge label to the starting node label, then deleting the first symbol of the result.
Since these nodes have exactly as many exit nodes as entrance nodes, the traversal can be done exactly the same way as in the n=10, m=2 case. You can never get stuck until you revisit the starting node for the nth time. Just make sure you don't do this before your sequence is complete.
Hmm... this is not as easy as I make it out to be. If you don't do things correctly, you might be forced to return to the starting node before the sequence is complete. More thought is required. There might be conditions where this is not possible.
No, I think it's possible for any m,n. But you have to be careful to guard your exit. After every symbol choice, you have to make sure that you don't end up going down a one-way path to the starting node. The way to do this is to simultaneously generate the trailing end of the sequence, whenever the choice of the last few digits is forced.
The string would require nm+m-1 digits.
d) Yes, when m=2, removing one digit works. For other m, you remove m-1 digits. Here is a sequence for m=3, n=3 (I was checking to see if there was a problem with m*n odd).
11121131221231321332223233311
Here is another string for m=2, n=10, based on a greedy algorithm and the above logic.
0010203040506070809
11213141516171819
223242526272829
3343536373839
44546474849
556575859
6676869
77879
889
9
0
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Willywutang and the Number Stamp
« Reply #6 on: Sep 9th, 2003, 3:39pm » |
Quote Modify
|
Actually, the way (c) is stated, I would say it's proof is trivial. Since you are only asked to prove that a "minimal string" exists, note that there is an obvious string of length mn that works. Examine all strings of length <= mn (there are only a finite number). Of those that work, at least one must have a smallest length. It is by definition "minimal".
Of course, what Willy really wants is one in which no sequence is ever repeated, but the way (c) is phrased does not require that.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print