wu :: forums - Print Page


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

        riddles >> hard >> Willywutang and the Number Stamp
        
(Message started by: william wu on Sep 8^th, 2003, 11:30pm)

Title: Willywutang and the Number Stamp
Post by william wu on Sep 8^th, 2003, 11:30pm

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): [hide]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![/hide]

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!

Title: Re: Willywutang and the Number Stamp
Post by towr on Sep 9^th, 2003, 12:36am

a is easy
::[hide]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[/hide]::

Title: Re: Willywutang and the Number Stamp
Post by william wu on Sep 9^th, 2003, 12:50am

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.

Title: Re: Willywutang and the Number Stamp
Post by towr on Sep 9^th, 2003, 2:03am

on 09/09/03 at 00:50:52, 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 :P
(getting something wrong is easier still)

Title: Re: Willywutang and the Number Stamp
Post by Sir Col on Sep 9^th, 2003, 9:48am

The shortest string that I can find consists of [hide]101[/hide] digits:
::[hide]
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
[/hide]::

Title: Re: Willywutang and the Number Stamp
Post by James Fingas on Sep 9^th, 2003, 10:40am

a) The length would be [hide]101 characters. Each character except for the last is the start of a two-digit number.[/hide]

b) [hide] 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).[/hide]

c) [hide]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 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 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 n^m+m-1 digits.[/hide]

d) [hide]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[/hide]

Title: Re: Willywutang and the Number Stamp
Post by Icarus on Sep 9^th, 2003, 3:39pm

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.

Title: Re: Willywutang and the Number Stamp
Post by william wu on Sep 9^th, 2003, 5:36pm

Reworded problem to replace instances of "minimal string" with "superstring."