Author 
Topic: Willywutang and the Number Stamp (Read 14701 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Willywutang and the Number Stamp
« on: Sep 8^{th}, 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 2digit 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 2digit 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 2digit 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 2digit 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 2digit numbers composed from the numbers 0 through 9, what if Willy must make a stamp which contains exactly once every mdigit 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 mdigit 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) (mediumlevel, occupationspecific): 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 9^{th}, 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 9^{th}, 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 9^{th}, 2003, 12:50am » 
Quote Modify

eh no ... note that when you say 100 numbers, i assume you mean the number of 2digit numbers you must hit; note that each of these numbers is 2digits 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 9^{th}, 2003, 2:03am » 
Quote Modify

on Sep 9^{th}, 2003, 12:50am, william wu wrote:eh no ... note that when you say 100 numbers, i assume you mean the number of 2digit numbers you must hit; note that each of these numbers is 2digits 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 9^{th}, 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 9^{th}, 2003, 10:40am » 
Quote Modify

a) The length would be 101 characters. Each character except for the last is the start of a twodigit 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 twodigit number. The question is then equivalent to finding a traversal of the graph so that every edge is traversed exactly once. This is trivially easytraverse 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^{(m1)} 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 n^{th} 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 oneway 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 n^{m}+m1 digits. d) Yes, when m=2, removing one digit works. For other m, you remove m1 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 9^{th}, 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



