数と組合せ　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　

　当ＨＰがいつもお世話になっているＨＮ「よおすけ」さんからの出題です。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２４年７月８日付け）

　A〜Fは、1〜12の重複しない数とする。

　　A×B＝D×E　、　B×C＝E×F　、　C×D＝F×A

が成り立つとき、A〜Fの組み合わせは何通りあるか。



































（答）

　よおすけさんから解答を頂きました。（平成２４年７月９日付け）

　1〜12のうち、7と11は、例えば、1×7＝7×1や1×11＝11×1の場合でしか使えないので、

除外。Aを固定して考えると、対称や数え漏れがなければ、以下のようになります。

　(A,B,C,D,E,F)＝(1,12,2,4,3,8)、(1,12,2,3,4,6)、(1,12,4,2,6,8)、(1,12,5,2,6,10)、(1,10,4,2,5,8)、

　　　　　　　　　　(1,10,3,2,5,6)、(2,6,8,3,4,12)、(2,9,8,3,6,12)、(2,10,6,4,5,12)、(2,10,3,4,5,6)、

　　　　　　　　　　(2,12,3,6,4,9)、(3,12,6,4,9,8)、(3,10,2,6,5,4)、(3,10,4,6,5,8)、(4,10,6,8,5,12)

の１５通り。


　攻略法さんから解答を頂きました。（平成２４年７月１７日付け）

　全１８０通りを書き上げました。

（コメント）　攻略法さんに感謝！


　とんくまさんから解答を頂きました。（平成２４年７月１７日付け）

　プログラム(SQL on DB2 9.7.5)で解いてみました。SQL は、本来 Relational Data base の
アクセス言語で、一般のプログラミング言語ではありませんが、組み合わせがJOIN操作で
自然に出来るので、使ってみました。 30通り。


----------------------- Commands Entered ------------------------
WITH
all_pattern AS (
SELECT a , b , c , d , e , f
FROM (VALUES 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ) n(a)
INNER JOIN
(VALUES 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ) n(b)
ON b <> a
INNER JOIN
(VALUES 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ) n(c)
ON c <> a
AND c <> b
INNER JOIN
(VALUES 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ) n(d)
ON d <> a
AND d <> b
AND d <> c
INNER JOIN
(VALUES 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ) n(e)
ON e <> a
AND e <> b
AND e <> c
AND e <> d
AND a * b = d * e
INNER JOIN
(VALUES 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ) n(f)
ON f <> a
AND f <> b
AND f <> c
AND f <> d
AND f <> e
AND b * c = e * f
AND c * d = f * a
)
SELECT
'(' || LPAD(a , 2) || ' , '
|| LPAD(b , 2) || ' , '
|| LPAD(c , 2) || ' , '
|| LPAD(d , 2) || ' , '
|| LPAD(e , 2) || ' , '
|| LPAD(f , 2) || ' )' AS "(a , b , c , d , e , f)"
FROM all_pattern t
WHERE NOT EXISTS
(SELECT 0
FROM all_pattern s
WHERE s.a <= t.a
AND
( s.b = t.a
AND s.c = t.b
AND s.d = t.c
AND s.e = t.d
AND s.f = t.e
OR
s.c = t.a
AND s.d = t.b
AND s.e = t.c
AND s.f = t.d
AND s.a = t.e
OR
s.d = t.a
AND s.e = t.b
AND s.f = t.c
AND s.a = t.d
AND s.b = t.e
OR
s.e = t.a
AND s.f = t.b
AND s.a = t.c
AND s.b = t.d
AND s.c = t.e
OR
s.f = t.a
AND s.a = t.b
AND s.b = t.c
AND s.c = t.d
AND s.d = t.e
)
)
ORDER BY
a , b , c , d , e
;
-----------------------------------------------------------------

(a , b , c , d , e , f)
------------------------------
( 1 , 6 , 4 , 2 , 3 , 8 )
( 1 , 6 , 4 , 3 , 2 , 12 )
( 1 , 6 , 5 , 2 , 3 , 10 )
( 1 , 8 , 3 , 2 , 4 , 6 )
( 1 , 8 , 3 , 4 , 2 , 12 )
( 1 , 8 , 5 , 2 , 4 , 10 )
( 1 , 8 , 6 , 2 , 4 , 12 )
( 1 , 10 , 3 , 2 , 5 , 6 ) -- (1,10,3,2,5,6)
( 1 , 10 , 4 , 2 , 5 , 8 ) -- (1,10,4,2,5,8)
( 1 , 10 , 6 , 2 , 5 , 12 )
( 1 , 12 , 2 , 3 , 4 , 6 ) -- (1,12,2,3,4,6)
( 1 , 12 , 2 , 4 , 3 , 8 ) -- (1,12,2,4,3,8)
( 1 , 12 , 4 , 2 , 6 , 8 ) -- (1,12,4,2,6,8)
( 1 , 12 , 5 , 2 , 6 , 10 ) -- (1,12,5,2,6,10)
( 2 , 6 , 5 , 4 , 3 , 10 ) -- *(3,10,2,6,5,4)
( 2 , 6 , 8 , 3 , 4 , 12 ) -- (2,6,8,3,4,12)
( 2 , 9 , 4 , 6 , 3 , 12 )
( 2 , 9 , 8 , 3 , 6 , 12 ) -- (2,9,8,3,6,12)
( 2 , 10 , 3 , 4 , 5 , 6 ) -- (2,10,3,4,5,6)
( 2 , 10 , 6 , 4 , 5 , 12 ) -- (2,10,6,4,5,12)
( 2 , 12 , 3 , 6 , 4 , 9 ) -- (2,12,3,6,4,9)
( 2 , 12 , 4 , 3 , 8 , 6 )
( 2 , 12 , 5 , 4 , 6 , 10 )
( 2 , 12 , 6 , 3 , 8 , 9 )
( 3 , 8 , 5 , 6 , 4 , 10 )
( 3 , 8 , 9 , 4 , 6 , 12 )
( 3 , 10 , 4 , 6 , 5 , 8 ) -- (3,10,4,6,5,8)
( 3 , 12 , 6 , 4 , 9 , 8 ) -- (3,12,6,4,9,8)
( 4 , 10 , 6 , 8 , 5 , 12 ) -- (4,10,6,8,5,12)
( 4 , 12 , 5 , 8 , 6 , 10 ) 　　　　　　　　　　　　　　30 record(s) selected.


　らすかるさんからのコメントです。（平成２４年７月１７日付け）

　90通りとか、30通りとかいろんな答えが出ていますが、対称解を削除したりしているようで
すね。しかし、この問題ではA〜Fはすべて区別されますので、正解は180通りだと思います。


　とんくまさんからのコメントです。（平成２４年７月１７日付け）

　出題者の「よおすけ」さんの回答（不十分だと思いますが）を見ると、巡回置換は除くよう
です。全部で180通り。巡回置換を除くと30通りでしょう。


　よおすけさんからのコメントです。（平成２４年７月１７日付け）

　攻略法さん、とんくまさん、らすかるさん、解答ありがとうございます。自分の解答はどうやら、
A〜Fの「解の集合」を全て書き上げたものだったようです。この問題は、5年前に当時某私立
の中高一貫校の生徒だった男性の方が作られた問題で、本人によると、小学生でもできると
ありました。(比を使えば・・・)


　攻略法さんからのコメントです。（平成２４年７月１８日付け）

　RDB的に解釈してみました。

九九表を作成しておく。行および列で、重複しないように3つずつ選んで、3×3の表をつくる。
p,q,r,kp,kq,krは重複しない1から12までの整数として、

　　 kp　kq　kr
　p　- 　○　△
　q　○　- 　□
　r　△　□　-

数値が対称（対称行列）となるものが、題意を満たす。

例　p,q,rを1,3,4とすると、k=2のとき、kp,kq,krは2,6,8
　　　　　　↓　　　　　　　↓　　　↓
　→ 1:　1　 2　 3　 4　 5　 6 　7　 8　 9　10　11　12
　　 2:　2　 4　 6　 8　10　12　14　16　18　20　22　24
　→ 3:　3　 6　 9　12　15　18　21　24　27　30　33　36
　→ 4:　4　 8　12　16　20　24　28　32　36　40　44　48
　　 5:　5　10　15　20　25　30　35　40　45　50　55　60
　　 6:　6　12　18　24　30　36　42　48　54　60　66　72
　　 7:　7　14　21　28　35　42　49　56　63　70　77　84
　　 8:　8　16　24　32　40　48　56　64　72　80　88　96
　　 9:　9　18　27　36　45　54　63　72　81　90　99 108
　　10: 10　20　30　40　50　60　70　80　90 100 110 120
　　11: 11　22　33　44　55　66　77　88　99 110 121 132
　　12: 12　24　36　48　60　72　84　96 108 120 132 144

A,B,C,D,E,Fの配置は、

　　D　　F　　B
A　 - 　F*A　A*B
C　C*D　 -　 B*C
E　D*E　E*F　 -

　　D　　B　　F
A　 - 　A*B　F*A
E　D*E　 -　 E*F
C　C*D　B*C　 -

　　B　　D　　F
E　 - 　D*E　E*F
A　A*B　 -　 F*A
C　B*C　C*D　 -

　　B　　F　　D
E　 - 　E*F　D*E
C　B*C　 -　 C*D
A　A*B　F*A　 -

　　F　　D　　B
C　 - 　C*D　B*C
A　F*A　 -　 A*B
E　E*F　D*E　 -

　　F　　B　　D
C　 - 　B*C　C*D
E　E*F　 -　 D*E
A　F*A　A*B　 -

の　3!=6通り。

　p,q,rの選び方は、k=4/3,3/2,2,3,4として、とんくまさんが提示されたように30通り。

よって、全部で30*6=180通り。(A,B,C,D,E,F)では、(A,C,E)=k(D,F,B)となる。


　ＧＡＩ さんからのコメントです。（平成２４年７月２０日付け）

　条件１〜１２の数を使うを変更して、１〜ｎ の数字での条件を満たす組合せの数 S(ｎ) を
計算したら、

S(7)=0　　、S(8)=12　　、S(9)=12　　、S(10)=60　　、S(11)=60　　、S(12)=180

S(13)=180　　、S(14)=324　　、S(15)=492　　、S(16)=672　　、S(17)=672

S(18)=1104　　、S(19)=1104　　、S(20)=1656　　、S(21)=2040　　、・・・・・・・・

と変化していく。（この数を確認して下さい。）

　さて、n=14、15、20 辺りの原因はなんだろう？


　らすかるさんからのコメントです。（平成２４年７月２０日付け）

　S(ｎ) について確認しました。n≧1１では、「nは素数」⇔「S(n)=S(n-1)」 となるようですね。

S(6)=0　　、S(7)=0　　、S(8)=12　　、S(9)=12　　、S(10)=60　　、S(11)=60　　、S(12)=180
S(13)=180　　、S(14)=324　　、S(15)=492　　、S(16)=672　　、S(17)=672　　、S(18)=1104
S(19)=1104　　、S(20)=1656　　、S(21)=2040　　、S(22)=2520　　、S(23)=2520
S(24)=3804　　、S(25)=3948　　、S(26)=4668　　、S(27)=5220　　、S(28)=6492
S(29)=6492　　、S(30)=8916　　、S(31)=8916　　、S(32)=10416　　、S(33)=11544
S(34)=12888　　、S(35)=13992　　、S(36)=17376　　、S(37)=17376　　、S(38)=19104
S(39)=20736　　、S(40)=24684　　、S(41)=24684　　、S(42)=29748　　、S(43)=29748
S(44)=33300　　、S(45)=36900　　、S(46)=39540　　、S(47)=39540　　、S(48)=46824
S(49)=47544　　、S(50)=52296　　、S(51)=55248　　、S(52)=60360　　、S(53)=60360
S(54)=68328　　、S(55)=71112　　、S(56)=79044　　、S(57)=82788　　、S(58)=87156
S(59)=87156　　、S(60)=102132　　、S(61)=102132　　、S(62)=107172　　、S(63)=114300
S(64)=122496　　、S(65)=126432　　、S(66)=139440　　、S(67)=139440　　、S(68)=148560
S(69)=154200　　、S(70)=168048　　、S(71)=168048　　、S(72)=187788　　、S(73)=187788
S(74)=195132　　、S(75)=206028　　、S(76)=217596　　、S(77)=222564　　、S(78)=240900
S(79)=240900　　、S(80)=261144　　、S(81)=269904　　、S(82)=279024　　、S(83)=279024
S(84)=308520　　、S(85)=315288　　、S(86)=325368　　、S(87)=334560　　、S(88)=354564
S(89)=354564　　、S(90)=388380　　、S(91)=395220　　、S(92)=412524　　、S(93)=423084
S(94)=435228　　、S(95)=443724　　、S(96)=479736　　、S(97)=479736　　、S(98)=498744
S(99)=516432　　、S(100)=546000　　、S(101)=546000　　、S(102)=577752
S(103)=577752　　、S(104)=605796　　、S(105)=636924　　、S(106)=652524
S(107)=652524　　、S(108)=698580　　、S(109)=698580


　ＧＡＩ さんからのコメントです。（平成２４年７月２０日付け）

　１〜ｎ の数字を使って、異なる ａ、ｂ、ｃ、ｄ、ｅ、ｆ で、

　　ａｂｃ=ｄｅｆ　、ｂｃｄ=ｅｆａ　、ｃｄｅ=ｆａｂ

の条件が成立することが可能かを調べています。

　ｎ＝２６まで計算しましたが（２６あたりですごく時間がかかる。）存在しない。どなたかどこ
までｎを広げたら存在できるのか効率の良いプログラムで調べて頂けませんか？もし、存
在が不可能ならそれはなぜ？


　らすかるさんからのコメントです。（平成２４年７月２０日付け）

　第１式の両辺にｄを掛けると、　ａｂｃｄ=ｄ²ｅｆ

　第２式の両辺にaを掛けると、　ａｂｃｄ=ａ²ｅｆ

　よって、ａ=ｄ となり矛盾。すなわち、任意のｎについて、条件を満たすものは存在しない。