◆海外 ブリタ さんからの解答
【問題1】
東西南北に対称な配置、すなわち、
aba b城b abaといった配置を考える。
番兵全体の人数をNとすると、
N=4(a+b)
11=2a+b
を満たすa,bが存在すれば、4辺をそれぞれ11人で守ることが出来る。
N=36を代入すれば、a=2,b=7が得られ、
272 7城7 272といった配置になる。
【問題2〜4】
上記【問題1】と同様の考え方で、
353 5城5 353(N=32) 434 3城3 434(N=28) 515 1城1 515(N=24)が得られる。
【問題5】
4辺が同数の番兵で守れるよう、
abc b城b cbaといった配置を考えてみる。
番兵全体の人数をNとすると、
N=2a+4b+2c
11=a+b+c
を満たすa,b,cが存在すれば、4辺をそれぞれ11人で守ることが出来る。
N=22を代入すれば、a+c=11,b=0が得られ、
(a,b)の組合せは(0,11)、(1,10)、(2,9)、…、(11,0)の12通り。
従って、例えば、
506 0城0 605といった配置が可能。
【感想】
題意では何か一つ回答を見つければ十分でしょうから、近道するために対称性を使いました。
でもやはり4辺の守りを固めるのが目的ですから、いくら題意を満たしているとはいえ、
1100 0城0 0011みたいなイビツな守りじゃ不安ですよね。
◆茨城県 mitchy さんからの解答
a、b、c、 b、城、b、 c、b、a、という対称性をもった配置の場合
【問題1】
連立方程式を立てると
a+ b+ c=11 ・・・(1)
2a+4b+2c=36 ・・・(2)
これより
b=7、 a+c=4
よってすべての解は
(a、b、c)=(4、7、0) =(3、7、1) =(2、7、2) =(1、7、3) =(0、7、4)【問題2】
同様に解くと
2a+4b+2c=32 ・・・(3)
式(1)および(3)より
b=5、 a+c=6
よってすべての解は
(a、b、c)=(6、5、0) =(5、5、1) =(4、5、2) =(3、5、3) =(2、5、4) =(1、5、5) =(0、5、6)【問題3】
同じく
2a+4b+2c=28 ・・・(4)
式(1)および(4)より
b=3、 a+c=8
よってすべての解は
(a、b、c)=(8、3、0) =(7、3、1) =(6、3、2) =(5、3、3) =(4、3、4) =(3、3、5) =(2、3、6) =(1、3、7) =(0、3、8)【問題4】
2a+4b+2c=24 ・・・(5)
式(1)および(5)より
b=1、 a+c=10
よってすべての解は
(a、b、c)=(10、1、 0) =( 9、1、 1) =( 8、1、 2) =( 7、1、 3) =( 6、1、 4) =( 5、1、 5) =( 4、1、 6) =( 3、1、 7) =( 2、1、 8) =( 1、1、 9) =( 0、1、10)【問題5】
これも同じく
2a+4b+2c=22 ・・・(6)
式(1)および(6)より
b=0、 a+c=11
よってすべての解は
(a、b、c)=(11、0、 0) =(10、0、 1) =( 9、0、 2) =( 8、0、 3) =( 7、0、 4) =( 6、0、 5) =( 5、0、 6) =( 4、0、 7) =( 3、0、 8) =( 2、0、 9) =( 1、0、10) =( 0、0、11)
◆北海道 YUJI さんからの解答
番兵の数をX、各箇所の番兵の数をそれぞれ以下のように定義する。
AbC
h城d
GfE
定義より、
A+b+C+d+E+f+G+h=X ・・・(1) A+b+C=11 ・・・(2) C+d+E=11 ・・・(3) E+f+G=11 ・・・(4) G+h+A=11 ・・・(5)(1)へ(2)、(4)を代入して、
11+d+11+h=X
d+h=X−22 ・・・(6)
同様に(1)へ(3)、(5)を代入して、
b+f=X−22 ・・・(7)
また(1)に(6)、(7)を代入して、
A+C+E+G+2(X−22)=X
A+C+E+G=44−X ・・・(8)
【問題1】〜【問題5】Answer.
各頂点の合計が(A+C+E+G)が、
44人から総番兵数を差し引いた数(44−X)になるように配置した後、
各辺の合計が11人になるようにb、d、f、hに配置すればよい。
【おまけ】
各辺11人としていたものを一般形N人と定義する。
ゆえに、(6)は、以下の通りになる。
d+h=X−2N ・・・(9)
d≧0、h≧0より、
X≧2N ・・・(10)
また、(8)においては、
A+C+E+G=4N−X ・・・(11)
A≧0、C≧0、E≧0、G≧0より、
X≦4N ・・・(12)
【おまけ】Answer.
番兵の数(N)は、一辺の番兵数の2倍(2N)以上、4倍(4N)以下にすれば、問題が作成できる。
【問題1】
2,7,2 7 7 2,7,2考え方:
城の隅に配置された番兵は2つの辺を守っています。
一方、辺の中央に配置された番兵は1つの辺のみを守っています。
したがって、隅の番兵は辺の中央の番兵の2倍の働きをしていることになります。
このことから、4辺の中央の番兵を1人ずつ減らして、隅へ1人ずつ配置すると、番兵の数を変えずに辺の守りを1人ずつ増やすことができます。
よって、この新しい配置から4辺の中央の番兵の数を1人ずつ減らせば、番兵の数を4人減らして、辺を守る番兵の数を元のままとすることができます。
以下【問題2】から【問題4】まで同様の考え方で配置を決めることができます。
【問題2】
3,5,3 5 5 3,5,3【問題3】
4,3,4 3 3 4,3,4【問題4】
5,1,5 1 1 5,1,5【問題5】
6,0,5 0 0 5,0,6考え方:
【問題1】の考え方を進めていくと、番兵の数が24人、かつ辺の中央の番兵の数が0人で、辺を守っている番兵の数が12人の配置に行き着きます。
ここから番兵の数を2人減らして、辺の守りの数を11人にするためには、ひとつの対角の隅の番兵を1人ずつ減らせばよいことにな
ります。
【おまけ】
問題を一般化してみます。
番兵の数をM人、4辺を守る番兵の数をN人とし、このような配置が存在する条件と解を求めます。
解が存在する条件は【問題1】〜【問題5】から2N≦M≦4Nと判りますが、以下方程式を立てることから導いてみます。
配置を下記のようにします。
k1,h1,k2 h4 h2 k4,h3,k3条件より
k1+h1+k2=N ・・・(1)式 k2+h2+k3=N ・・・(2)式 k3+h3+k4=N ・・・(3)式 k4+h4+k1=N ・・・(4)式 k1+k2+k3+k4+h1+h2+h3+h4=M ・・・(5)式5つの一次式に対し、8個の変数があるため、解が存在すれば、少 なくとも3個の変数を独立に定めることができます。
(1)-(2)+(3)-(4)より、h1+h3=h2+h4 ・・・(6)式 (k1+h1+k2)+(k2+h2+k3)+(k3+h3+k4)+(k4+h4+k1)+h1+h2+h3+h4=2Mより h1+h2+h3+h4=2M-4N ・・・(7)式 (6)、(7)式より、 h1+h3=h2+h4=M-2N ・・・(8)式ここでh1,h4,k1を独立な3変数に定めてみます。
h3=M-2N-h1 ・・・(9)式 h2=M-2N-h4 ・・・(10)式 (1)式より、k2=N-k1-h1 ・・・(11)式 (4)式より、k4=N-k1-h4 ・・・(12)式 (2)、(10)、(11)式より、 k3=N-k2-h2=k1+h1+h4-(M-2N) ・・・(13)式(9)〜(13)式は、代入により(1)〜(5)式を満たすので、(1)〜(5)式の 解です。
題意に適合する解は、すべての変数が0以上の整数でなければなりません。
まず(1)〜(4)式より、明らかに
0≦h1≦N、0≦h4≦N、0≦k1≦N ・・・(14)式
また(9)、(10)式より 0≦h1≦M-2N ・・・(15)式 0≦h4≦M-2N ・・・(16)式 (11)、(12)式より k1≦N-h1 ・・・(17)式 k1≦N-h2 ・・・(18)式 また(13)式より M-2N-h1-h4≦k1 ・・・(19)式(17)〜(19)式より
(20)式よりk1が存在する条件として
M-2N-h1-h4≦N-h1、M-2N-h1-h4≦N-h4が必要十分条件ですので
M-3N≦h1 ・・・(21)式 M-3N≦h4 ・・・(22)式 (14)、(21)、(22)式から M-3N≦h1≦N、M-3N≦h4≦Nよって M≦4N
また(15)、(16)式より 2N≦M
これより解の存在条件 2N≦M≦4N が導かれました。
さらに(14)〜(16)、(20)〜(22)式より題意を満たすh1,h4,k1の必要十分条件が以下のように導かれます。
MAX(M-3N,0)≦h1≦MIN(M-2N,N) ・・・(23)式 MAX(M-3N,0)≦h4≦MIN(M-2N,N) ・・・(24)式 MAX(M-2N-h1-h4,0)≦k1≦MIN(N-h1,N-h2) ・・・(25)式ただし、MAX(a,b)はa,bの大きい方を、MIN(a,b)はa,bの小さい方を表します。
以上から2N≦M≦4Nの時の題意を満たす解の種類Sを求めることができます。
ただし回転、裏返しで同型の解は1つとします。
回転裏返し同型を同一とするため
h1の対辺h3=M-2N-h1から
h1≧h4、MAX(M-3N,0)≦h1≦[ | M-2N
2 | ] (≦N) |
2N≦M≦3Nのとき、(23)〜(25)式は下記のようになります。
0≦h4≦h1≦[ | M-2N
2 | ] |
M-2N-h1-h4≦k1≦N-h1
解の種類Sは α=[ | M-2N
2 | ] と置いて |
S= | α Σ h1=0 | h1 Σ h4=0 | (3N-M+h4+1) |
これより
S= | α Σ h1=0 | {(3N-M+1)(h1+1)+ | (h1+1)h1
2 | } |
= | (3N-M+1)(α+2)(α+1)
2 | + | (α+2)(α+1)α
6 |
3N≦M≦4Nのとき、(23)〜(25)式は下記のようになります。
M-3N≦h4≦h1≦[ | M-2N
2 | ] |
M-2N-h1-h4≦k1≦N-h1
解の種類Sは α=[ | M-2N
2 | ] と置いて |
S= | α Σ h1=M-3N | h1 Σ h4=M-3N | (3N-M+h4+1) |
S= | α Σ h1=M-3N | h1-M+3N Σ h4=0 | (h4+1) |
= | α Σ h1=M-3N |
(h1-M+3N+2)(h1-M+3N+1)
2 |
= | α-M+3N Σ h1=0 | (h1+2)(h1+1)
2 |
= | (α-M+3N+3)(α-M+3N+2)(α-M+3N+1)
6 |
番兵の数 解の種類 36 29 32 65 28 56 24 21 22 6たとえば36人のケースでは、まっちゃんさんの回答では(1,2,2,3)でできる2通りが不足しています。
【解答の修正】
解の種類Sについて、h1=h3のとき、k1の異なる値に対し裏返しで同型になるものがあることが判りましたので回答を修正します。
Mが奇数のときは、M-2N(=h1+h3)が奇数となり、h1=h3とならず、
またh2≠h4であり、裏返し同型は発生しません。
なお、h1、h4の制限から回転同型が発生ないことは保証されており、
またh1=h4の場合はk2=k4のため対角線裏返しは同一であることから、2重にカウントされる心配はありません。
したがって、Mが奇数のときは上記Sの解は正しい値となります。
Mが偶数のとき、
h1=h3= | M-2N
2 | でk1に対しk4が異なる値をとれば、 |
h1= | M-2N
2 | の条件で、h4に対しk1がn個の解を持てば、 |
同型として2重にカウントされる数は[ | n
2 | ]で求められます。 |
2N≦M≦3Nのとき、0≦h4≦h1= | M-2N
2 | であり |
M-2N 2 | -h4≦k1≦ | 4N-M 2 |
3N-M+1個から | 4N-M 2 | +1個までの解を持ちます。 |
2N≦M≦3Nのとき、M-3N≦h4≦h1= | M-2N
2 | であり |
M-2N 2 | -h4≦k1≦ | 4N-M 2 |
したがってk1はh4の値により、
1個から | 4N-M 2 | +1個までの解を持ちます。 |
この各個数nに対し[ | n
2 | ]を求め総計すれば2重にカウントされる数が求まります。 |
関数F(x)を次のように定義します。(詳細は省略します。)
F(x)=[ | x
2 | ] ([ | x
2 | ]+1) ・・・ x が偶数のとき |
F(x)=([ | x
2 | ]+1)([ | x
2 | ]+1) ・・・ x が奇数のとき |
この関数を使って解の種類は以下のように求められます。
2N≦M≦3Nのとき、 S-F( | 4N-M
2 | )+F(3N-M-1) |
3N≦M≦4Nのとき、 S-F( | 4N-M
2 | ) |
◆東京都 まっちゃん さんからの解答
【問題1】
面に配置された番兵の総人数をa人、角に配置された番兵の総人数をb人とします。
一辺を11人で守っている状態にしているので、4辺を合計すると44人で守っていることになります。
ただし、角にいる番兵は二面に対して守備をしているので2人分の働きをしていることになります。
よってa+2b=44
また a+b=36より
a=28、b=8
まず角の人数配分を考えます。
すると8人の分け方は
(0、0、0、8)(0、0、1、7)(0、0、2、6) (0、1、1、6)(0、0、3、5)(0、1、2、5) (1、1、1、5)(0、0、4、4)(0、1、3、4) (0、2、2、4)(1、1、2、4)(0、2、3、3) (1、1、3、3)(2、2、2、2)回転したり、対角線に関して反転して一致するものは同一と見なすと、
(0、0、0、8)(1、1、1、5)(2、2、2、2)はそれぞれ1通り、
(0、0、1、7)(0、0、2、6)(0、1、1、6) (0、0、3、5)(0、0、4、4)(0、2、2、4) (1、1、2、4)(0、2、3、3)(1、1、3、3)はそれぞれ2通り、
(0、1、2、5)(0、1、3、4)はそれぞれ3通り
となります。
次に各々の場合についての面の人数配分について考えます。
面は両隣の角の人数が決まれば、全ての辺は11人で守っているという条件から一意に決まります。
よって合計で27通り。
【問題2】
問題1と同様に a+2b=44 および a+b=32より
a=20、b=12
角の人数配分は
(0、0、1、11)(0、0、2、10)(0、1、1、10) (0、0、3、9) (0、1、2、9) (1、1、1、9) (0、0、4、8) (0、1、3、8) (0、2、2、8) (1、1、2、8) (0、0、5、7) (0、1、4、7) (0、2、3、7) (1、1、3、7) (1、2、2、7) (0、0、6、6) (0、1、5、6) (0、2、4、6) (1、1、4、6) (1、2、3、6) (2、2、2、6) (0、2、5、5) (1、1、5、5) (1、2、4、5) (1、3、3、5) (2、2、3、5) (0、4、4、4) (1、3、4、4) (2、2、4、4) (2、3、3、4) (3、3、3、3)となり、
(1、1、1、9)(2、2、2、6) (0、4、4、4) (3、3、3、3)(0、0、1、11)(0、0、3、9) (0、0、4、8)(0、0、6、6)はそれぞれ1通り、
(0、0、2、10)(0、1、1、10)(0、2、2、8) (1、1、2、8) (0、0、5、7) (1、1、3、7) (1、2、2、7) (1、1、4、6) (0、2、5、5) (1、1、5、5) (1、3、3、5) (2、2、3、5) (1、3、4、4) (2、2、4、4) (2、3、3、4)はそれぞれ2通り、
(0、1、2、9)(0、1、3、8)(0、1、4、7) (0、2、3、7)(0、1、5、6)(0、2、4、6) (1、2、3、6)(1、2、4、5)はそれぞれ3通り
となり、合計62通り。
【問題3】
問題1と同様に a+2b=44 および a+b=28より
a=12、b=16
角の人数配分は
(0、0、5、11)(0、0、6、10)(0、1、5、10) (1、1、4、10)(0、0、7、9) (0、1、6、9) (0、2、5、9) (1、1、5、9) (0、3、4、9) (1、2、4、9) (2、2、3、9) (0、0、8、8) (0、1、7、8) (0、2、6、8) (1、1、6、8) (0、3、5、8) (1、2、5、8) (1、3、4、8) (2、2、4、8) (0、2、7、7) (1、1、7、7) (0、3、6、7) (1、2、6、7) (0、4、5、7) (1、3、5、7) (2、2、5、7) (1、4、4、7) (2、3、4、7) (3、3、3、7) (0、4、6、6) (1、3、6、6) (2、2、6、6) (0、5、5、6) (1、4、5、6) (2、3、5、6) (2、4、4、6) (3、3、4、6) (1、5、5、5) (2、4、5、5) (3、3、5、5) (3、4、4、5) (4、4、4、4)となり、
(0、0、5、11)(0、0、6、10)(0、1、5、10) (1、1、4、10)(0、0、7、9) (0、1、6、9) (0、2、5、9) (1、1、5、9) (0、3、4、9) (1、2、4、9) (2、2、3、9) (0、0、8、8) (0、1、7、8) (0、2、6、8) (1、1、6、8) (0、3、5、8) (1、2、5、8) (1、3、4、8) (2、2、4、8) (0、2、7、7) (1、1、7、7) (0、3、6、7) (1、2、6、7) (0、4、5、7) (1、3、5、7) (2、2、5、7) (0、4、6、6) (1、3、6、6) (2、2、6、6) (3、3、3、7) (1、5、5、5) (4、4、4、4)はそれぞれ1通り、
(1、4、4、7) (0、5、5、6)(2、4、4、6) (3、3、4、6) (2、4、5、5)(3、3、5、5) (3、4、4、5)はそれぞれ2通り、
(2、3、4、7)(1、4、5、6)(2、3、5、6)はそれぞれ3通り
となり、合計55通り。
【問題4】
問題1と同様に a+2b=44 および a+b=24より
a=4、b=20
角の人数配分は
(0、0、9、11)(0、1、10、10)(1、1、9、10) (0、2、9、9) (1、1、9、9) (1、2、8、9) (2、2、7、9) (1、3、8、8) (2、2、8、8) (2、4、7、7) (3、3、7、7) (3、4、6、7) (4、4、5、7) (3、5、6、6) (4、4、6、6) (4、5、5、6) (5、5、5、5)となり、
(0、0、9、11)(0、1、10、10)(1、1、9、10) (0、2、9、9) (1、1、9、9) (1、2、8、9) (2、2、7、9) (1、3、8、8) (2、2、8、8) (2、4、7、7) (3、3、7、7) (3、4、6、7) (4、4、5、7) (3、5、6、6) (4、4、6、6) (5、5、5、5)はそれぞれ1通り、
(4、5、5、6)は2通り
となり、合計18通り。
【問題5】
問題1と同様に a+2b=44 および a+b=22より
a=0、b=22
角の人数配分は
(0、0、11、11)(1、1、10、10)(2、2、9、9) (3、3、8、8) (4、4、7、7) (5、5、6、6)となり、全て1通りずつなので合計6通り。
【感想】
角の人数によって場合分けすれば面の人数は一意に決まるので便利だと思います。
問題2以降は、各辺に11人という条件から隣り合う角には合わせて11人以下しかいないということに気をつけなければいけないですね。
◆愛知県 Y.M.Ojisan さんからの解答
【全般】
4辺11人を単純に数えれば全部で44人が必要です。
これをV人<44人でカバーするには、一人で2辺をカバー可能な角の番兵をW人おいて
(V−W)+2W=44 すなわち W=44−V
でなければなりません。
4角の番兵数を順にa,b,c,d人とするとき、
辺中央の人数は 11−(a+b)等で一意に計算されるので、
辺中央人数およびcが0人以上である為には、下記およびa,b,dは非負が必要十分条件です。
W=8 です。 W-11=-3なので 自由度は大きい。
例えば a=3 b=3 d=2 とすれば c=0 であり、その他は下記です。
現在の番兵の数は人です。配置
【問題2】
W=12 で, W-11=1です。
例えば a=3 b=3 d=2 とすれば c=4 であり、その他下記です。
現在の番兵の数は人です。配置
【問題3】
W=16 で, W-11=5です。
例えば a=3 b=3 d=6 とすれば c=4 であり、その他は下記です。
現在の番兵の数は人です。配置
【問題4】
W=20 で, W-11=9です。
例えば a=3 b=7 d=6 とすれば c=4 であり、その他は下記です。
現在の番兵の数は人です。配置
【問題5】
W=22 で, W-11=11です。自由度はかなり小さくなります。
例えば a=3 b=8 d=8 とすれば c=3 であり、その他は下記です。
現在の番兵の数は人です。配置
◆ 問題へもどる
◆ 今週の問題へ