能包含00~99的最短的長數字有多少個?例:1203包含12,20,03。

最短存在一個長度為10的數字里包含0~9(9876543210)。
這種數字有10!個,如果我們讓0可以在第一位。如果我們考慮0123等價於1230,或者說讓數列成環狀,不同的數字環有9!個。
---------------------------------------------------------------------------------------------------------------------
那能包含00~99的最短長度為多少?同理問000~999,0000~9999。
這個是我的原問題,不過後來00~99的被證明了,排出下列這個環
0919293949596979899
08182838485868788
071727374757677
0616263646566
05152535455
041424344
0313233
02122
011
0
隨便取個數字ab(37),找到a和b中間大的那一個,即7,那麼我們就可以在7最多的第三行看,因為第三行每格一個就有個7,就可以在273747中看到37。並且37隻出現了一次,並沒有重複。
同理00~99每個都只在這個數據環中出現了一次,(00出現在開頭和結尾連在一起)那麼這個數據環肯定是最短,即100位。

但是如果我們把這個數據環中的313233中的1和2互換,我們發現這個數據環還是滿足所有條件的,也就是說最短數據環其實還有很多條。

那麼我想問的就是一共有多少條最短數據環。
-------------------------------------------------------------------------------------------------
但是在000~999的時候我就不能找到一個有序的方法來創建一個最短數據環。
所以雖然我能猜到最短數據環的長度是1000,但是我不能證明它,更不要說找到有幾個數據環。
----------------------------------------------------------------------------------------------------
研究方向1:
通過讓0~9換成0~4(5進位)或者0~3(4進位)甚至abcd都行,來簡化問題,答案也是類似,比如包含00~44的最短數據環長度為5^2=25,包含00~22的最短數據環長度為3^2=9,共有24條不同最短數據環。

包含00到33的有2^{8} 3^{4} =20736條。
包含00到44的有2^{15} 3^{5}5^{3}=995328000條。
這些都是用電腦跑出來的,00到44的已經跑了2個多小時。00到55的估計要跑一年....

研究方向2:
建數據環時可以先畫一個矩陣
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33
然後固定00開始,然後把00從矩陣中劃掉,接著從01,02,03中選擇一個接著劃掉(比如01),然後寫下001,再接著劃掉10,11,12,13,要保證不要重複劃即可做到無重複,最後一定要以x0結尾,才能讓首尾相接,做到最大利用話,利用到開頭的0,才是最短數據環。
另外研究到000~333的時候是3維矩陣,所以弄不下去了。

進階,
通過推理髮現,如果要利用最大化,
比如0的次數,在00~33中出現8次,在數據環中每個0會被計算兩次,比如302相當於30,02。所以需要0在數據環中出現4次。其他每個數字都是類似的,所以每個數字都需要出現4次,和在一起就是4*4=16位。符合我們的結果。
並且這4個0一定要以00,0,0的形式隔開,因為00必須出現,而且其他的0不能挨在一起,不然就會重複出現00.
後來我發現,在數據環中,比如
0313233
02122
011
0
在313233的部分,4個3的位置,我們可以把那個雙三放在任何某個3都不影響大局,
比如
33,1 ,3 , 2,3
3,1 ,33, 2,3
3,1 ,3 , 2 ,33
全是ok的。
所以創建數據環時,可以先不放入雙數,如00,11,22,33.
等到創出一條原數據環,然後在三個0中選一個0放入雙0,三個1中選一個放入雙1,三個3中選一個放入雙3。根據不同的排列方法,會得到9個不同的最短數據環。
詳細創建原數據環的方法還是畫矩陣,但是要把矩陣的對角線提前劃掉,
01 02 03
10 12 13
20 21 23
30 31 32

如010203121323,
然後可以在任意一個0,1,2,3內各插入雙數,就行,得到
0011022033121323,這就是一個最短數據環。

-------------------------------------------------
本來不想寫我的自己的研究方向,因為怕限制了其他人的思考方向。但是並沒有人理我。
這個好像和組合數學有關,我有空會去自學相關知識,若有懂的朋友請指教。


我是題主,終於在同學的幫助下找到了相關信息,這是deBruijn序列_百度百科,De Bruijn sequence_wiki.

大家英語好的直接看wiki的,百度里的是撇腳地翻譯wiki里的一部分,看哭我了。

簡單的說,給定k個符號組成符號串,一個 成環形的(cyclic) 包含所有 長度為n的 這k個符號組成的 符號串 或者 序列, 就是De Bruijn序列,簡稱B(k,n).

每個B(k,n)的長度為k^{n}.

一共有frac{(k!)^{k^{n-1}}}{k^{n}} 條不同的B(k,n).

然而我並不知道最後這個式子怎麼來的,有人能解釋是最好的:)

最後裝下逼:

好憂傷啊,研究了這麼久原來已經被人研究過了,簡單有趣的數學問題越來越少了,以後只能去搞什麼抽象的代數,群,域了~

2015/12/25


2017/10/12更新

今天被 @王贇 Maigo 點贊了,於是了在兩年後又引來了一些關注。

這題的後續我在這個回答里詳細說了,論文鏈接也在最後發了,請移步

一道在夢中想到的數學題?Lancewu的回答-知乎

謝謝大家的關注。


推薦閱讀:

TAG:有趣 | 高等數學 | 數學難題 | 排列組合 |