wu :: forums - Print Page


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

        riddles >> medium >> number strings and sub-strings
        
(Message started by: Brian on Aug 26^th, 2004, 1:38pm)

Title: number strings and sub-strings
Post by Brian on Aug 26^th, 2004, 1:38pm

consider all m-digit strings made of n different numbers. for example, with (m,n)=(2,3), they are:

11 21 31
12 22 32
13 23 33

note that there are always n^m different strings. now consider a longer string containing these m digits. the minimum size it has to be to be able to contain all the m-digit substrings would be n^m + n - 1. for example, with (m,n)=(2,3) again, one possible string would be 1121322331. is it always possible to construct such a string with this minimum length?

Title: Re: number strings and sub-strings
Post by william wu on Aug 26^th, 2004, 4:18pm

Hi Brian. Thanks for the puzzle, but this is already on the site under a unnecessarily complicated problem description written by yours truly. See

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1063089039

Title: Re: number strings and sub-strings
Post by brian on Aug 27^th, 2004, 9:34am

o sorry. but i didnt see a clear proof of the general case over there, so do you or anyone else have that?