a,b,c,d,nを自然数とする。 (1)a+b+c=nかつa≦b+c、b≦c+a、c≦a+bを満たす(a,b,c)の組の個数を求めよ。 (2)a+b+c+d=nかつa≦b+c+d、b≦c+d+a、c≦d+a+b、d≦a+b+cを満たす(a,b,c,d)の組の個数を求めよ。
数学オリンピックの問題みたいなのですが、解答が見つけられなくて(2)が解けないです。
(1)は、 a+b+c=n、a≦b+cからa≦n-aとなって、a≦n/2となり、 aは自然数なので、a≦[n/2]([ ]はガウス記号) 同様にb≦[n/2]、c≦[n/2]
a=kとすると、 [1] nが奇数のとき n=2m-1とおくと、b+c=2m-1-k、b≦m-1,c≦m-1より (b,c)=(m-k,m-1),(m-k+1,m-2),・・・,(m-1,m-k)のk組で、1≦k≦m-1より Σk(k=1..m-1)=1/2*m*(m-1)組 m=(n+1)/2より(n^2-1)/8組 [2] nが偶数のとき n=2mとおくと、b+c=2m-k、b≦m,c≦mより 1≦k≦m-1のとき (b,c)=(m-k,m),(m-k+1,m-1),・・・,(m,m-k)の(k+1)組で、 k=mのとき (b,c)=(1,m-1),(2,m-2),・・・,(m-1,1)の(m-1)組で より Σ(k+1)(k=1..m-1)+(m-1)=1/2*m*(m+3)-2組 m=n/2より(n^2+6n-16)/8組
だと思うのですが、(2)が同様にやろうと思ってもうまく解けません。 高校数学の範囲までで教えてください。
|
No.88116 - 2024/05/26(Sun) 00:32:15
| ☆ Re: 整数解の組の個数 / IT | | | (1)例えば(1,1,2)と(1,2,1),は別として数えるのでしょうか?
|
No.88117 - 2024/05/26(Sun) 10:15:44 |
| ☆ Re: 整数解の組の個数 / 大西 | | | ITさんご返信ありがとうございます。
a,b,c,dの大小関係はありませんので別として考えます。
|
No.88118 - 2024/05/26(Sun) 11:44:17 |
| ☆ Re: 整数解の組の個数 / IT | | | > [2] nが偶数のとき(n^2+6n-16)/8組 n=4 なら 3組 ですか? (1,1,1),(1,1,2)(1,2,1),(2,1,1) の4組では?
プログラムで求めると f(3)=1差分=1 f(4)=4差分=3 f(5)=7差分=3 f(6)=14差分=7
|
No.88119 - 2024/05/26(Sun) 12:00:33 |
| ☆ Re: 整数解の組の個数 / 大西 | | | ITさんご返信ありがとうございます。 a+b+c≦nではなくて、a+b+c=nですね。 問題文を訂正いたしました。
|
No.88120 - 2024/05/26(Sun) 13:01:55 |
| ☆ Re: 整数解の組の個数 / IT | | | それなら合ってそうですね。プログラムからの結果 f(1)=0差分=0 f(2)=0差分=0 f(3)=1差分=1 f(4)=3差分=2 f(5)=3差分=0 f(6)=7差分=4 f(7)=6差分=-1 f(8)=12差分=6 f(9)=10差分=-2 f(10)=18差分=8
|
No.88121 - 2024/05/26(Sun) 13:38:50 |
| ☆ Re: 整数解の組の個数 / IT | | | (2)プログラム出力 (合っているか未検証です) 差分の変化の規則性から帰納できるかも知れませんので参考までに載せます。 f(4)=1差分=1 f(5)=4差分=3 f(6)=10差分=6 f(7)=16差分=6 f(8)=31差分=15 f(9)=40差分=9 f(10)=68差分=28
|
No.88122 - 2024/05/26(Sun) 13:47:33 |
| ☆ Re: 整数解の組の個数 / 大西 | | | ITさんご返信ありがとうございます。 (2)はなかなか難しそうですね。
(1)の結果を使って和を取って求められそうな気がしているのですがなかなか見えてこないです。
|
No.88123 - 2024/05/26(Sun) 14:07:12 |
| ☆ Re: 整数解の組の個数 / らすかる | | | (2) a+b+c+d=nとなる組み合わせは(n-1)C3通り nが偶数のとき a>b+c+d⇔a>n/2なので a>b+c+dとなる組み合わせの数は(n/2-1)C3通り (A=a-n/2としてA+b+c+d=n/2となる組み合わせを求めればよい) b>c+d+a,c>d+a+b,d>a+b+cも同様なので 求める組の個数は(n-1)C3-4・(n/2-1)C3=(n-2)(n^2+2n-18)/12個 nが奇数のとき a>b+c+d⇔a>(n-1)/2なので a>b+c+dとなる組み合わせの数は((n+1)/2-1)C3通り b>c+d+a,c>d+a+b,d>a+b+cも同様なので 求める組の個数は(n-1)C3-4・((n+1)/2-1)C3=(n-3)(n-1)(n+1)/12個 従って求める組の個数は nが偶数のとき (n-2)(n^2+2n-18)/12個 nが奇数のとき (n-3)(n-1)(n+1)/12個 (必要ないかも知れませんが)偶奇まとめると {(2n^3-3n^2-23n+39)+(-1)^n・3(n^2-7n+11)}/24個
(1)もこの考え方で求めると簡単ですね。 a+b+c=nとなる組み合わせは(n-1)C2通り nが偶数のときa>b+cとなる組み合わせの数は(n/2-1)C2通りなので 求める組の個数は(n-1)C2-3・(n/2-1)C2=(n-2)(n+8)/8個 nが奇数のときa>b+cとなる組み合わせの数は((n+1)/2-1)C2通りなので 求める組の個数は(n-1)C2-3・((n+1)/2-1)C2=(n-1)(n+1)/8個 まとめると{(2n^2+6n-17)+(-1)^n・3(2n-5)}/16個
|
No.88147 - 2024/05/29(Wed) 13:19:18 |
| ☆ Re: 整数解の組の個数 / 大西 | | | らすかるさんご返信ありがとうございます。
らすかるさんの考え方がとても分かりやすくて理解できました。 数え上げることに必死で、全体から引くという考えは思い付きませんでした。 行き詰ったら、別の角度から考えてみることも大事ですね。
ありがとうございました。
|
No.88150 - 2024/05/30(Thu) 23:50:46 |
|