MENU
273,351

スレッドNo.2398

0 から 19 まではうまくいく

① n を 0 から 19 までの整数とします。整数の集合 A ={a,b,c,d,e,f} の部分集合のうち、要素数が 3 の部分集合は 20 個あります。これらの部分集合を X_n とします。X_n の要素の総和を S_n とします。S_n = n となるような A を求めてください。

② n を 1 から 20 までの整数とします。整数の集合 A ={a,b,c,d,e,f} の部分集合のうち、要素数が 3 の部分集合は 20 個あります。これらの部分集合を X_n とします。X_n の要素の総和を S_n とします。S_n = n となるような A を求めてください。

=== 8< === 8< === 8< === チョッキン

皆様にご教示を頂戴いたしたく。
②に解がないことをスマートに証明できるものなのでしょうか?

引用して返信編集・削除(未編集)

私の理解が正しければ、mod3で証明できます。
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の要素と和はmod3で表します。
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が偶数個ずつにしかならないので不適
よってmod3が一致するものは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通り
# 解の存在証明ではありません

引用して返信編集・削除(未編集)

らすかるさん、まことに有難うございます。
なるほど mod 3 で!! ウロコが目からボロボロと。

【付記1】
①の解として
a=−5, b=2, c=3, d=4, e=6, f=9
があります。
おそらくはこれひとつだけと存じます。

【付記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

ここから全数をあたるプログラムでも作ろうかと思っていたのです……とほほ

引用して返信編集・削除(未編集)

続きを手作業で証明してみました。

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」は不適。

以上により、解なし。

引用して返信編集・削除(未編集)

いやあ、素晴らしいです!

引用して返信編集・削除(未編集)

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)のみ。

引用して返信編集・削除(未編集)

さらに 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)
とわかりました。

引用して返信編集・削除(未編集)

らすかるさん、いろいろと勉強になります!
《n=0~19のときのa,b,c,d,e,fを全部7から引いて》→口をあんぐりとあけました!!!

引用して返信編集・削除(未編集)

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なので、条件を満たす数は存在しない。

引用して返信編集・削除(未編集)

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 を代入してもよいかもしれません。

引用して返信編集・削除(未編集)

それをするには a+b+c+d+e+f = 21 の証明を書き足さないといけないので……

引用して返信編集・削除(未編集)

あっなるほど。これはウッカリしておりました。失礼いたしました。

それにしても平方で評価するなんて驚きました。

引用して返信編集・削除(未編集)

このスレッドに返信

ロケットBBS

Page Top