・要素の和 Dengan kesaktian Indukmu 氏
次の問題設定は、0 から 19 まではうまくいくのだが...。
(1) n を 0 から 19 までの整数とします。整数の集合 A={a,b,c,d,e,f} の部分集合のうち、要
素数が3の部分集合は20個あります。これらの部分集合を X_n とします。X_n の要素の
総和を S_n とします。S_n= n となるような A を求めてください。
(2) n を 1 から 20 までの整数とします。整数の集合 A={a,b,c,d,e,f} の部分集合のうち、要
素数が3の部分集合は20個あります。これらの部分集合を X_n とします。X_n の要素の
総和を S_n とします。S_n= n となるような A を求めてください。
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・< === チョッキン
皆様にご教示を頂戴いたしたく...、(2)に解がないことをスマートに証明できるものなの
でしょうか?
(コメント) 整数の集合 A={a,b,c,d,e,f} の部分集合のうち、要素数が3の部分集合は、20個
あって、すなわち、
No. |
a |
b |
c |
d |
e |
f |
1 |
○ |
○ |
○ |
|
|
|
2 |
○ |
○ |
|
○ |
|
|
3 |
○ |
○ |
|
|
○ |
|
4 |
○ |
○ |
|
|
|
○ |
5 |
○ |
|
○ |
○ |
|
|
6 |
○ |
|
○ |
|
○ |
|
7 |
○ |
|
○ |
|
|
○ |
|
|
No. |
a |
b |
c |
d |
e |
f |
8 |
○ |
|
|
○ |
○ |
|
9 |
○ |
|
|
○ |
|
○ |
10 |
○ |
|
|
|
○ |
○ |
11 |
|
○ |
○ |
○ |
|
|
12 |
|
○ |
○ |
|
○ |
|
13 |
|
○ |
○ |
|
|
○ |
14 |
|
○ |
|
○ |
○ |
|
|
|
No. |
a |
b |
c |
d |
e |
f |
15 |
|
○ |
|
○ |
|
○ |
16 |
|
○ |
|
|
○ |
○ |
17 |
|
|
○ |
○ |
○ |
|
18 |
|
|
○ |
○ |
|
○ |
19 |
|
|
○ |
|
○ |
○ |
20 |
|
|
|
○ |
○ |
○ |
|
具体的には、{a,b,c} 、{a,b,d} 、{a,b,e} 、{a,b,f} 、{a,c,d} 、・・・、{d,e,f} 達である。特徴としては、
X_n の要素の総和 S_n は、(a+b+c+d+e+f)*10 に等しいことである。
らすかるさんからのコメントです。(令和6年12月18日付け)
私の理解が正しければ、mod 3で証明できます。
nが 1~20 のとき、ΣS_n=Σn=210 から、a+b+c+d+e+f=21
(a,b,c,d,e,f がそれぞれ10回ずつ登場するので、210÷10=21)
以下、集合Aの要素と和は、mod 3で表します。
3つの和が0になるものが、n=3,6,9,12,15,18 の6通り
3つの和が1になるものが、n=1,4,7,10,13,16,19 の7通り
3つの和が2になるものが、n=2,5,8,11,14,17,20 の7通り
A={x,x,x,x,y,z} (x,y,zはそれぞれ0か1か2) の場合
2x+y が6通り、2x+z が6通り、3x が4通り、x+y+z が4通り
このとき、0、1、2 が偶数個ずつにしかならないので不適
よって、mod 3が一致するものは、3個以下
Aの要素で、0 が3個のとき、総和が 0 (21≡0) なので、(0,0,0,1,1,1)か(0,0,0,2,2,2)の何れか。
しかし、どちらの場合も 0 になるものが、2通り((0,0,0)と(1,1,1)または(2,2,2))しかなく不適。
#何れの場合も 1 になるものと 2 になるものがそれぞれ9通りずつです。
Aの要素で 0 が2個のとき、総和が 0 なので、(0,0,1,1,2,2)
このとき 0 になるものが(0,1,2)の組合せ 2×2×2=8通りとなり不適。
# 1になるものは、(0,0,1)が2通り、(0,2,2)が2通り、(1,1,2)が2通りの計6通り
# 2になるものは、(0,0,2)が2通り、(0,1,1)が2通り、(1,2,2)が2通りの計6通り
Aの要素で 0 が1個のとき、総和が 0 になるものは、(0,1,1,1,1,2)か(0,1,2,2,2,2)しかなく、
同じものが4個以上になるので不適。
Aの要素で 0 が0個のとき、総和が 0 で同じものが3個以下なので、(1,1,1,2,2,2)
このとき、0 になるものが、(1,1,1)と(2,2,2)の2通りとなり不適。
従って、解は存在しません。
ちなみに、n=0~19 の場合は、上記と全く同じ手順で考えると、
(0,0,0,1,1,2)、(0,0,1,2,2,2)、(0,1,1,1,2,2)
の3通りが条件を満たします。
# 条件は総和が190÷10=19≡1、3つの和が0,1,2になるものが順に7,7,6通り
# 解の存在証明ではありません。
Dengan kesaktian Indukmu さんからのコメントです。(令和6年12月18日付け)
らすかるさん、まことに有難うございます。なるほど mod 3 で!ウロコが目からボロボロと。
【付記1】 (1)の解として、a=−5, b=2, c=3, d=4, e=6, f=9 があります。
おそらくはこれひとつだけと存じます。
【付記2】 (2)をおいかけていて、下記までで挫折しました。お笑いください。
a+b+c = 1 、d+e+f = 20 、a ≤ b ≤ c ≤ d ≤ e ≤ f
実は、a < b < c < d < e < f である。なんとなれば、たとえば、題意から、a+b+c <
a+b+d
とならねばならず、他の組み合わせどうしでも同様だからである。
◆補題1 d ≤ 5
(証明) 6 ≤ d と仮定する。すると、d < e < f より、7 ≤ e、8 ≤ f さらに、21 ≤ d+e+f を得る。
これは、d+e+f = 20 と矛盾する。背理法により補題1「d ≤ 5」が証明された。
◆補題2 c ≤ 4 、b ≤ 3
(証明) b < c < d ≤ 5 より明らか
◆補題3 -6 ≤ a
(証明) c ≤ 4、b ≤ 3 より、b+c ≤ 7 で、a+b+c = 1 であるから、1 -a = b+c ≤ 7 より、-6 ≤ a
◆補題4 d = c +1
(証明) 3つの総和が最大のものは、d + e +f 、2番目に大きいものは、c +e +f
前者は 20 、後者は 19 ゆえに、d = c +1
ここから全数をあたるプログラムでも作ろうかと思っていたのです……とほほ
らすかるさんからのコメントです。(令和6年12月18日付け)
Dengan kesaktian Indukmu さんの続きを手作業で証明してみました。
a+b+c=1 から、c≧2 (∵ c≦1 ならば、a+b+c<1) よって、c=2、3、4
3番目に大きいものは、b+e+f または c+d+f
3番目に大きいものが b+e+f である場合
b+1=c、c+1=d、1-b-c=a なので、(a,b,c,d)=(-2,1,2,3),(-4,2,3,4),(-6,3,4,5)
(a,b,c,d)=(-2,1,2,3) の場合
1+2+3=6 なので、1~5 に -2 が使われる。
-2,1,2,3で 4 は作れないから、4-(-2)-2=4 または 4-(-2)-1=5 のいずれかが必要。
f≧8 なので、4 か 5 になるのは、e。
e=4 のとき、(-2)+1+4=(-2)+2+3=3 となり、不適。
e=5 のとき、(-2)+3+5=1+2+3=6 となり、不適。
よって、(a,b,c,d)=(-2,1,2,3) は、不適。
(a,b,c,d)=(-4,2,3,4) の場合
2+3+4=9 なので、1~8 に -4 が使われる。
-4,2,3,4で 4 は作れないから、4-(-4)-3=5 または 4-(-4)-2=6 のいずれかが必要。
f≧8 なので、5 か 6 になるのは、e。
e=5 のとき、(-4)+2+5=(-4)+3+4=3 となり、不適。
e=6 のとき、d+e+f=20 なので、f=10 となるが、(-4)+3+10=2+3+4=9 となり、不適。
よって、(a,b,c,d)=(-4,2,3,4) は、不適。
(a,b,c,d)=(-6,3,4,5) の場合
3+4+5=12 なので、1~11を作るのに -6 を使わなければならないが、-6 を使えるのはちょう
ど10回なので不適。
よって、(a,b,c,d)=(-6,3,4,5) も不適なので、「3番目に大きいものがb+e+f」は不適。
3番目に大きいものが c+d+f である場合
c+1=d、d+1=e、20-d-e=f なので、(c,d,e,f)=(2,3,4,13),(3,4,5,11),(4,5,6,9)
(c,d,e,f)=(2,3,4,13) の場合
2+3+4=9 なので、10~20を作るのに13を使わなければならないが、13を使えるのはちょうど
10回なので不適。
(c,d,e,f)=(3,4,5,11) の場合
3+4+5=12 なので、13~20に11が使われる。
3,4,5,11で17は作れないから、17-11-5=1 または 17-11-4=2 のいずれかが必要。
a<0 なので、1 か 2 になるのは、b (∵a≧0 のとき、a+b+c≧3)。
b=1 のとき、a+b+c=1 なので、a=-3 となるが、-3+4+11=3+4+5=12 となり、不適。
b=2 のとき、2+5+11=3+4+11=18 となり、不適。
よって、(c,d,e,f)=(3,4,5,11) は、不適。
(c,d,e,f)=(4,5,6,9) の場合
4+5+6=15 なので、16~20に 9 が使われる。
4,5,6,9で17は作れないから、17-9-6=2 または 17-9-5=3 のいずれかが必要。
上と同様に、2 か 3 になるのは、b。
b=2 のとき、2+4+9=4+5+6=15 となり、不適。
b=3 のとき、3+6+9=4+5+9=18 となり、不適。
よって、(c,d,e,f)=(4,5,6,9) も不適なので、「3番目に大きいものがc+d+f」は不適。
以上により、解なし。
(コメント) 「(1)の解として、a=−5, b=2, c=3, d=4, e=6, f=9 があります。」とのことなので、検証
してみた。
No. |
a |
b |
c |
d |
e |
f |
和 |
1 |
○ |
○ |
○ |
|
|
|
0 |
2 |
○ |
○ |
|
○ |
|
|
1 |
3 |
○ |
○ |
|
|
○ |
|
3 |
4 |
○ |
○ |
|
|
|
○ |
6 |
5 |
○ |
|
○ |
○ |
|
|
2 |
6 |
○ |
|
○ |
|
○ |
|
4 |
7 |
○ |
|
○ |
|
|
○ |
7 |
|
|
No. |
a |
b |
c |
d |
e |
f |
和 |
8 |
○ |
|
|
○ |
○ |
|
5 |
9 |
○ |
|
|
○ |
|
○ |
8 |
10 |
○ |
|
|
|
○ |
○ |
10 |
11 |
|
○ |
○ |
○ |
|
|
9 |
12 |
|
○ |
○ |
|
○ |
|
11 |
13 |
|
○ |
○ |
|
|
○ |
14 |
14 |
|
○ |
|
○ |
○ |
|
12 |
|
|
No. |
a |
b |
c |
d |
e |
f |
和 |
15 |
|
○ |
|
○ |
|
○ |
15 |
16 |
|
○ |
|
|
○ |
○ |
17 |
17 |
|
|
○ |
○ |
○ |
|
13 |
18 |
|
|
○ |
○ |
|
○ |
16 |
19 |
|
|
○ |
|
○ |
○ |
18 |
20 |
|
|
|
○ |
○ |
○ |
19 |
|
Dengan kesaktian Indukmu さんからのコメントです。(令和6年12月18日付け)
いやあ、素晴らしいです!
らすかるさんからのコメントです。(令和6年12月19日付け)
n=0~19 に、同じ証明方法を適用すれば全解が得られるはずなので、やってみたくなりま
した。
プログラムによる総当たりで、解は、(-5,2,3,4,6,9)の一つとわかっていますので、結果が合
えば内容を確認していただく必要はありません。ただの落書きとしてスルーして下さい。
n=0~19 のとき、a<b<c<d<e<f として、
a+b+c=0 、d+e+f=19 、d=c+1 、-7≦a≦-1 、-1≦b≦3 、1≦c≦4 、2≦d≦5 、3≦e≦8
8≦f≦14
(ここまで証明省略)
c=1 のとき、(a,b,c,d)=(-1,0,1,2) となるが、このとき、a+d+e=b+c+e となり、不適。
よって、2≦c≦4、3≦d≦5、4≦e≦8、8≦f≦12。
3番目に大きいものは、b+e+f または c+d+f
3番目に大きいものが b+e+f である場合
b+1=c、c+1=d、a+b+c=0 なので、(a,b,c,d)=(-3,1,2,3)、(-5,2,3,4)、(-7,3,4,5)
(a,b,c,d)=(-3,1,2,3)の場合
1+2+3=6 なので、0~5 に -3 が使われる。
-3,1,2,3 で 3 は作れないから、3-(-3)-2=4 または 3-(-3)-1=5 のいずれかが必要。
f≧8 なので、4 か 5 になるのは、e。
e=4 のとき、(-3)+1+4=(-3)+2+3=2 となり、不適。
e=5 のとき、f=19-5-3=11 となるが、(-3)+1+11=1+3+5=9 となり、不適。
よって、(a,b,c,d)=(-3,1,2,3) は不適。
(a,b,c,d)=(-5,2,3,4)の場合
2+3+4=9 なので、0~8 に -5 が使われる。
-5,2,3,4 で 3 は作れないから、3-(-5)-3=5 または 3-(-5)-2=6 が必要。
f≧8 なので、5 か 6 になるのは、e。
e=5 のとき、(-5)+2+5=(-5)+3+4=2 となり、不適。
e=6 のとき、f=19-6-4=9 となるが、(a,b,c,d,e,f)=(-5,2,3,4,6,9) は、
(-5)+2+3=0, (-5)+2+4=1, (-5)+3+4=2, (-5)+2+6=3, (-5)+3+6=4, (-5)+4+6=5,(-5)+2+9=6,
(-5)+3+9=7, (-5)+4+9=8, 2+3+4=9, (-5)+6+9=10, 2+3+6=11, 2+4+6=12,3+4+6=13,
2+3+9=14,
2+4+9=15, 3+4+9=16, 2+6+9=17, 3+6+9=18, 4+6+9=19 となり、適。
よって、(a,b,c,d)=(-5,2,3,4) のときの解は、(a,b,c,d,e,f)=(-5,2,3,4,6,9)
(a,b,c,d)=(-7,3,4,5)の場合
3+4+5=12 なので、0~11 に -7 が使われることになるが、-7 が使われるのは、10回なので
不適。
従って、「3番目に大きいものがb+e+f」のときに解が一つ得られた。
3番目に大きいものがc+d+fである場合
c+1=d, d+1=e, d+e+f=19 なので、(c,d,e,f)=(2,3,4,12),(3,4,5,10),(4,5,6,8)
(c,d,e,f)=(2,3,4,12)の場合
2+3+4=9 なので、10~19 に 12 が使われる。
2,3,4,12 で 16 は作れないから、16-12-4=0 または 16-12-3=1 のいずれかが必要。
a≦-1 なので、0 か 1になるのは、b。
b=0 のとき、a=0-0-2=-2 となるが (-2)+3+4=0+2+3=5 となり、不適。
b=1 のとき、1+4+12=2+3+12=17 となり、不適。
よって、(c,d,e,f)=(2,3,4,12) は不適。
(c,d,e,f)=(3,4,5,10)の場合
3+4+5=12 なので 13~19 に 10 が使われる。
3,4,5,10 で 16 は作れないから、16-10-5=1 または 16-10-4=2 のいずれかが必要。
a≦-1 なので、1 か 2 になるのは、b。
b=1 のとき、a=0-1-3=-4 となるが、(-4)+3+10=1+3+5=9 となり、不適。
b=2 のとき、2+5+10=3+4+10=17 となり、不適。
よって、(c,d,e,f)=(3,4,5,10) は不適。
(c,d,e,f)=(4,5,6,8)の場合
4+5+6=15 なので、16~19 に 8 が使われる。
4,5,6,8 で 16 は作れないから、16-8-6=2 または 16-8-5=3 のいずれかが必要。
a≦-1 なので、2 か 3 になるのは、b。
b=2 のとき、2+5+8=4+5+6=15 となり、不適。
b=3 のとき、3+6+8=4+5+8=17 となり、不適。
よって、(c,d,e,f)=(4,5,6,8) は、不適なので、「3番目に大きいものがc+d+f」は不適。
従って、条件を満たす解は、(a,b,c,d,e,f)=(-5,2,3,4,6,9) のみ。
らすかるさんからのコメントです。(令和6年12月19日付け)
さらに、n=2~21 や n=3~22 などのように範囲を変えるとどうなるかを考えたのですが、
0~19 と 1~20 の場合からすべて導けますね。
まず、a,b,c,d,e,f すべてに 1 を足せば、3つの和は3大きくなりますので、n=0~19 で解があ
ることから、n=3~22、6~25、9~28、… でも +1、+2、+3、… した唯一解が存在することが
わかります。
同様に、n=1~20 で解がないことから、n=4~23、7~26、10~29、… でも解がないことが
わかります。
そして、n=2~21 の場合は、n=0~19 のときの a,b,c,d,e,f を全部 7 から引いて、
7-f 、7-e 、7-d 、7-c 、7-b 、7-a
をあらためて a,b,c,d,e,f とすると、3数の和は 21 から引いたものになり、2~21 が作れます。
よって、n=2~21 のときの唯一解は、
(a,b,c,d,e,f)=(7-9,7-6,7-4,7-3,7-2,7-(-5))=(-2,1,3,4,5,12)
とわかり、上と同様に、n=5~24、8~27、11~30、… では、それぞれに +1、+2、+3、… した
解が存在します。
従って、n=t~t+19 のときの一般解は、
t=3k のとき、 (a,b,c,d,e,f)=(-5+k, 2+k, 3+k, 4+k, 6+k, 9+k)
t=3k+1 のとき、解なし
t=3k+2 のとき、 (a,b,c,d,e,f)=(-2+k, 1+k, 3+k, 4+k, 5+k, 12+k)
(kは負でもOK)
とわかりました。
Dengan kesaktian Indukmu さんからのコメントです。(令和6年12月19日付け)
らすかるさん、いろいろと勉強になります!
《n=0~19 のときの a,b,c,d,e,f を全部 7 から引いて》→口をあんぐりとあけました!!!
DD++ さんからのコメントです。(令和6年12月21日付け)
1〜20 で解がないことの超スッキリした証明、できました。
Σ (S_n)^2 = 10*(a^2+b^2+……f^2) + 8*(ab+ac+……+ef)
すなわち、 2870 = (a+b+c+d+e+f)^2 + 9*(a^2+b^2+……f^2) + 6*(ab+ac+……+ef)
左辺を 3 で割った余りは 2 、右辺を 3 で割った余りは 0 か 1 なので、条件を満たす数は
存在しない。
Dengan kesaktian Indukmu さんからのコメントです。(令和6年12月21日付け)
DD++ さんによる鮮やかな短証明を拝見して、感激しております。
2870 = (a+b+c+d+e+f)^2 + 9*(a^2+b^2+……f^2) + 6*(ab+ac+……+ef)
のところで、a+b+c+d+e+f = 21 を代入してもよいかもしれません。
DD++ さんからのコメントです。(令和6年12月21日付け)
それをするには a+b+c+d+e+f = 21 の証明を書き足さないといけないので……。
Dengan kesaktian Indukmu さんからのコメントです。(令和6年12月21日付け)
あっ、なるほど。これはウッカリしておりました。失礼いたしました。それにしても、平方で
評価するなんて驚きました。
以下、工事中!