No. 18≫ No.19 ≫No. 20
いはら
2010/06/07 17:43
今までのヒントを整理します。
回転に対する不変配置の個数をP,反転に対する不変配置の個数をQとすると、
P=Σφ(s)C(n/s,k/s) [sはn,kの公約数]
Q=n×C([(n-r)/2],(k-r)/2)
と計算できることが分かりました。
(rはkを2で割ったときの余りです)
首飾りの総数をαとすると、α=(P+Q)/2n です。
少し進めます。
村人2が正直者だと仮定します。
α＜４です。
α≠1ですので、αは2または3です。
α=2のとき、(P+Q)/2n=2より、P+Q=4nです。
α=3のとき、(P+Q)/2n=3より、P+Q=6nです。
Q=n×C([(n-r)/2],(k-r)/2)
ですのでQはnの整数倍であり、Pもnの整数倍であることが分かります。
P,Qは正の整数ですので、Qはn,2n,3n,4n,5nのいずれかです。
i=[(n-r)/2],j=(k-r)/2とすると、Q=n×C(i,j)ですので、
C(i,j)の値は、1,2,3,4,5のいずれかとなります。
k≧2ですので、j≧1です。
C(i,j)=i!/j!(i-j)!=i×(i-1)/j×(i-2)/(j-1)×･･･×(i-j+1)/2
=i×Π(i-w)/(j-w+1) [w=1,2,･･･,j-1]
i=jのとき、n=kまたはn=k-1となりますので、α=1となり不適です。
よってi＞jであり、i-j≧1です。
すると、(i-w)-(j-w+1)=i-j-1≧0であり、0＜j-w+1≦i-wですので、
(i-w)/(j-w+1)≧1であり、C(i,j)≧iが分かります。
C(i,j)≦5なので、i≦5です。
村人は村長を含めて6人以上いますので、i≧2です。
よって、(i,j)は(2,1),(3,1),(3,2),(4,1),(4,3),(5,1),(5,4)のいずれかです。
(i,j)=(2,1)の場合
nが偶数,kが偶数⇒(n,k)=(4,2)⇒n＜6で不適
nが偶数,kが奇数⇒(n,k)=(6,3)⇒α=3
nが奇数,kが偶数⇒(n,k)=(5,2)⇒n＜6で不適
nが奇数,kが奇数⇒(n,k)=(5,3)⇒n＜6で不適
(i,j)=(3,1)の場合
nが偶数,kが偶数⇒(n,k)=(6,2)⇒α=3
nが偶数,kが奇数⇒(n,k)=(8,3)⇒α=5で不適
nが奇数,kが偶数⇒(n,k)=(7,2)⇒α=3
nが奇数,kが奇数⇒(n,k)=(7,3)⇒α=4で不適
(i,j)=(3,2)の場合
nが偶数,kが偶数⇒(n,k)=(6,4)⇒α=3
nが偶数,kが奇数⇒(n,k)=(8,5)⇒α=5で不適
nが奇数,kが偶数⇒(n,k)=(7,4)⇒α=4で不適
nが奇数,kが奇数⇒(n,k)=(7,5)⇒α=3
(i,j)=(4,1)の場合
nが偶数,kが偶数⇒(n,k)=(8,2)⇒α=4で不適
nが偶数,kが奇数⇒(n,k)=(10,3)⇒α=8で不適
nが奇数,kが偶数⇒(n,k)=(9,2)⇒α=4で不適
nが奇数,kが奇数⇒(n,k)=(9,3)⇒α=7で不適
(i,j)=(4,3)の場合
nが偶数,kが偶数⇒(n,k)=(8,6)⇒α=4で不適
nが偶数,kが奇数⇒(n,k)=(10,7)⇒α=8で不適
nが奇数,kが偶数⇒(n,k)=(9,6)⇒α=7で不適
nが奇数,kが奇数⇒(n,k)=(9,7)⇒α=4で不適
(i,j)=(5,1)の場合
nが偶数,kが偶数⇒(n,k)=(10,2)⇒α=5で不適
nが偶数,kが奇数⇒(n,k)=(12,3)⇒α=12で不適
nが奇数,kが偶数⇒(n,k)=(11,2)⇒α=5で不適
nが奇数,kが奇数⇒(n,k)=(11,3)⇒α=10で不適
(i,j)=(5,4)の場合
nが偶数,kが偶数⇒(n,k)=(10,8)⇒α=5で不適
nが偶数,kが奇数⇒(n,k)=(12,9)⇒α=12で不適
nが奇数,kが偶数⇒(n,k)=(11,8)⇒α=10で不適
nが奇数,kが奇数⇒(n,k)=(11,9)⇒α=5で不適
以上より、(n,k)=(6,2),(6,3),(6,4),(7,2),(7,5)のどれかで、α=3
嘘つき、正直者の人数の組み合わせは(2,4),(4,2),(3,3),(2,5),(5,2)
この組み合わせについて条件を満たすかどうか確かめましょう。
村長は正直者、
α=3は素数なので、村人1は嘘つき、
仮定より、村人2は正直者、
α-1=2は3の倍数でないので、村人4は嘘つき、
嘘つき、正直者どちらも6人となることはないので、村人5は正直者
村人4が嘘つきなので、正直者と嘘つきはどちらも4人ではありません。
よって、(2,4),(4,2)は不適。
村人5の発言より嘘つきは4人以下なので、(5,2)は不適。
残るは(3,3),(2,5)のみ。
(3,3)の場合、正直者の人数が3の倍数なので村人3は正直者。
すると、正直者が4人となり矛盾するので不適。
(2,5)の場合、正直者の人数は3の倍数でないので村人3は嘘つき。
すると、嘘つきが3人となり矛盾するので不適。
結局、条件を満たす場合はないことが分かり、仮定は誤りであったことが判明。
よって、村人2は嘘つき。
すると、村人2の発言から村人1が嘘つきであることが分かります。
回転に対する不変配置の個数をP,反転に対する不変配置の個数をQとすると、
P=Σφ(s)C(n/s,k/s) [sはn,kの公約数]
Q=n×C([(n-r)/2],(k-r)/2)
と計算できることが分かりました。
(rはkを2で割ったときの余りです)
首飾りの総数をαとすると、α=(P+Q)/2n です。
少し進めます。
村人2が正直者だと仮定します。
α＜４です。
α≠1ですので、αは2または3です。
α=2のとき、(P+Q)/2n=2より、P+Q=4nです。
α=3のとき、(P+Q)/2n=3より、P+Q=6nです。
Q=n×C([(n-r)/2],(k-r)/2)
ですのでQはnの整数倍であり、Pもnの整数倍であることが分かります。
P,Qは正の整数ですので、Qはn,2n,3n,4n,5nのいずれかです。
i=[(n-r)/2],j=(k-r)/2とすると、Q=n×C(i,j)ですので、
C(i,j)の値は、1,2,3,4,5のいずれかとなります。
k≧2ですので、j≧1です。
C(i,j)=i!/j!(i-j)!=i×(i-1)/j×(i-2)/(j-1)×･･･×(i-j+1)/2
=i×Π(i-w)/(j-w+1) [w=1,2,･･･,j-1]
i=jのとき、n=kまたはn=k-1となりますので、α=1となり不適です。
よってi＞jであり、i-j≧1です。
すると、(i-w)-(j-w+1)=i-j-1≧0であり、0＜j-w+1≦i-wですので、
(i-w)/(j-w+1)≧1であり、C(i,j)≧iが分かります。
C(i,j)≦5なので、i≦5です。
村人は村長を含めて6人以上いますので、i≧2です。
よって、(i,j)は(2,1),(3,1),(3,2),(4,1),(4,3),(5,1),(5,4)のいずれかです。
(i,j)=(2,1)の場合
nが偶数,kが偶数⇒(n,k)=(4,2)⇒n＜6で不適
nが偶数,kが奇数⇒(n,k)=(6,3)⇒α=3
nが奇数,kが偶数⇒(n,k)=(5,2)⇒n＜6で不適
nが奇数,kが奇数⇒(n,k)=(5,3)⇒n＜6で不適
(i,j)=(3,1)の場合
nが偶数,kが偶数⇒(n,k)=(6,2)⇒α=3
nが偶数,kが奇数⇒(n,k)=(8,3)⇒α=5で不適
nが奇数,kが偶数⇒(n,k)=(7,2)⇒α=3
nが奇数,kが奇数⇒(n,k)=(7,3)⇒α=4で不適
(i,j)=(3,2)の場合
nが偶数,kが偶数⇒(n,k)=(6,4)⇒α=3
nが偶数,kが奇数⇒(n,k)=(8,5)⇒α=5で不適
nが奇数,kが偶数⇒(n,k)=(7,4)⇒α=4で不適
nが奇数,kが奇数⇒(n,k)=(7,5)⇒α=3
(i,j)=(4,1)の場合
nが偶数,kが偶数⇒(n,k)=(8,2)⇒α=4で不適
nが偶数,kが奇数⇒(n,k)=(10,3)⇒α=8で不適
nが奇数,kが偶数⇒(n,k)=(9,2)⇒α=4で不適
nが奇数,kが奇数⇒(n,k)=(9,3)⇒α=7で不適
(i,j)=(4,3)の場合
nが偶数,kが偶数⇒(n,k)=(8,6)⇒α=4で不適
nが偶数,kが奇数⇒(n,k)=(10,7)⇒α=8で不適
nが奇数,kが偶数⇒(n,k)=(9,6)⇒α=7で不適
nが奇数,kが奇数⇒(n,k)=(9,7)⇒α=4で不適
(i,j)=(5,1)の場合
nが偶数,kが偶数⇒(n,k)=(10,2)⇒α=5で不適
nが偶数,kが奇数⇒(n,k)=(12,3)⇒α=12で不適
nが奇数,kが偶数⇒(n,k)=(11,2)⇒α=5で不適
nが奇数,kが奇数⇒(n,k)=(11,3)⇒α=10で不適
(i,j)=(5,4)の場合
nが偶数,kが偶数⇒(n,k)=(10,8)⇒α=5で不適
nが偶数,kが奇数⇒(n,k)=(12,9)⇒α=12で不適
nが奇数,kが偶数⇒(n,k)=(11,8)⇒α=10で不適
nが奇数,kが奇数⇒(n,k)=(11,9)⇒α=5で不適
以上より、(n,k)=(6,2),(6,3),(6,4),(7,2),(7,5)のどれかで、α=3
嘘つき、正直者の人数の組み合わせは(2,4),(4,2),(3,3),(2,5),(5,2)
この組み合わせについて条件を満たすかどうか確かめましょう。
村長は正直者、
α=3は素数なので、村人1は嘘つき、
仮定より、村人2は正直者、
α-1=2は3の倍数でないので、村人4は嘘つき、
嘘つき、正直者どちらも6人となることはないので、村人5は正直者
村人4が嘘つきなので、正直者と嘘つきはどちらも4人ではありません。
よって、(2,4),(4,2)は不適。
村人5の発言より嘘つきは4人以下なので、(5,2)は不適。
残るは(3,3),(2,5)のみ。
(3,3)の場合、正直者の人数が3の倍数なので村人3は正直者。
すると、正直者が4人となり矛盾するので不適。
(2,5)の場合、正直者の人数は3の倍数でないので村人3は嘘つき。
すると、嘘つきが3人となり矛盾するので不適。
結局、条件を満たす場合はないことが分かり、仮定は誤りであったことが判明。
よって、村人2は嘘つき。
すると、村人2の発言から村人1が嘘つきであることが分かります。