平成２７年１月１１日

[流れ星]

　　　　　第31５回数学的な応募解答

　　　　　　＜解答募集期間：1２月1４日〜1月1１日＞

［整数解・交代和の2題］

2014年も残り少なくなりました。今までのご応募に深く感謝申し上げます。来る2015年も引き続きご愛顧賜りますようよろしくお願いたします。。

問題１：ｎを正の整数とする。方程式　ｘ＋８ｙ＋８ｚ＝ｎ　を満たす正の整数 （ｘ，ｙ，ｚ）の組が３１３７５個存在するとき、ｎとして考えられる値の最大値を求めよ。

問題２：実数からなる空でない有限集合に対してその集合の「交代和」とは、要素を大きい順に並べて大きいほうから順番に足して、引いて、足して、引いて、・・・としてできたものとする。例えば,{１，２，３，７，９}の交代和は９−７＋３−２＋１＝４、｛５｝の交代和は５です。それでは｛１，２，３，・・・，ｎ｝の空でないすべての部分集合に対して交代和を計算したとき、それらの総和をｎで表せ。ただし、ｎは正の整数で、必要あらば空集合｛�刀pの交代和は０とする。＜出典：数学オリンピックへの道１　組合せ論の精選102問（朝倉書店）＞

「uchinyan」 12/14 13時57分　受信 更新 1/11

問題１：ｎを正の整数とする。方程式　ｘ＋８ｙ＋８ｚ＝ｎ　を満たす正の整数 （ｘ，ｙ，ｚ）の組が３１３７５個存在するとき、ｎとして考えられる値の最大値を求めよ。

x + 8y + 8z = n，n，x，y，z は正の整数，実際には n は 17 以上の整数，です。

u = y + z とおくと，u は 2 以上の整数で，

x + 8u = n

これを満たす u は 2 〜 [(n-1)/8] の整数で，x はこれらの u のそれぞれに対して一意に決まります。

これらの u に対して y，z は，y が 1 〜 u - 1 の整数で，z はこれらの y のそれぞれに対して一意に決まります。

そこで，k = [(n-1)/8] として，解の組の個数は全部で，

Σ[u=2,k]{u - 1} = Σ[u=1,k-1]{u} = k(k - 1)/2 個

これが 31375 になればいいので，

k(k - 1)/2 = 31375，k(k - 1) = 62750 = 251 * 250，k = 251

つまり，[(n-1)/8] = 251 になります。

これより，これを満たす n は，2009 〜 2016 なので，最大の n は 2016 になります。

(確認)　2015 になるのかな，と思ったのですが，違うので，念のために，十進ベーシックで確認してみました。

＜水の流れ：実はその通りでして、作問の中では2015を想定していました。８の倍数引く１でしたが・・・。ご指摘の通りでして恐れ入ります。＞

FOR n = 2000 TO 2020

LET cnt = 0

FOR y = 1 TO n/8

FOR z = 1 TO n/8

LET x = n - 8 * y - 8 * z

IF x > 0 THEN

LET cnt = cnt + 1

END IF

NEXT z

NEXT y

PRINT n; cnt

NEXT n

END

2000 30876

2001 31125

2002 31125

2003 31125

2004 31125

2005 31125

2006 31125

2007 31125

2008 31125

2009 31375

2010 31375

2011 31375

2012 31375

2013 31375

2014 31375

2015 31375

2016 31375 <----- ここ

2017 31626

2018 31626

2019 31626

2020 31626

確かに，n は 2016 のようです。

問題２：

まず，簡単な例で調べてみましょう。

{1} の場合

部分集合，φ，{1{，交代和，0，1，総和 1

{1,2} の場合

部分集合，φ，{1{，{2}，{1,2}，交代和，0，1，2，1，総和 4

{1,2,3} の場合

部分集合，φ，{1{，{2}，{1,2}，{3}，{1,3}，{2,3}，{1,2,3}，

交代和，0，1，2，1，3，2，1，2，総和 12

{1,2,3,4} の場合

部分集合，

φ，{1{，{2}，{1,2}，{3}，{1,3}，{2,3}，{1,2,3}，

{4}，{1,4}，{2,4}，{1,2,4}，{3,4}，{1,3,4}，{2,3,4}，{1,2,3,4}，

交代和，0，1，2，1，3，2，1，2，4，3，2，3，1，2，3，2，総和 32

．．．

総和を見ると，1 = 2^0，4 = 2 * 2^1，12 = 3 * 2^2，32 = 4 * 2^3，となっています。

そこで，{1,2,3,...,n} では n * 2^(n-1) と予想されます。

これは次のように考えれば明らかでしょう。

{1,2,3,...,n} の交代和の総和を S(n) とします。

するとこれは，交代和に n を含まない場合と含む場合との和になります。

n を含まない場合の交代和の総和は，{1,2,3,...,n-1} の交代和の総和に等しく S(n-1) です。

n を含む場合の交代和の総和は，

その場合の部分集合が {1,2,3,...,n-1} の部分集合に n を追加したものなので，

交代和の中で n は常に足されその個数は {1,2,3,...,n-1} の部分集合の個数 2^(n-1) 個，

それ以外は {1,2,3,...,n-1} の部分集合の要素ですが交代和の中では符号が反転するので総和は - S(n-1)，

結局，この場合は，n * 2^(n-1) - S(n-1)，です。

そこで，

S(n) = S(n-1) + (n * 2^(n-1) - S(n-1)) = n * 2^(n-1)

になります。

(感想)

問題１：で答えが 2015 かと思ったのですが，どうも違うようです。これでいいのでしょうか？何か勘違いしているのでしょうか？

問題２：は一見難しそうですが，実はあっさりと解けてしまうのですね。数学オリンピックだったら，国内の予選の中程度の難易度でしょうか。

「浜田明巳」 12/16 16時32分　受信 更新 1/11

問題１：ｘ＋８ｙ＋８ｚ＝ｎより，
　　８(ｙ＋ｚ)＝ｎ−ｘ
　１＋８・２≦ｎ≦８＋８・２のとき，
　　(ｘ，ｙ＋ｚ)＝(ｋ，２)（ｋ＝１，２，３，………，８)となり，１通りずつ．
　１＋８・３≦ｎ≦８＋８・３のとき，
　　(ｘ，ｙ＋ｚ)＝(ｋ，３)，(ｋ＋８・１，２)（ｋ＝１，２，３，………，８）となり，(２＋１)通りずつ．
　１＋８・４≦ｎ≦８＋８・４のとき，
　　(ｘ，ｙ＋ｚ)＝(ｋ，４)，(ｋ＋８・１，３)，(ｋ＋８・２，２)（ｋ＝１，２，３，………，８）
となり，(３＋２＋１)通りずつ．
　・・・
　１＋８ｍ≦ｎ≦８＋８ｍのとき，
　　(ｘ，ｙ＋ｚ)＝(ｋ，ｍ)，(ｋ＋８・１，ｍ−１)，(ｋ＋８・２，ｍ−２)，………，(ｋ＋８(ｍ−２)，２)（ｋ＝１，２，３，………，８）
となり，(ｍ−１)＋………＋３＋２＋１＝１／２・(ｍ−１)ｍ（通り）ずつ．
　１／２・(ｍ−１)ｍ＝３１３７５とすると，
　　(ｍ−１)ｍ＝３１３７５・２＝２５０・２５１
　関数(ｍ−１)ｍはｍ≧１で単調増加なので，
　　(ｍ−１，ｍ)＝(２５０，２５１)
　　∴ｍ＝２５１
　故にｎの最大値は，
　　８＋８・２５２＝２０１６………（答）

問題２：集合｛１，２，３，………，ｎ｝の部分集合の交代和の総和をａ_ｎとする．
　このとき，
　　ａ_ｎ＋１＝（集合｛１，２，３，………，ｎ，ｎ＋１｝の部分集合の交代和の総和）
　　　　＝（集合｛１，２，３，………，ｎ｝の部分集合の交代和の総和）
　　　　　　　＋｛（集合｛１，２，３，………，ｎ｝の部分集合）∪｛ｎ＋１｝の部分集合の交代和の総和｝
である．
　集合｛１，２，３，………，ｎ｝の部分集合の１つを
　　｛ｂ_１，ｂ_２，ｂ_３，………，ｂ_ｍ｝（ｂ_１＜ｂ_２＜ｂ_３＜………＜ｂ_ｍ，ｍ≦ｎ）
とすると，この集合の交代和は，
　　ｂ_ｍ−ｂ_ｍ−１＋ｂ_ｍ−２−………＋(−１)^ｍ−１ｂ_１
　集合｛ｂ_１，ｂ_２，ｂ_３，………，ｂ_ｍ，ｎ＋１｝の交代和は，
　　(ｎ＋１)−ｂ_ｍ＋ｂ_ｍ−１−ｂ_ｍ−２＋………−(−１)^ｍ−１ｂ_１
　　　＝(ｎ＋１)−{ｂ_ｍ−ｂ_ｍ−１＋ｂ_ｍ−２−………＋(−１)^ｍ−１ｂ_１}
　また，集合｛１，２，３，………，ｎ｝の部分集合は，２^ｎ個ある．
　故に集合｛１，２，３，………，ｎ｝の部分集合）∪｛ｎ＋１｝の部分集合の交代和の総和は，
　　(ｎ＋１)・２^ｎ−ａ_ｎ
　　∴ａ_ｎ＋１＝ａ_ｎ＋{(ｎ＋１)・２^ｎ−ａ_ｎ}＝(ｎ＋１)２^ｎ
　ａ_１＝１より，
　　ａ_ｎ＝ｎ・２^ｎ−１（ｎ＝１，２，３，………）

「浜田明巳」 12/18 10時08分　受信 更新 1/11

Ｅｘｃｅｌのマクロで解いた．
問題１：１≦ｎ≦１００００で計算した結果，
　　ｎ＝２００９，２０１０，２０１１，………，２０１６のとき，３１３７５組
となる．
　したがって答は２０１６である．

Option Explicit 'x+8y+8z=n
Const n_max As Long = 10000
Dim a(n_max) As Integer
Sub Macro1()
     Cells(1, 1).Value = 0
     Dim x As Long, y As Long, z As Long
     Dim n As Long, k As Long
     For n = 1 + 8 + 8 To n_max
       Cells(2, 1).Value = n
       k = 0
       For z = 1 To Int((n - 1 - 8) / 8)
         For y = 1 To Int((n - 1 - 8 * z) / 8)
           x = n - 8 * y - 8 * z
           k = k - (x >= 1)
         Next y
       Next z
       Cells(3, 1).Value = k
       If k = 31375 Then
         Cells(1, 1).Value = Cells(1, 1).Value + 1
         Cells(Cells(1, 1).Value, 2).Value = n
         Range("B" & Cells(1, 1).Value).Select
       End If
     Next n
End Sub

問題２：１≦ｎ≦２０で計算した結果，
　　すべて，ｎ・２^ｎ−１
となる．

Option Explicit
Dim a(20) As Integer
Sub Macro2()
     Dim n As Long
     For n = 1 To 20
       Cells(n, 1).Value = n
       Cells(n, 2).Value = 0
       Call saiki(n, 1)
       Range("A" & n).Select
     Next n
End Sub
Sub saiki(ByVal n As Integer, ByVal m As Integer)
     Dim fugou As Integer, j As Integer
     a(m) = 0
     While a(m) <= 1
       If m < n Then
         Call saiki(n, m + 1)
       Else
         fugou = -1
         For j = n To 1 Step -1
           If a(j) Then
             fugou = -fugou
             Cells(n, 2).Value = Cells(n, 2).Value + fugou * j
           End If
         Next j
       End If
       a(m) = a(m) + 1
     Wend
End Sub

「ｽﾓｰｸﾏﾝ」 12/20 22時48分　受信 更新 1/11

問題１：

8(y+z)=n-x=8m

m=2k のとき…

y+zは…

1-(2k-1)

2-(2k-2)

…

k-k

から…2k+1通りの解がある。

m=2k-1 のときは…2k通りの解しかないので、

2k+1=31375 の方で、

2k=31375-1=31374

8m=8*31374=250992

xは最小でも8なので…n=250992+8=251000

のはず…^^

問題２

回答

n=2m のとき…

明らかに、連続するペアの差は1なので…交代和=m=n/2

n=2m-1 のとき…

偶数のときに倣い…

2m-2 においては…-(m-1)

一番大きい数が2m-1だから…

交代和=2m-1-(m-1)=m=(n+1)/2

でいいですね ^^

「ｽﾓｰｸﾏﾝ」 12/23 20時31分　受信 更新 1/11

問題１：

8(y+z)=n-x=8m

m個の間(m-1)カ所に区切りを入れる…

m-1=31375

m=31376

xは最小で8なので…

n=8m+8=8*(m+1)=8*31377=251016

のはずですね ^^;v

＜水の流れ：どこかでミスがあり、答えに至っていませんが・・・＞

問題２

{1,2,3,4,5} のとき...

先頭が5のとき、残り4個と{1,2,3,4}は打ち消し合う。

先頭が4のとき、残り3個と打ち消し合う。

先頭が3のとき、残り2個と打ち消し合う。

先頭が2のとき、残り1個と打ち消し合う。

これは、{1,2,3,5}とか、{2,4}でも同じ。

つまり、5*2^4

一般にも、

n*2^(n-1)

になりそうな…?

たとえば…

5-4+3-2+1　　4-3+2-1　　3-2+1　　2-1　　1

5-4+3-2　　　 4-3+2　　　 3-2　　　 2

5-4+3-1　　　 4-3+1　　　 3-1

5-4+2-1　　　 4-2+1        3

5-3+2-1　　　 4-3

5-4+3　　　　　4-2

5-4+2　　　　　4-1

5-4+1　　　　　4

5-3+2

5-3+1

5-2+1

5-4

5-3

5-2

5-1

5

「早起きのおじさん」 12/24 16時37分　受信 更新 1/11

問題１

方程式を次のように変形して考えます。

xは8より小さい正の整数を初項として、公差8の等差数列の値をとります。

例えばn＝39としてみます。

正の整数の組の個数を数えます。

　

1つのxに対してyとzは和が一定になります。

この場合は、1＋2＋3＝6組となります。

(組数の合計6は、自然数の1から3までの和です)

つまりn＝7＋8×(3＋1)＝39です。

7は8より小さい整数の最大です。

自然数の1からmまでの合計は、なので、

として

m＝250(＞0)

よって、n＝7＋8×(250＋1)＝2015です。

と思いましたが、ｘになりうる数の最小は8をこえなければよいので、8となります。

よって、n＝8＋8×(250＋1)＝2016が解答になります。

＜上の部分は12月24日22時18分に訂正を受信しました＞

問題２

｛1,2,･･･,n｝のすべての部分集合の交代和の総和をF(n)で表します。

｛1,2,･･･,n｝の部分集合で要素の個数がkのものすべての交代和の合計をf(n,k)で表します。

つまり、F(n)＝f(n,1)＋f(n,2)＋f(n,3)＋･･････＋f(n, n)です。

具体的にいくつか例をみてみます。

n＝1のとき：｛1｝

F(1)＝f(1,1)＝1

n＝2のとき：｛1,2｝

　要素が1個の部分集合は、｛1｝、｛2｝なので、f(2,1)＝1＋2＝3

　要素が2個の部分集合は、｛1,2｝なので、f(2,2)＝1

　F(2)＝f(2,1)＋f(2,2)＝3＋1＝4

n＝3のとき：｛1,2,3｝

　要素が1個の部分集合は、｛1｝、｛2｝、｛3｝なので、f(3,1)＝1＋2＋3＝6

　要素が2個の部分集合は、｛1,2｝、｛1,3｝、｛2,3｝なので、f(3,2)＝1＋2＋1＝4

　要素が3個の部分集合は、｛1,2,3｝なので、f(3,3)＝2

　F(3)＝f(3,1)＋f(3,2)＋f(3,3)＝6＋4＋2＝12

f(n, k)の値を表にします。

この結果をみると、次の漸化式が予想されます。

式の解釈はあとにして、漸化式を解きます。

上の漸化式の両辺を で割ります。

ここで、とおくと、漸化式が、 となり、 は等差数列になります。

初項 、公差 なので、

よって、

さて、漸化式の意味を考えます。

具体的にF(5)、F(6)を調べてみます。

F(4)を考えるための部分集合

F(5)を考えるための部分集合

　f(5,1)　｛1｝、｛2｝、｛3｝、｛4｝、｛5｝

　f(5,2)　｛1,2｝、｛1,3｝、｛1,4｝、｛1,5｝、

｛2,3｝、｛2,4｝、｛2,5｝、

｛3,4｝、｛3,5｝、

｛4,5｝

　f(5,3)　｛1,2,3｝、｛1,2,4｝、｛1,2,5｝、｛1,3,4｝、｛1,3,5｝、｛1,4,5｝、

｛2,3,4｝、｛2,3,5｝、｛2,4,5｝、

｛3,4,5｝

　f(5,4)　｛1,2,3,4｝、｛1,2,3,5｝、｛1,2,4,5｝、｛1,3,4,5｝、｛2,3,4,5｝

　f(5,5)　｛1,2,3,4,5｝

F(6)を考えるための部分集合

　f(6,1)　｛1｝、｛2｝、｛3｝、｛4｝、｛5｝、｛6｝、

　f(6,2)　｛1,2｝、｛1,3｝、｛1,4｝、｛1,5｝、｛1,6｝、

｛2,3｝、｛2,4｝、｛2,5｝、｛2,6｝、

｛3,4｝、｛3,5｝、｛3,6｝、

｛4,5｝、｛4,6｝、

｛5,6｝

　f(6,3)　｛1,2,3｝、｛1,2,4｝、｛1,2,5｝、｛1,2,6｝、

｛1,3,4｝、｛1,3,5｝、｛1,3,6｝、

｛1,4,5｝、｛1,4,6｝、

｛1,5,6｝、

｛2,3,4｝、｛2,3,5｝、｛2,3,6｝、｛2,4,5｝、｛2,4,6｝、｛2,5,6｝、

｛3,4,5｝、｛3,4,6｝、｛3,5,6｝

｛4,5,6｝

　f(6,4)　｛1,2,3,4｝、｛1,2,3,5｝、｛1,2,3,6｝、｛1,2,4,5｝、｛1,2,4,6｝、｛1,2,5,6｝、

｛1,3,4,5｝、｛1,3,4,6｝、｛1,3,5,6｝、

｛1,4,5,6｝、

｛2,3,4,5｝、｛2,3,4,6｝、｛2,3,5,6｝、｛2,4,5,6｝、

｛3,4,5,6｝

　f(6,5)　｛1,2,3,4,5｝、｛1,2,3,4,6｝、｛1,2,3,5,6｝、｛1,2,4,5,6｝、｛1,3,4,5,6｝、｛2,3,4,5,6｝

　f(6,5)　｛1,2,3,4,5,6｝

説明A：kが偶数のとき

f(6,2)の1を含まない部分集合は、f(5,2)の部分集合の各要素に1を加えたものです。

　　　　f(6,2)の1を含まない部分集合の交代和はの合計は、f(5,2)です。

説明B：kが奇数のとき

f(6,3)の1を含まない部分集合は、f(5,3)の部分集合の各要素に1を加えたものです。

　　　　交代和は、それぞれが1大きくなります。

　　　個数は、 です。

f(6,3)の1を含まない部分集合の交代和の合計は、f(5,3)＋です。

説明C：kが奇数のとき

f(6,3)の1を含む部分集合は、f(6,2)の1を含まない部分集合と1との和集合です。

f(6,3)の1を含む部分集合の交代和の合計は説明Aより、f(5,2)＋ になります。

説明D：kが偶数のとき

f(6,4)の1を含む部分集合は、f(6,3)の1を含まない部分集合と1との和集合です。

f(6,4)の1を含む部分集合の交代和の合計は説明Bより、f(5,3) になります。

このことをふまえて、F(n)とF(n+1)について、f(n, k)とf(n+1,k)を比較していきます。

k＝1のとき

　f(n,1)は、｛1｝、｛2｝、･･･、｛n｝の交代和の合計です。

　f(n+1,1)は、｛1｝、｛2｝、｛3｝、･･･、｛n+1｝の交代和の合計です。

　これを｛1｝と青色の部分に分けて考えます。

　｛1｝の交代和は、1(＝)です。

青色の部分の交代和の合計は、f(n,1)の部分集合｛1｝、｛2｝、･･･、｛n｝のそれぞれが1増加したものです。

つまり、青色の部分の交代和の合計はf(n,1)＋1＋1＋･･･＋1＝f(n,1)＋n＝f(n,1)＋

よって、f(n+1,1)＝＋ f(n,1)＋

k＝2のとき

　f(n,2)は、

｛1,2｝、｛1,3｝、･･････････、｛1,n｝、

｛2,3｝、｛2,4｝、･･･、｛2,n｝、

･･･、

｛n−1, n｝

の交代和の合計です。

　f(n+1,2)は、

｛1,2｝、｛1,3｝、･････････････････、｛1,n+1｝、

｛2,3｝、｛2,4｝、･････････、｛2,n＋1｝、

｛3,4｝、｛3,5｝、･･･｛3,n＋1｝、

･･･、

｛n, n＋1｝

の交代和の合計です。

　これを1行目と青色の部分に分けて考えます。

　1行目の交代和の合計は、f(n,1)と等しくなります。

青色の部分の交代和の合計は、

f(n,2)の部分集合のそれぞれに1を加えたものとして考えます。

数が2個なのでそれぞれの数が1増えても差は等しくなります。

つまり、青色の部分の交代和の合計はf(n,2)と等しくなります。

よって、f(n+1,2)＝ f(n,1)＋f(n,2)

f(n, k)を考えるとき、部分集合は

｛1,･･･,k｝、･･･････････････････････････････････････････････、｛1,･･･,n｝、

｛2,･･･,k＋1｝、･･･････････････････････････････････、｛2,･･･,n｝、

･･･、

｛n−k＋1,･･･,n｝

f(n＋1,k)を考えるとき、部分集合は

｛1,･･･,k｝、････････････････････････････････････････････････････････、｛1,･･･,n＋1｝、

｛2,･･･,k＋1｝、･････････････････････････････････････････、｛2,･･･n＋1｝、

｛3,･･･,k＋2｝、･････････････････････････････、｛3,･･･n＋1｝、

･･･、

｛n−k＋2, ･･･,n＋1｝

f(n＋1,k)を考えるとき、部分集合を1を含む部分集合とそうでないものに分けます。

1を含むものは、f(n＋1,k−1)の1を含まない部分集合と1との和集合になります。

1を含まないものは、f(n, k)の部分集合の各要素に1を加えたものです。

f(n＋1,k)について

・kが偶数のとき

1を含む部分集合の交代和の合計は、f(n＋1,k−1)の1を含まない部分集合

｛2,･･･,k｝、･･･････････････････････････、｛n−k＋3,･･･,n＋1｝

のそれぞれの交代和の合計と等しくなります。

　つまり、

　｛1,･･･,k−1｝、･･･････････････････････････、｛n−k＋2,･･･,n｝

　の交代和の合計を考えればよいので、f(n, k−1)と等しくなります。

1を含まない部分集合の交代和の合計は、f(n, k)となります。

　よって、f(n＋1,k)＝f(n, k−1)＋f(n, k)

・kが奇数のとき、

1を含む部分集合の交代和の合計は、f(n＋1,k−1)の1を含まない部分集合

｛2,･･･,k｝、･･･････････････････････････、｛n−k＋3,･･･,n＋1｝

のそれぞれの交代和に1を加えたものの合計と等しくなります。

　つまり、f(n, k−1)の部分集合

　｛1,･･･,k−1｝、･･･････････････････････････、｛n−k＋2,･･･,n｝

のそれぞれの交代和に1を加えたものの合計と等しくなるので、f(n, k−1)＋となります。

1を含まない部分集合の交代和の合計は、f(n, k)＋となります。

　よって、f(n＋1,k)＝f(n, k−1)＋＋f(n, k)＋

最後に、f(n＋1,n＋1)を考えます。

・n＋1が偶数なら、f(n＋1,n＋1)＝f(n, n)です。

・n＋1が奇数なら、f(n＋1,n＋1)＝f(n, n)＋1＝f(n, n)＋です。

以上からF(n＋1)について整理すると、

・n＋1が奇数なら、

F(n＋1)＝f(n＋1,1)＋f(n＋1,2)

＋f(n＋1,3)＋f(n＋1,4)

＋･･･

＋f(n＋1,n−1) ＋f(n＋1,n)

＋f(n＋1,n＋1)

　　　 ＝｛＋ f(n,1)＋｝＋｛f(n,1)＋f(n, 2)｝

＋｛f(n,2)＋＋f(n, 3)＋｝＋｛f(n,3)＋f(n, 4)｝

＋･･･

　　　　＋｛f(n, n−2) ＋＋f(n, n−1) ＋｝＋｛f(n, n−1) ＋f(n, n)｝

＋｛f(n, n) ＋｝

　　　 ＝2×｛f(n,1)＋f(n,2)＋･･･＋f(n, n−1)＋ f(n, n)｝＋｛＋＋＋･･･＋｝

　　　 ＝

・n＋1が偶数なら、

F(n＋1)＝f(n＋1,1)＋f(n＋1,2)

＋f(n＋1,3)＋f(n＋1,4)

＋･･･

＋f(n＋1,n)＋f(n＋1,n＋1)

　　　 ＝｛＋ f(n,1)＋｝＋｛f(n,1)＋f(n, 2)｝

＋｛f(n,2)＋＋f(n, 3)＋｝＋｛f(n,3)＋f(n, 4)｝

＋･･･

　　　　＋｛f(n, n−1) ＋＋f(n, n) ＋｝＋｛f(n, n)｝

　　　 ＝2×｛f(n,1)＋f(n,2)＋･･･＋f(n, n−1)＋ f(n, n)｝＋｛＋＋＋･･･＋｝

　　　 ＝

となります。

＜水の流れ：いつもながら分かりやすく丁寧できれいな解答です。助かります。＞

「二度漬け白菜」 01/05 19時26分　受信 更新 1/11

以下では，実数 x に対して，a≦x＜a+1 を満たす整数 a を floor(x) と表し，
二項係数をcomb(a,b)というように表すことにします．
(つまり，comb(a,b)=a!/(b!*(a-b)! です．)

問題1：nとして考えられる値の最大値は2016．(答)

x+8*y+8*z=n ---(1)
を満たす正整数(x,y,z)の組の個数を f(n) とする．
(1) ⇔ (x-1)+8*(y-1)+8*(z-1)=(n-17)
であるので，f(n)は，
a+8*b+8*c=(n-17) ---(2)
を満たす非負整数の組(a，b，c)の個数に等しい．
さらに，(2)を満たすような非負整数の組(a，b，c)の個数は，
8*b+8*c≦(n-17)を満たすような非負整数の組(b，c)の個数に等しい．
さらにこのような組(b，c)の個数は，
b+c≦floor((1/8)*(n-17))を満たすような非負整数の組(b，c)の個数に等しい．
そしてさらにこのような組(b，c)の個数は，
a+b+c=floor((1/8)*(n-17))
を満たすような非負整数の組(a，b，c)の個数に等しい．
よって，
f(n)
=comb(floor((1/8)*(n-17))+2，2)
=(1/2)*(floor((1/8)*(n-17))+2)*(floor((1/8)*(n-17))+1)．

f(n)=31375 となるようなnの値の範囲を求める．
f(n)=31375より，(1/2)*(floor((1/8)*(n-17))+2)*(floor((1/8)*(n-17))+1)=31375．
よって，floor((1/8)*(n-17))=249．
よって，
249≦(1/8)*(n-17)＜250．
よって，2009≦n＜2017．
以上よりnとして考えられる値の最大値は2016．

問題2： 求める総和は，n*2^(n-1)．(答)　

集合{1，2，3，…，n}の部分集合Sに対して，
Sの交代和を f(S) で表す．
集合{1，2，3，…，n-1}の任意の部分集合Aに対して，
集合 {n}∪A を対応させる．
このようなペア (A ，{n}∪A) を考えることにより，
{1，2，3，…，n}のすべての部分集合が2個ずつのペアになる．
f({n}∪A)=n-f(A) に注意する．
求める総和は，
Σ[S⊂{1，2，3，…，n}]f(S)
=Σ[A⊂{1，2，3，…，n-1}](f(A) + (n-f(A)))
=Σ[A⊂{1，2，3，…，n-1}](n)
=n*2^(n-1)．

(別解)
1≦k≦n であるような k に対して，
｛1，2，…， n｝の空でないすべての部分集合に対して交代和を計算したとき，
+k および -k が何回現れるかを考える．
k∈S⊂{1，2，…，n}なるSに対し，Sの元を大きい順に並べたとき，
kが奇数番目に来るときに，Sの交代和の計算において +k が現れる．
このようなSの個数は，
(comb(n-k，0)+comb(n-k，2)+comb(n-k，4)+comb(n-k，6)+…)*2^(k-1) 個．
また，Sの元を大きい順に並べたとき，kが偶数番目に
来るときに，Sの交代和の計算において -k が現れる．
このようなSの個数は，
(comb(n-k，1)+comb(n-k，3)+comb(n-k，5)+…)*2^(k-1) 個．

以上ことを考えると，求める総和は，
Σ[k=1〜n](comb(n-k，0)+comb(n-k，2)+comb(n-k，4)+comb(n-k，6)+…)*2^(k-1)*(+k)
+Σ[k=1〜n](comb(n-k，1)+comb(n-k，3)+comb(n-k，5)+…)*2^(k-1)*(-k)
=Σ[k=1〜n-1](comb(n-k，0)+comb(n-k，2)+comb(n-k，4)+comb(n-k，6)+…)*2^(k-1)*(+k)
+Σ[k=1〜n-1](comb(n-k，1)+comb(n-k，3)+comb(n-k，5)+…)*2^(k-1)*(-k)
+(2^(n-1))*n
=Σ[k=1〜n-1](2^(k-1)*(k)*Σ[j=0〜n-k](-1)^j*comb(n-k，j)) + (2^(n-1))*n
=Σ[k=1〜n-1]2^(k-1)*(k)*(-1+1)^(n-k) + (2^(n-1))*n
=Σ[k=1〜n-1]2^(k-1)*(k)*0^(n-k) + (2^(n-1))*n
=0+(2^(n-1))*n
=(2^(n-1))*n．

「にいばりZ12」 01/05 22時26分　受信 更新 1/11

３１,３７５を素因数分解すると5³×251となります・・・�@

　

　　(x,y,z)＝(1,1,1),(2,1,1),・・・,(8,1,1)で各々ｎは17,18,19,20,21,22,23,24となります。

　　　たとえばｎ＝18としたとき、(x,y,z)＝(2,1,1)に一意に定まりx+8ｙ+8ｚ＝18の不定方程式の解となります。

　

　(x,y,z)＝(9,1,1)はn=25ですが、

　　x+8ｙ+8ｚ＝25の不定方程式の解は

　　（9,1,1）,（1,2,1）,（1,1,2）の3個となり不適です。

　　まず、特殊（簡単）な場合から考えていきます

　次の不定方程式の場合です（x,ｙ，nは正の整数；x≧1，ｙ≧1，n≧2）

　　x+ｙ＝n

　解が1個の場合　（x,ｙ，n）＝（1,1，2）

解が2個の場合（x,ｙ，n）＝（1,2，3）（x,ｙ，n）＝（2,1，3）

解が3個の場合（x,ｙ，n）＝（1,3，4）（x,ｙ，n）＝（2,2，4）（x,ｙ，n）＝（3,1，4）

解が4個の場合（x,ｙ，n）＝（1,4，5）（x,ｙ，n）＝（2,3，5）（x,ｙ，n）＝（3,2，5）（x,ｙ，n）＝（4,1，5）

以上のように解の個数は（x,ｙを変数と見た対称式なので）x,ｙの最大値に一致します。またこの時のｎは解の個数+1（ｘ（ｙ）の最大値+ｙ（ｘ）の最小値）

解の個数はｎ-1

次に

　x+2ｙ＝n　の場合を考えます。

　解が1個の場合（x,ｙ，n）＝（1,1，3）（x,ｙ，n）＝（2,1，4）

解が2個の場合（x,ｙ，n）＝（1,2，5）（x,ｙ，n）＝（3,1，5）（x,ｙ，n）＝（2,2，6）（x,ｙ，n）＝（4,1，6）

解が3個の場合（x,ｙ，n）＝（1,3，7）（x,ｙ，n）＝（3,2，7）（x,ｙ，n）＝（5,1，7）（x,ｙ，n）＝（2,3，8）（x,ｙ，n）＝（4,2，8）（x,ｙ，n）＝（6,1，8）

解が4個の場合（x,ｙ，n）＝（1,4，9）（x,ｙ，n）＝（3,3，9）（x,ｙ，n）＝（5,2，9）（x,ｙ，n）＝（7,1，9）（x,ｙ，n）＝（2,4，10）（x,ｙ，n）＝（4,3，10）（x,ｙ，n）＝（6,2，10）（x,ｙ，n）＝（8,1，10）

次に

　x+ x+2ｙ＝n　の場合を考えます。

　解が1個の場合（x,ｙ，n）＝（1,1，3）（x,ｙ，n）＝（2,1，4）

解が2個の場合（x,ｙ，n）＝（1,2，5）（x,ｙ，n）＝（3,1，5）（x,ｙ，n）＝（2,2，6）（x,ｙ，n）＝（4,1，6）

解が3個の場合（x,ｙ，n）＝（1,3，7）（x,ｙ，n）＝（3,2，7）（x,ｙ，n）＝（5,1，7）（x,ｙ，n）＝（2,3，8）（x,ｙ，n）＝（4,2，8）（x,ｙ，n）＝（6,1，8）

解が4個の場合（x,ｙ，n）＝（1,4，9）（x,ｙ，n）＝（3,3，9）（x,ｙ，n）＝（5,2，9）（x,ｙ，n）＝（7,1，9）（x,ｙ，n）＝（2,4，10）（x,ｙ，n）＝（4,3，10）（x,ｙ，n）＝（6,2，10）（x,ｙ，n）＝（8,1，10）

次にx+8ｙ＝n　の場合を考えます。

　解が1個の場合（x,ｙ，n）＝（1,1，9）（x,ｙ，n）＝（2,1，10）（x,ｙ，n）＝（3,1，11）（x,ｙ，n）＝（4,1，12）（x,ｙ，n）＝（5,1，13）（x,ｙ，n）＝（6,1，14）（x,ｙ，n）＝（7,1，15）（x,ｙ，n）＝（8,1，16）8ｙ＝n

の場合を考えます。

　解が1個の場合（x,ｙ，n）＝（1,1，9）（x,ｙ，n）＝（2,1，10）（x,ｙ，n）＝（3,1，11）（x,ｙ，n）＝（4,1，12）（x,ｙ，n）＝（5,1，13）（x,ｙ，n）＝（6,1，14）（x,ｙ，n）＝（7,1，15）（x,ｙ，n）＝（8,1，16）

解が2個の場合（x,ｙ，n）＝（1,2，17）（x,ｙ，n）＝（9,1，17）（x,ｙ，n）＝（2,2，18）（x,ｙ，n）＝（10,1，18）（x,ｙ，n）＝（3,2，19）（x,ｙ，n）＝（11,1，19）（x,ｙ，n）＝（4,2，20）（x,ｙ，n）＝（12,1，20）（x,ｙ，n）＝（5,2，21）（x,ｙ，n）＝（13,1，21）（x,ｙ，n）＝（6,2，22）（x,ｙ，n）＝（14,1，22）（x,ｙ，n）＝（7,2，23）（x,ｙ，n）＝（15,1，23）（x,ｙ，n）＝（8,2，24）（x,ｙ，n）＝（16,1，24）

解が3個の場合（x,ｙ，n）＝（1,3，25）（x,ｙ，n）＝（9,2，25）（x,ｙ，n）＝（17,1，25）（x,ｙ，n）＝（2,3，26）（x,ｙ，n）＝（10,2，26）（x,ｙ，n）＝（18,1，26）（x,ｙ，n）＝（3,3，27）（x,ｙ，n）＝（11,2，27）（x,ｙ，n）＝（19,1，27）（x,ｙ，n）＝（4,3，28）（x,ｙ，n）＝（12,2，28）（x,ｙ，n）＝（20,1，28）（x,ｙ，n）＝（5,3，29）（x,ｙ，n）＝（13,2，29）（x,ｙ，n）＝（21,1，29）（x,ｙ，n）＝（6,3，30）（x,ｙ，n）＝（14,2，30）（x,ｙ，n）＝（22,1，30）（x,ｙ，n）＝（7,3，31）（x,ｙ，n）＝（15,2，3（x,ｙ，n）＝（23,1，31）（x,ｙ，n）＝（8,3，32）（x,ｙ，n）＝（16,2，32）（x,ｙ，n）＝（24,1，32）

解が4個の場合（x,ｙ，n）＝（1，4，33）（x,ｙ，n）＝（9，3，33）（x,ｙ，n）＝（17，2，33）（x,ｙ，n）＝（25，1，33）（x,ｙ，n）＝（2，4，34）（x,ｙ，n）＝（10，3，34（x,ｙ，n）＝（18，2，34）（x,ｙ，n）＝（26，1，34）（x,ｙ，n）＝（3，4，35）（x,ｙ，n）＝（11，3，35）（x,ｙ，n）＝（19，2，35）（x,ｙ，n）＝（27，1，35）（x,ｙ，n）＝（4，4，36）（x,ｙ，n）＝（12，3，36）（x,ｙ，n）＝（20，2，36）（x,ｙ，n）＝（28，1，36）（x,ｙ，n）＝（5，4，37）（x,ｙ，n）＝（13，3，37）（x,ｙ，n）＝（21，2，37）（x,ｙ，n）＝（29，1，37）（x,ｙ，n）＝（6，4，38）（x,ｙ，n）＝（14，3，38）（x,ｙ，n）＝（22，2，38）（x,ｙ，n）＝（30，1，38）（x,ｙ，n）＝（7，4，39）（x,ｙ，n）＝（15，3，39）（x,ｙ，n）＝（23，2，39）（x,ｙ，n）＝（31，1，39）（x,ｙ，n）＝（8，4，40）（x,ｙ，n）＝（16，3，40）（x,ｙ，n）＝（24，2，40）（x,ｙ，n）＝（32，1，40）

ここまでの結果を俯瞰すると、次の法則に気づきます。

nによりｙの取りうる値がの個数が一意に決まる。

即ち、ｎ-8ｙ>0（∵x≧1）から8ｙがｎ-1を超えることができない

よって、ｙの個数（最大値ｙ_ｍａｘ）は

ｎが8で割り切れる場合

(ｎ/8 -1)となり最小値は1となります。

ｎが8で割り切れない場合

(ｎ/8の整数部)となり最小値は1となります

ｎとｙが決まるとｘはｙの値により各々一意に定まりその最大値は

ｎが8で割り切れる場合

ｘ_max=n-ｙ_min×8＝ｎ-1×8=n-8　

またその最小値は

ｘ_min= n-ｙ_max×8＝ｎ-（ｎ/8-1）×8= 8

ｎが8で割り切れない場合

ｘ_max=n-ｙ_min×8＝ｎ-1×8=n-8　

またその最小値は

ｘ_min= n-ｙ_max×8＝ｎ-（ｎ/8の整数部）×8

一般には、当然ｘ=ｎ-8ｙ(nが定まるとｙの値によって飛び飛び)となります。

いよいよ、問題1に取り組むわけですが

前述の

x+8ｙ＝n

と

x+ｙ＝n（ｙ+ｚ＝ｗ）

の結果を利用します

問題1の式

ｘ＋８ｙ＋８ｚ＝ｎを変形すると

x+8(ｙ+ｚ)＝n

ｙ+ｚ＝ｗと置くと

x+8ｗ＝n

となり、x+8ｙ＝nで行った議論がほぼ同様にできます。

（ただし変数の定義域がｗ≧2に注意が必要です）

　x+8ｗ＝n

の場合を考えます。

　解が1個の場合（x，w，n）＝（1，2，17）（x，w，n）＝（2，2，18）（x，w，n）＝（3，2，19）（x，w，n）＝（4，2，20）（x，w，n）＝（5，2，21）（x，w，n）＝（6，2，22（x，w，n）＝（7，2，23）（x，w，n）＝（8，2，24）

解が2個の場合（x，w，n）＝（1，3，25）（x，w，n）＝（9，2，25）（x，w，n）＝（2，3，26）（x，w，n）＝（10，2，26）（x，w，n）＝（3，3，27）（x，w，n）＝（11，2，27（x，w，n）＝（4，3，28）（x，w，n）＝（12，2，28）（x，w，n）＝（5，3，29）（x，w，n）＝（13，2，29）（x，w，n）＝（6，3，30）（x，w，n）＝（14，2，30）（x，w，n）＝（7，3，31）（x，w，n）＝（15，2，31）（x，w，n）＝（8，3，32）（x，w，n）＝（16，2，32）

解が3個の場合（x，w，n）＝（1，4，33）（x，w，n）＝（9，3，33）（x，w，n）＝（17，2，33）（x，w，n）＝（2，4，34）（x，w，n）＝（10，3，34）（x，w，n）＝（18，2，3（x，w，n）＝（3，4，35）（x，w，n）＝（11，3，35）（x，w，n）＝（19，2，35）（x，w，n）＝（4，4，36）（x，w，n）＝（12，3，36）（x，w，n）＝（20，2，36）（x，w，n）＝（5，4，37）（x，w，n）＝（13，3，37）（x，w，n）＝（21，2，37）（x，w，n）＝（6，4，38）（x，w，n）＝（14，3，38）（x，w，n）＝（22，2，38）（x，w，n）＝（7，4，39）（x，w，n）＝（15，3，39）（x，w，n）＝（23，2，39）（x，w，n）＝（8，4，40）（x，w，n）＝（16，3，40）（x，w，n）＝（24，2，40）

解が4個の場合（x，w，n）＝（1，5，41）（x，w，n）＝（9，4，41）（x，w，n）＝（17，3，41）（x，w，n）＝（25，2，41）（x，w，n）＝（2，5，42）（x，w，n）＝（10，4，4（x，w，n）＝（18，3，42）（x，w，n）＝（26，2，42）（x，w，n）＝（3，5，43）（x，w，n）＝（11，4，43）（x，w，n）＝（19，3，43）（x，w，n）＝（27，2，43）（x，w，n）＝（4，5，44）（x，w，n）＝（12，4，44）（x，w，n）＝（20，3，44）（x，w，n）＝（28，2，44）（x，w，n）＝（5，5，45）（x，w，n）＝（13，4，45）（x，w，n）＝（21，3，45）（x，w，n）＝（29，2，45）（x，w，n）＝（6，5，46）（x，w，n）＝（14，4，46）（x，w，n）＝（22，3，46）（x，w，n）＝（30，2，46）（x，w，n）＝（7，5，47）（x，w，n）＝（15，4，47）（x，w，n）＝（23，3，47）（x，w，n）＝（31，2，47）（x，w，n）＝（8，5，48）（x，w，n）＝（16，4，48）（x，w，n）＝（24，3，48）（x，w，n）＝（32，2，48）

これらから、不定方程式　x+8ｗ＝n（x≧1，ｗ≧2 ，n≧17）

の解の個数をｋとするとwは2からｋ+1までのｋ通りの値を取ることがわかります。

wがｋ+1（つまり解の個数に対する最大値）を取ったときxは最小値となり8

よってその時のｎの最大値は

　8（ｋ+1）+8=8k+16

ここでx+ｙ＝n（ｙ+ｚ＝ｗ）

の結果を利用します

ｗ＝ｙ+ｚと置いていることから

ｙ，ｚの組み合わせは

（2-1）+（3-1）+・・・・+（ｋ+1-1）＝k(k+1)/2

即ち不定方程式

ｘ+8（ｙ+ｚ）=n

の解の個数(P)がP =k(k+1)/2の場合

nの最大値は

n_max=8（ｋ+1）+8=8k+16

k=(-1+√(1+8P))/2から

n_max=4(-1+√(1+8P))+16=4√(1+8P)+12

よって

P=5³×251の時の

n_max=4√(1+8P)+12=2016・・・・・回答

計算が、煩雑になるので先にkを求めてみますと冒頭の素因数分解から

k(k+1)/2＝5³×251

k(k+1)＝2×5³×251=250×251

∴k=250

n_max=8k+16=2016

この計算だと、手計算でもなんとかなります。

なんとか新年の2015を導きたかったのですが至りませんでした。

おそらくどこかで計算間違いをしていると思います。

＜水の流れ：実はその通りでして、作問の中では2015を想定して・・・。ご指摘の通りでして恐れ入ります。＞

問題２：

先ず部分集合の意味を考えてみます

「全ての集合は部分集合として空集合を含む」

ここで問題では空集合を｛�刀pと表現していますがφまたは｛｝と考えます。

空集合は集合の元として存在するのではなく、集合そのものだからです。

自然数ｎまでの部分集合には空集合も含まれますが、この場合0と定義されているので計算上無視できます。

次に部分集合の元の数が問題になりますが、題意はすべてと言っているので、１，２，３，・・・，ｎを全て求めなければなりません

そこでまず、元が1個の場合を考えます

交代和の定義から元が1個の場合すべて正となるので

その総和は

n(n+1)/2です

次に元が2個の場合（このとき空集合を集合の元として考えると1個の場合と同じものが出てきてしまいます）

相異なる（n以下の）自然数を2個選んだ時

部分集合の個数は_nC₂=n!/(2!・(n-2))=n(n-1)/2、元の個数はn(n-1)個です

この時

nに注目すると

nを含む集合はn-1回出現します({n,n-1}{n,n-2}{n,n-3}{n,n-4}{n,n-5}{n,n-6}・・・・・{n,1})

nは最大数なので交代和における符号はすべて正

n-1に注目すると

n-1を含む集合はn-1回出現します({n,n-1}{n-1,n-2}{n-1,n-3}{n-1,n-4}{n-1,n-5}{n-1,n-6}・・・・・{n-1,1})

n-1は最大数-1なので交代和における符号は負が1個、正がn-2個

同様にして

n-iは最大数-iなので交代和における符号は負がi個、正がn-i-1個

これら注目した各元毎の総和は

n (n-1) +(n-1) (n-2)+(n-2) (n-3)+(n-3) (n-4) +(n-4) (n-5) +・・+(n-i) (n-i-1) +・・・+(n-(n-2))(n-(n-2)-1)+(n-(n-1))(n-(n-1)-1)-((n-1)+2(n-2)+・・・・i(n-i)+・・・+(n-1))

これを展開整理すると・・・・・・・・と、ここまで考えもっとシンプルな回答があるのではと思いました。

ある集合を考えます。

たとえば元が3個の

｛5,3,1｝

この交代和は5-3+1ですが

これには元の数がそれより少ない

対応する部分集合

2個と1個の部分集合が必ず存在し

それらを合計すると

5-3+1　　・・・元が3個の集合の交代和

5-3　　　・・・元が2個の集合の交代和

5  -1　　・・・元が2個の集合の交代和

+3-1　　・・・元が2個の集合の交代和

5+3+1　　・・・元が1個の集合の交代和の総和

これらを合計すると最大値以外は全てキャンセルアウトします

したがって回答は

20(元の最大値×最大値を含む部分集合の個数)

となりますがこれでは数学的な回答とはとても言えないので以下で述べます（交代和の定義は題意に沿います）

自然数1,2,3,4,5,・・・ｎの集合をPとします

その部分集合の個数はＮ＝_nC₁+ _nC₂+・・・・+ _nC_n

N=��_(i=1~n)　nC_ｉ=��_(i=0~n)　nC_ｉ-1・・・（_i=0~n) は�狽ﾌ上下に_i=0と_nを付けたものです。記号がうまく書けないものでご容赦ください）

よってNは2項係数の総和-1である事が解ります（2項係数の総和＝(1+1)ⁿ)

N=2ⁿ-1

全ての部分集合の中にある元が出現する回数は

元の個数が1個の場合その数以外で構成される組み合わせが除外されるので_ｎC₁−_ｎ-1C₁回=1回

元の個数が2個の場合その数以外で構成される組み合わせが除外されるので_ｎC₂−_ｎ-1C₂回

元の個数が3個の場合同様にその数以外で構成される組み合わせが除外されるので_ｎC₃−_ｎ-1C₃回

これを1~ｎまで足し合わせると

��_(i=1~n)　nC_ｉ−��_{(i=1~n)　n-1}C_ｉ

となり2項係数の総和の計算に基づくと

2ⁿ-1-（2^n-1-1）＝2^n-1

となります。数の大きさにかかわらず同数回出現することは直感的にもは予想できます。

次に各元の正負について考えます。

ｎは常に正です（∵交代和の定義から正から始まるため）

全ての部分集合の中にｎとｎ-1が同時に現れる個数はｎ-1現れた時にｎが現れない個数と等しい。

これは、組み合わせの対称性（即ちｎとｎ-1を交換しても組み合わせの個数が変わらない）を考慮すると、組み合わせの元の個数上にｎとn-1の差異はないことから自明です。これはｎ-iとn-i-1との間にも言えます。

すべての部分集合の内ｎ-1を含み且つｎを含む集合ではｎ-1の符号は−、ｎ-1を含みｎを含まない集合ではｎ-1の符号は+。その個数が等しいことから元ｎ-1の総和は0以下、ｎ-2・・・も同様で自然数1,2,3,4,5,・・・ｎの部分集合の交代和の総和は

2^n-1ｎ・・・・回答

補足

　数学的帰納法による証明

　自然数1,2,3,4,5,・・・ｎ-1の部分集合の交代和の総和が

2^n-2（n-1）

であることが真であると仮定すると

自然数1,2,3,4,5,・・・ｎの部分集合の交代和の総和が

　2^n-1n

であることとn-1=1で成立していることを証明する

自然数1,2,3,4,5,・・・ｎの部分集合の交代和の総和は

（ｎを含まない部分集合の交代和の総和＝2^n-2（n-1））+（nを含む部分集合の交代和の総和）

nを含む部分集合の交代和の個数はｎが規定値として定まっているので

　元が1個の場合_ｎ-1C₀=1個・・・元はｎ

　元が2個の場合_ｎ-1C₁個

元が3個の場合_ｎ-1C₂個

元が4個の場合_ｎ-1C₃個

・・・・

元がn-1個の場合_ｎ-1C_n-2個

元がn個の場合_ｎ-1C_n-1個=1個

これらの個数を足し合わせると

��_{(i=0~n-1)　n-1}C_ｉ=2 ^n-1

これらの交代和には規定値として最大数に正整数nが含まれるため

自然数1,2,3,4,5,・・・ｎの部分集合の交代和の総和は

自然数1,2,3,4,5,・・・ｎ-1の部分集合の交代和の総和の符号を反転したものと2 ^n-1nの和に等しい

よって

2 ^n-1n-2^n-2（n-1）+2^n-2（n-1）=2 ^n-1n

ｎ-1＝1の時

2^n-2（n-1）＝1

・・・・・・・・・・・証明終わり

「SPCK」 01/10 １５時27分　受信 更新　1/11

C++で解いた。
a = x-1, b = y-1, c = z-1とする。(a, b, cは0以上の整数)
(1+a) + 8(1+b) + 8(1+c) = n
a + 8b + 8c = n-17
となる。
このプログラムではn-17の値(_n変数)を0から一つずつ増やしていってa, b, cの
組み合わせを求め31375通りを越えたらその一つ前のn-17の値に+17を足して31375通りのx, y, zの組合せを持つ
最大のnを求めている。

a, b, cの組み合わせを求める際、次のように考えている。
b, cが共に0である場合を考えるとa = n-17となる一通りが存在する。
このaから8を引いてn-17の値を保つにはb+cの値を1増やさなければならない。
だから、aが不敵な値になる直前まで8を引き続けると、b+cの値は1ずつ増えていくので、
a, b, cの組み合わせも2P1, 3P1, 4P1...となる。
b, cが共に0である場合の一通りも合わせて考えると
aが不適な値になる直前まで8を引き続けた時に一つのaの値に存在するa, b, cの組み合わせは
8を引けた回数をmとすると
1, 2, 3......m, m+1と表せる。
mは最初のaの値、つまりn-17を8で割った商であるため、等差数列の和の公式より
(1+(_n/8+1))*(_n/8+1)/2で求められる。

#include ＜cstdio＞
#include ＜cstdlib＞
#include ＜cmath＞
int main(void)
{
int _n = 0, C = 0;
while(C <= 31375){
_n++;
C = (1+(_n/8+1))*(_n/8+1)/2;
}
printf("%d\n", _n-1 + 17);
system("pause");
return 0;
}

＜水の流れ：どこかで考え方のミスをしていますね＞

「浜田明巳」 01/12　 17時14分　受信 更新　2/9

前回の問題の「SPCK」の解答で

C = (1+(_n/8+1))*(_n/8+1)/2;

を考えミスとしていたと思います。

しかし、Ｃ＋＋において、プログラム中、Cを整数宣言しているので、この式を計算した際、小数点以下は切り捨てされます。したがって、これで正解だと思います。

C++で解いた。
a = x-1, b = y-1, c = z-1とする。(a, b, cは0以上の整数)
(1+a) + 8(1+b) + 8(1+c) = n
a + 8b + 8c = n-17
となる。
このプログラムではn-17の値(_n変数)を0から一つずつ増やしていってa, b, cの
組み合わせを求め31375通りを越えたらその一つ前のn-17の値に+17を足して31375通りのx, y, zの組合せを持つ
最大のnを求めている。

a, b, cの組み合わせを求める際、次のように考えている。
b, cが共に0である場合を考えるとa = n-17となる一通りが存在する。
このaから8を引いてn-17の値を保つにはb+cの値を1増やさなければならない。
だから、aが不敵な値になる直前まで8を引き続けると、b+cの値は1ずつ増えていくので、
a, b, cの組み合わせも2P1, 3P1, 4P1...となる。
b, cが共に0である場合の一通りも合わせて考えると
aが不適な値になる直前まで8を引き続けた時に一つのaの値に存在するa, b, cの組み合わせは
8を引けた回数をmとすると
1, 2, 3......m, m+1と表せる。
mは最初のaの値、つまりn-17を8で割った商であるため、等差数列の和の公式より
(1+(_n/8+1))*(_n/8+1)/2で求められる。

#include ＜cstdio＞
#include ＜cstdlib＞
#include ＜cmath＞
int main(void)
{
int _n = 0, C = 0;
while(C <= 31375){
_n++;
C = (1+(_n/8+1))*(_n/8+1)/2;
}
printf("%d\n", _n-1 + 17);
system("pause");
return 0;
}

＜水の流れ：修正できて助かりました。どうもありがとうございます。2月9日記＞

皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。