| ■50829 / 1階層) |
積と和が一致する自然数の組
|
□投稿者/ WIZ 一般人(4回)-(2021/06/09(Wed) 17:37:25)
 | 横から失礼します。
値をソートして 1 ≦ a[1] ≦ a[2] ≦ ・・・ ≦ a[n-1] ≦ a[n] とすると、
1 ≦ k ≦ n で a[k]/a[n] ≦ 1 です。
a[1]a[2]・・・a[n-1]a[n] = a[1]+a[2]+・・・+a[n-1]+a[n]
⇒ a[1]a[2]・・・a[n-1] = (a[1]/a[n])+(a[2]/a[n])+・・・+(a[n-1]/a[n])+(a[n]/a[n]) ≦n
つまり、a[1]a[2]・・・a[n-1] は n 以下の自然数を因数分解したものとなります。
n 以下の自然数は有限個です。
また、個々の自然数を n-1 の自然数の積で表す表現数は、
a[1]a[2]・・・a[n-1] = k ≦ n ならば、1 ≦ a[1] ≦ k, 1 ≦ a[2] ≦ k, ・・・, 1 ≦ a[n-1] ≦ k なので、
(a[1], a[2], ・・・, a[n-1]) の組の数は高々 k^(n-1) 個となり、表現数も有限通りといえます。
(a[1], a[2], ・・・, a[n-1]) の各組に対して、a[1]a[2]・・・a[n-1] = k, a[1]+a[2]+・・・+a[n-1] = m
とすると、k*a[n] = m+a[n] となり、この a[n] 対する1次方程式が解ける場合は、
自然数になるとは限らないが a[n] の値は一意に決まりますので、
題意の解の個数も有限個となります。
以下、蛇足。
a[1]a[2]・・・a[n-1] = 1 つまり a[1] = a[2] = ・・・ = a[n-1] = 1 とすると、
a[n] = (n-1)+a[n] ⇒ 0 = n-1 > 0 と矛盾。n ≧ 2 なので。
a[1]a[2]・・・a[n-1] = k ≧ 2 で a[1] = a[2] = ・・・ = a[n-2] = 1, a[n-1] = k とすると、
k*a[n] = (n-2)+k+a[n] ⇒ a[n] = (n-2+k)/(k-1) = 1+(n-1)/(k-1)
k = 2 なら a[n] = 1+(n-1)/(2-1) = n。これはらすかるさんの提示した解。
一般に n = m(k-1)+1 という形なら、a[n] = 1+m となる解があります。
5 = 1*(5-1)+1 ⇒ m = 1, k = 5 ⇒ (1, 1, 1, 5, 2) #大小関係が崩壊してますが!
5 = 2*(3-1)+1 ⇒ m = 2, k = 3 ⇒ (1, 1, 1, 3, 3)
5 = 4*(2-1)+1 ⇒ m = 4, k = 2 ⇒ (1, 1, 1, 2, 5)
# a[1] = a[2] = ・・・ = a[n-2] = 1 という場合のみの解ですので、
# a[n-2] 以前に 2 以上の値があるパターンは上記方法では網羅できません。
|
|
上記ツリーを一括表示 / 上記ツリーをトピック表示