發新話題
打印

106師大附中

回復 7# g112 的帖子

填充 2. 寫得有得長,前面是合理推測答案,後面是證明,順序有得亂,請見諒

\( 106^{106} = 53^{106} \times 2^{106} \)

重點在 53 這個質因數,當兩數模 53 同餘時,兩數相減會有53 這個因數。

因此我們將\( S_n \) 中的元素以模 53 來分類,各分類的元素個數記作 \( x_i \),滿足 \( \sum x_i =n \)。

令 \( p = \sum \frac{x_i(x_i-1)}{2} \),則 \( 53^p \) 整除 \( \prod\limits_{i\neq j} (a_i-a_j) \)

而函數 \( f(x) = \frac12 x(x-1) \) 是凸函數,因此 \( p \) "應"在 \( x_i \) 盡量接近時有最小值。

當 \( x_i =3 \), \( i=1,2,3,\ldots, 26 \), \( x_i =2 \), \( i =27,28,\dots 53 \) 時,\( p = 26\times 2 + 27 = 105 \)

取 \( S_n = \{1,2,3 \ldots 132 \} \),此 \( S_n \) 滿足上行 \( x_i \),且無 \( 53^2 \mid a_i - a_j \) 之情況,故 \( 53^{105} \) 整除 \( \prod\limits_{i \neq j} (a_i-a_j) \),但 \( 53^{106} \) 不整除 \( \prod\limits_{i\neq j} (a_i-a_j) \)。

因此 \( n > 132 \)。

當 \( x_i =3 \), \( i=1,2,3,\ldots, 27 \), \( x_i =2 \), \( i =28,29,\dots 53 \) 時,\( p = 27\times 2 + 26 = 107 \)

至此,可相信 \( n \) 之最小值為 \( 3\times 27 + 2\times 26 =133 \)

但證明部分尚缺「而函數 \( f(x) = \frac12 x(x-1) \) 是凸函數,因此 \( p \) "應"在 \( x_i \) 盡量接近時有最小值。」即最小值發生的情況正好是上上行,因為其餘情況,\( 53^{106} \) 必整除 \( \prod\limits_{i \neq j} (a_i-a_j) \)。

而最小值的證明,本等上與凸函數不等式相同,但在這裡 \( x_i \) 是非負整數,也就是離散版的。

運用反證法,假設有 \( x_i,  x_j \) 滿足 \( x_i \geq x_j +2 \)

易驗 \( \frac12 x_i(x_i-1) + \frac12 x_j(x_j-1) > \frac12 (x_i-1)(x_i-2) +\frac12 (x_j+1)x_j \)

因此我們將 \( x_i,  x_j \) 換成 \( x_i-1,  x_j+1 \),可保持 \( n = \sum x_k \) 不變,但 \( p \) 的值更小。

因此當 \( p \) 達最小值時,任兩個 \( x_i,  x_j \) 必須滿足 \( |x_i -  x_j| \leq 1 \)。

[ 本帖最後由 tsusy 於 2017-8-6 14:20 編輯 ]
網頁方程式編輯 imatheq

TOP

回復 35# jackyxul4 的帖子

填充2.
沒有連續整數的條件,記得前面我寫過,也沒有當連續整數,而是題意中

欲使 \( 106^{106} \) "恆" 可整除,意思是不管哪個 S,只要元素 n 個,就整除,所以不能指定 S

[ 本帖最後由 tsusy 於 2018-2-16 00:06 編輯 ]
網頁方程式編輯 imatheq

TOP

發新話題