最大公約数
"コレクション $\lbrace 8, 9, 12\rbrace$ は3つの正の整数のセットであり、これらの整数のいずれか2つが与えられると、それらの最大公約数（gcf）はそれらの差に等しくなります。
- $\text{gcd}(8,9)=1=9−8$;
- $\text{gcd}(8,12)=4=12−8$;
- $\text{gcd}(9,12)=3=12−9$。
同じプロパティを持つ4つの整数のセットを見つけることができますか？のセットはどうですか$n$ 整数？」
私は2つの整数ペアの例をもっと思いついた（例： $\lbrace 84,112 \rbrace$）しかし、「式」または一般的なケースを作成して、 $4$ 整数の場合、または $n$ 整数の場合。
回答
はい、必要なだけ大きなセットを作成できます。これは、誘導によって証明できます。
にとって $n=2$ セットを取ることができます $\{1,2\}$解決策として。今、帰納法のステップ：
ここで、そのようなセットが一部に存在するとします。 $n$ そしてそのセットを $S_n=\{a_i\mid i=1,2,...,n\}$。
すべての差異を計算する $d_{jk}$ 要素のすべてのペア間 $a_j<a_k$ セットから選んだ $S_n$。次のことに注意してください。
$$d_{jk}=a_k-a_j=\gcd(a_j,a_k)\tag{1}$$
すべての最小公倍数を見つける $d_{jk},a_i$：
$$L=LCM \left(\{d_{jk}=a_k-a_j\mid 1\le j <k\le n\}\cup \{a_i\mid i=1,2,...,n\}\right)\tag{2}$$
次のセットをチェックしてください $n+1$ 要素：
$$S_{n+1}=\{L\}\cup\{L+a_i\mid i=1,2,...,n\} $$
まず、拡張セットから任意の2つの要素を取得します。$L$：
$$\gcd(L+a_j, L+a_k)=\gcd(L+a_j, a_k-a_j)=\gcd(L+a_j, d_{jk})$$
（1）と（2）によると、 $d_{jk}\mid a_j$ そして $d_{jk}\mid L$。したがって：
$$\gcd(L+a_j, L+a_k)=d_{jk}=a_k-a_j=(L+a_k)-(L+a_j)$$
第二に、あなたが選ぶなら$L$ そして $L+a_j$：
$$\gcd(L, L+a_j)=\gcd(L, a_j)=a_j=(L+a_j)-L$$
最後は、の定義に従って明らかです $L$ （（$a_j\mid L$）。
さて、楽しい部分です。皮切りに：
$$S_2=\{1,2\}$$
上記のアルゴリズムを適用すると、次の一連のソリューションが急速に増加します。
$$S_3=\{2, 3, 4\}$$
$$S_4=\{12, 14, 15, 16\}$$
$$S_5=\{1680, 1692, 1694, 1695, 1696\}$$
$$S_6=\{343319185440, 343319187120, 343319187132, 343319187134, 343319187135, \ 343319187136\}$$
$$S_7=\{118295944058236539689200180716000759951728985298370880, \ 118295944058236539689200180716000759951729328617556320, \ 118295944058236539689200180716000759951729328617558000, \ 118295944058236539689200180716000759951729328617558012, \ 118295944058236539689200180716000759951729328617558014, \ 118295944058236539689200180716000759951729328617558015, \ 118295944058236539689200180716000759951729328617558016\}$$
したがって、この方法は最適とはほど遠いものであり、特定の「最小」セットを見つけることはできません。 $n$まだ挑戦です。ただし、必要なだけ長いシーケンスを作成できます。
（私はここで類似しているが完全に同一ではない問題を解決しましたが、同じロジックがここでも適用できます。）