回復 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 編輯 ]