数学の部屋へもどる
◆広島県 清川 育男 さんからの解答
【問題１】
○，○，×，○，○，
×，○，×，○，×，
×，×，◎，×，×，
×，○，×，○，×，
○，○，×，○，○
【問題２】
盤を固定したものとする。
４５３４８通り。
結果はこちらです。
◆千葉県 悠々 さんからの解答
【問題１】
例えば
●パターン１
交差する縦横あるいは斜めの列がすべて０で交点に２がある場合
01100 01100 21111
10100 01100 00011
11211 11110 00011
00101 00002 00101
00110 11110 01010
●パターン２
２がある縦、横あるいは斜めの列は２以外はすべて０の場合
２と同じ列の０のところに２を移しても解答（５通り）10001 11002 11000
11110 11000 11000
20000 10010 10010
11110 01100 10111
10001 11110 20101
●パターン３
上記以外の場合
他の０のところに２を移しても解答（１３通り）20110
11000
00101
11101
00110
【問題２】
45348通り。
スマートな方法があるか、わからなかったのでプログラムを作成しました。
◆アルゴリズム概要
寂しがりのひよこの一組を除いて、１２匹で条件２を満足するパターンを数える。
このとき列の数は０でも良いとする。
（最終的に０のところに寂しがりのひよこ一組を置けばすべての条件に合う。）
こうすると１列は以下の１６通りに限られるので、これを５個づつ取り出して、１６の５乗の組み合わせパターンを全てチェックする。11000
10100
10010
10001
01100
01010
01001
00110
00101
00011
11110
11101
11011
10111
01111
00000
その結果
●交差する斜めの列がすべて０
（問題１の解答例パターン１の左） ４個
●交差する縦横の列がすべて０
（問題１の解答例パターン１の中） ２９２個
●交差する縦と斜めあるいは横と斜めの列がすべて０
（問題１の解答例パターン１の右） １１２個
●横の列がすべて０
（問題１の解答例パターン２の左） １０４０個
●縦の列がすべて０
（問題１の解答例パターン２の中） １０４０個
●斜めの列がすべて０
（問題１の解答例パターン２の右） ３３０個
●上記以外
（条件１，２を満たしている・問題１の解答例パターン３） ２５３０個
よって
4+292+112+(1040+1040+330)*5+2530*13=45348
◆東京都 明 さんからの解答
【問題１】
○，○，○，×，○，
×，◎，○，×，○，
×，○，×，○，×，
×，×，○，○，×，
○，×，○，×，×
方法
各行、各列に2匹ずつ配置されるように一筆書きの要領で10匹を配置。
斜めが偶数になるように、残り4匹を適当な矩形の4隅に配置する。
このとき1箇所のみ2匹になるように調整する。
【問題２】
下記の方針で数えあげる。
方針
(1)縦、横共に0匹の列がない場合
CASE1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 1
1 0 0 0 1
0 0 1 1 0
CASE2
0 1 1 1 1
1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 0 0 0 1
(2)1列のみ0匹の列がある場合
（後でさびしがりやを0匹の列へ配置）
CASE3
0 1 1 0 0
0 1 1 0 0
0 1 1 0 0
0 1 1 1 1
0 0 0 1 1
CASE4
0 1 1 1 1
0 1 1 0 0
0 1 1 0 0
0 1 0 1 0
0 0 1 0 1
注、CASE3,4は縦、横を入れ替えた場合がある。（数え上げの2倍）
(3)縦、横の各1列が0匹の場合
（さびしがりやを0匹の列の交点へ配置）
CASE5
1 1 1 1 0
1 1 1 1 0
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
(4)縦、横列いずれか2列が0匹となる場合は、各列偶数の条件では最大10匹しか配置できないので対象外。
2.以上の基本配置の入れ替えで、斜めが偶数になるケースを数え上げる。
後記プログラム（10進BASIC）で数えあげました。
（プログラムが長すぎるため、バグがないか自信がありません。正しいとすれば以下の流れとなります。）
ただし
共に0：2つの斜めの列にひよこがいない。
一方0：1つの斜めの列に偶数匹のひよこ。
もう一方の列にはひよこがいない。
両偶数：2つの斜めの列とも偶数匹のひよこ。
奇数：いずれか、もしくは共に奇数匹のひよこ。
CASE1
総計 : 3600
共に0 : 0
一方0 : 112
両偶数: 928
奇数 : 2560
CASE2
総計 : 600
共に0 : 4
一方0 : 50
両偶数: 170
奇数 : 376
CASE3
総計 : 600
共に0 : 0
一方0 : 0
両偶数: 88
奇数 : 512
CASE4
総計 : 3600
共に0 : 0
一方0 : 56
両偶数: 952
奇数 : 2592
CASE5
総計 : 900
共に0 : 0
一方0 : 0
両偶数: 292
奇数 : 608
3.以上に、条件を満たすように「さびしがりやのひよこ」を配置すれば、総数は以下のようになる。
CASE1 112×5 ＋ 928×13 CASE2 4×1 ＋ 50×5 ＋ 170×13 CASE3 88×5×2 CASE4 56×1×2 ＋ 952×5×2 CASE5 292×1 総数：25892なお、蛇足ですが、下記配列は対角線だけでなく、すべての斜め列も偶数匹となっています。
（CASE2）
×，×，○，○，×，
×，×，○，×，○，
○，○，◎，○，○，
○，×，○，×，×，
×，○，○，×，×
【問題２】数え上げプログラム（DATAはCASE1の場合）
---------------------------------
DECLARE EXTERNAL SUB ZYUN
DIM A(5,5)
DIM B(5,5)
DIM C(5,5)
DIM X(5)
DIM XB(5)
DIM XC(5)
DIM XP(5)
DIM Y(5)
DIM YB(5)
DIM YC(5)
DIM YP(5)
LET Z0=0 !斜め共に0の計数
LET Z1=0 !斜め一方0の計数
LET Z2=0 !斜め共に偶数の計数
LET Z3=0 !いずれか奇数の計数
LET FIN=0
LET EX=0
LET TOTAL=0
!基本配列の定義
SUB SEISEI
DATA 1,1,1,1,0
DATA 1,1,0,0,0
DATA 1,0,0,0,1
DATA 1,0,0,0,1
DATA 0,0,1,1,0
MAT READ A
END SUB
!縦列(X)、横列(Y)の種別の定義
SUB AXDEF
DATA 1,2,3,3,4
DATA 1,2,3,3,4
MAT READ X
MAT READ Y
END SUB
CALL SEISEI
FOR K=1 TO 5
FOR J=1 TO 5
PRINT A(J,K);
NEXT J
PRINT
NEXT K
CALL AXDEF
MAT XB=X
MAT YB=Y
DO
LET TOTAL=TOTAL+1
CALL HAIRETU
CALL NARABIKAE
CALL CHECK
IF FIN=1 THEN
PRINT "総計 : ";TOTAL
PRINT
PRINT "共に0 : ";Z0
PRINT "一方0 : ";Z1
PRINT "両偶数: ";Z2
PRINT "奇数 : ";Z3
EXIT DO
END IF
LOOP
!配列の並び替え
SUB NARABIKAE
IF FIN=0 THEN
FOR J=1 TO 5
FOR K=1 TO 5
LET C(J,K)=A(XP(J),YP(K))
NEXT K
NEXT J
END IF
CALL ZYUN(5,EX,X)
IF EX=1 THEN EXIT SUB
MAT X=XB
CALL ZYUN(5,EX,Y)
IF EX=1 THEN EXIT SUB
LET FIN=1
END SUB
!並び替え後の配列
SUB HAIRETU
MAT XC=XB
FOR J=1 TO 5
FOR K=1 TO 5
IF XC(K)=X(J) THEN
LET XP(J)=K
LET XC(K)=0
EXIT FOR
END IF
NEXT K
NEXT J
MAT YC=YB
FOR J=1 TO 5
FOR K=1 TO 5
IF YC(K)=Y(J) THEN
LET YP(J)=K
LET YC(K)=0
EXIT FOR
END IF
NEXT K
NEXT J
END SUB
!斜めチェック
SUB CHECK
LET P1=0
LET P2=0
FOR J=1 TO 5
LET P1=P1+C(J,J)
LET P2=P2+C(J,6-J)
NEXT J
IF MOD(P1,2)=0 AND MOD(P2,2)=0 THEN
IF P1>1 AND P2>1 THEN
LET Z2=Z2+1
ELSE
IF P1=0 AND P2=0 THEN
LET Z0=Z0+1
ELSE
IF P1=0 OR P2=0 THEN LET Z1=Z1+1
END IF
END IF
ELSE
LET Z3=Z3+1
END IF
END SUB
END
!順列の変更
EXTERNAL SUB ZYUN(K,EX,N())
DECLARE EXTERNAL SUB SEIRETU
LET EX=0
LET J=1
DO
IF J>=K THEN EXIT DO
IF N(K-J)<N(K-J+1) THEN
CALL SEIRETU(J,K,N)
LET L=1
DO
IF N(K-J)>=N(K-J+L) THEN
LET L=L+1
ELSE
LET B=N(K-J)
LET N(K-J)=N(K-J+L)
LET N(K-J+L)=B
LET EX=1
EXIT DO
END IF
LOOP
EXIT DO
ELSE
LET J=J+1
END IF
LOOP
END SUB
!配列の整列
EXTERNAL SUB SEIRETU(G,K,N())
LET D=G
DO
LET J=K-D+1
IF J>=K THEN EXIT DO
LET B=J
DO WHILE J<K
LET J=J+1
IF N(B)>N(J) THEN
LET T=N(B)
LET N(B)=N(J)
LET N(J)=T
END IF
LOOP
LET D=D-1
LOOP
END SUB
ちなみに種別の定義DATAは以下のとおり。
CASE1 X DATA 1,2,3,3,4
Y DATA 1,2,3,3,4
CASE2 X DATA 1,2,2,2,2
Y DATA 1,2,3,4,5
CASE3 X DATA 1,2,2,3,3
Y DATA 1,1,1,2,3
CASE4 X DATA 1,2,3,4,5
Y DATA 1,2,2,3,3
CASE5 X DATA 1,1,2,2,3
Y DATA 1,1,2,2,3
基本配列のDATAはプログラム上は縦列(Y)先行に注意。
◆回答の訂正 その１
『第165回』問題の件、下記のように総当り方法にプログラムを変更して確認したところ、４５３４８通りとなりました。
こちらのプログラムは実行に時間がかかりますが、紛れがありません。
実行に3時間半ぐらいかかります。
----------------------------------------------
結果
総計 : 67603900
0列あり : 2121304
奇数列あり : 65437248
合格 : 45348
注、
５×５のマスに１２匹のひよこと２匹のさびしがりやのひよこを配置するすべての場合を総当りでチェックした結果です。
「0列あり」、「奇数列あり」は、それぞれプログラムのチェックで、該当の不適合が先に検出された場合の数を示しており、該当のエラーのみが存在するという意味ではありません。
----------------------------------------------
DECLARE EXTERNAL SUB ZYUN
DIM C(5,5)
DIM N(25)
LET Z0=0 !0の列あり
LET Z1=0 !奇数の列あり
LET Z2=0 !全列偶数
LET FIN=0
LET EX=0
LET TOTAL=0
CALL SEISEI
DO
LET TOTAL=TOTAL+1
CALL NARABIKAE
CALL CHECK
IF FIN=1 THEN
PRINT "総計 : ";TOTAL
PRINT
PRINT "0列あり : ";Z0
PRINT "奇数列あり : ";Z1
PRINT "合格 : ";Z2
STOP
END IF
LOOP
!基本配列種別の定義
SUB SEISEI
DATA 1,1,1,1,1,1,1,1,1,1,1,1
DATA 2,2,2,2,2,2,2,2,2,2,2,2
DATA 3
MAT READ N
END SUB
!配列の並び替え
SUB NARABIKAE
LET L=1
FOR J=1 TO 5
FOR K=1 TO 5
LET C(J,K)=N(L)-1
LET L=L+1
NEXT K
NEXT J
CALL ZYUN(25,EX,N)
IF EX=1 THEN EXIT SUB
LET FIN=1
END SUB
!各列の偶奇性チェック
SUB CHECK
FOR J=1 TO 5 !縦列のチェック
LET P=0
FOR K=1 TO 5
LET P=P+C(J,K)
NEXT K
IF P=0 THEN
LET Z0=Z0+1
EXIT SUB
END IF
IF MOD(P,2)=1 THEN
LET Z1=Z1+1
EXIT SUB
END IF
NEXT J
FOR J=1 TO 5 !横列のチェック
LET P=0
FOR K=1 TO 5
LET P=P+C(K,J)
NEXT K
IF P=0 THEN
LET Z0=Z0+1
EXIT SUB
END IF
IF MOD(P,2)=1 THEN
LET Z1=Z1+1
EXIT SUB
END IF
NEXT J
LET P1=0 !斜列のチェック
LET P2=0
FOR J=1 TO 5
LET P1=P1+C(J,J)
LET P2=P2+C(J,6-J)
NEXT J
IF P1=0 OR P2=0 THEN
LET Z0=Z0+1
EXIT SUB
END IF
IF MOD(P1,2)=1 OR MOD(P2,2)=1 THEN
LET Z1=Z1+1
EXIT SUB
END IF
LET Z2=Z2+1
END SUB
END
!順列の変更
EXTERNAL SUB ZYUN(K,EX,N())
DECLARE EXTERNAL SUB SEIRETU
LET EX=0
LET J=1
DO
IF J>=K THEN EXIT DO
IF N(K-J)<N(K-J+1) THEN
CALL SEIRETU(J,K,N)
LET L=1
DO
IF N(K-J)>=N(K-J+L) THEN
LET L=L+1
ELSE
LET B=N(K-J)
LET N(K-J)=N(K-J+L)
LET N(K-J+L)=B
LET EX=1
EXIT DO
END IF
LOOP
EXIT DO
ELSE
LET J=J+1
END IF
LOOP
END SUB
!配列の整列
EXTERNAL SUB SEIRETU(G,K,N())
LET D=G
DO
LET J=K-D+1
IF J>=K THEN EXIT DO
LET B=J
DO WHILE J<K
LET J=J+1
IF N(B)>N(J) THEN
LET T=N(B)
LET N(B)=N(J)
LET N(J)=T
END IF
LOOP
LET D=D-1
LOOP
END SUB
◆回答の訂正 その２
『第165回』の答え間違いの原因がわかりましたのでご報告します。
基本配置がもうひとつ不足していたのが原因です。
CASE1の近親にもうひとつ下記基本配置がありました。CASE1-2
1 1 1 1 0
1 1 0 0 0
1 0 1 0 0
1 0 0 0 1
0 0 0 1 1
種別定義データは
X DATA 1,2,3,4,5
Y DATA 1,2,2,3,4
（Ｙの2,3列目はＸ側の入れ替えで場合を尽くせるので同じ値として入れ替えを発生させない。）
プログラムの実行結果は下記のとおりになります。
総計 : 7200
共に0 : 0
一方0 : 168
両偶数: 1432
奇数 : 5600
さびしがりやを加えた場合の数は
168×5 + 1432×13 ＝19456
これを前回回答の 25892に加えると目出度く45348になります。
一番の大口が抜けていたことになります。
【おまけ】
logの式をMaclaurin展開すると
| X ＝ | 1 102002・(8+17) + 1996・(12+23) |
＝ | 1 10119910 |
として
| -X- | X2 2 |
- | X3 3 |
- | X4 4 |
- | X5 5 |
- | X6 6 |
- | X7 7 |
- | X8 8 |
- | X9 9 |
-・・・ |
9項以降は、小数点以下1000000桁より小さくなるため8項までを考えればよい。
3,6,7項以外は係数が割り切れてしまうため、1000000桁目へ影響しない。
3,6項は両方で6項の桁以下.99999・・となるため1000000桁目へ影響しない。
| 結局 | X7 7 |
の項のみの影響を考えればよい。 |
| 7項目は | 1 7 |
＝0.142857142857・・と |
1000000＝839370+6×26771+4
よって4桁目の「八」が1000000桁目となります。
末広がりということでしょうか。
◆ 問題へもどる
◆ 今週の問題へ