1樓：Snakes
若存在長度不小於 的單增子序列則得證；
若不存在長度不小於 的單增子序列，則排列中任意單增子序列長度子串行不大於 ，單增子序列個數至少為 。根據 Dilworth 定理可知最長單減子串行長度不小於 。
對於任意 下界似乎都可以通過構造取得。
2樓：曉生
反過來說，總有長為n+1的單調子列的1～g（n）的任意排列，g（n）=n^2+1。
證明方法如下：在排列的每個數字上方標有乙個長度，等於從該數字開始的最大單增子列長度。注意到，這個長度只可以為1～n，而我們可以證明，標有長度相同的數字必然是遞減的（不然，可以把後面的單增子列接在前面那個數字的後面變得更長），而一共n^2+1個數字，易知必然有長為n+1的單調子列。
n^2的構造:321654987
3樓：法國球
我不會，但是至少可以發現如下的比較簡單的估計：
存在某種1到n的排列，使得其中沒有長度為f(n)+1的單調子例，這個排列記作An。而對任何1到n的排列，都存在長度為f(n)的單調子列。
1.把1到mn的數按照An×Am的方式排列(分塊矩陣)，容易證明這個排列裡任何單調子列的長度不超過f(m)*f(n)，因此f(mn)≤f(m)f(n)。
2.把1到m+n的數按照Am+An的方式排列(分塊矩陣)，容易證明f(m+n)≤f(m)+f(n)。
就這麼多了……
4樓：
下證:先證明如下引理:
Erds-Szekeres定理:設 是正整數,在任意長度為 的實數序列中,一定存在長為 的不增子序列或長為 的不減子串行.
引理的證明:設該序列為 ,若結論不成立.則任意不增子序列長度 ,任意不減子串行長度 .
記 是以 為首項的最長不減子串行長度,記 是以 為首項的最長不增子序列長度.將數對 對應成平面上的點,一共有 個這樣的點.
然而 , ,所以只有 個不同的.由抽屜原理,必存在 .使得 ,由於 和 有確定的大小關係,矛盾!
需要注意到,長度 是最佳的,因為對於 有反例:
每組n個,一共m組
在這裡我們只用定理的一種特殊情況:當且僅當長度不小於 的互不相等實數序列中,一定存在長為 的單調子串行.
回到原題,具體數對問題不會造成影響不妨它們是 個不同實數
顯然 不減.
由Erds-Szekeres定理,對於 , ,若取反例前 項知矛盾.故 .綜上,
找到一切正整數n,使得不存在n個連續的比n 小的合數？
Zephyr 第一想法就是當n足夠大的時候n 大於等於n 兀 n n，然後直接用抽屜原理就能證明存在連續n個比n 小的合數。然後就要算按這種方法，n得多大才能足夠大。因為我水平過於低下，所以在放縮的時候非常浪費，結果就估計到了這個亞子.這樣的n一定有上限，然後把這個範圍內的n編個程式跑一遍就能算了 ...
如何證明存在 n 個連續的整數，使得其中恰好有 m 個素數 m n ？
昴星團 引理1 存在 k 個連續的整數，使得其中全部是合數 k N 證明 若 a k 1 1 2k 1 則根據乘法分配率，易得 a 2 a 3 a k 1 這 k 個連續的整數均為合數，即引理1得證。下面我們來說明原命題的正確性 對於正整數數列 定義陣列 arr 其左端點為2，右端點為n，其中素數的...
有沒有自然數 n，使得 n 的前四個數字是 2020？
mathe 2021年了，該換2021開頭的了，第乙個以2021開頭的n 為16979！由於Sterling公式的存在，尋找某個特點模式開頭的階乘還是比較容易的，比如以圓周率的前若干位開始的最小階乘數n 有 d 3,n 9 d 31,n 62 d 314,n 62 d 3141,n 10044 d ...