このクイズのヒント
-
ヒント知らないよ
このクイズの参加者(9人)
広告

広告
広告
広告
クイズ大陸関連書籍
![]() ![]() |
![]() |
![]() |
![]()
難易度:★★★★★
![]() ![]() マリーベル博士がある村を訪れたときのこと。
その村に住むのはいつも嘘をつく嘘つきか正直者のどちらか。 最初に訪れた家はたまたま村長の家で、しばらく話すうちに村長は正直者であることが判明。 村長「この村では毎年特別な首飾りを作って神様にお供えしております。 いわゆるルビーとダイアモンドに紐を通して輪にしたものです。 我々は赤石、白石と呼んでおりますが。 赤石の個数はこの村に住む嘘つきの人数と同じ、 白石の個数はこの村に住む正直者の人数と同じです。 但し、過去にお供えした首飾りと同じものを供えると村が滅びるという言い伝えがありましてな、 毎年気をつけてお供えしております」 博士「毎年作っているのであれば、同じものになることはないのでは?」 村長「おっと失礼。誤解を招く言い方でしたな。 赤石と白石の配置が同じ首飾りは同じものとみなすのです。 回転したり裏返しにしたりして同じ配置になるものも同じとします」 博士「なるほど。そうなると首飾りをお供えできる回数には限りがありますね」 村長「そうなのです。 実際、どうしても異なる首飾りを作ることができない年がありまして、 そのときには急遽他の村から嫁を迎えたそうです。 今年は去年の首飾りをばらして組み替えるだけでよいですから楽なものです」 博士「その首飾りを見せていただきたいのですが」 村長「いくら博士の頼みでもそればかりは」 博士「そこをなんとか」 村長「それでは賢者の試しを受けていただくしかありませんな。 自らの英知を証明し賢者と認められればこの村の秘儀に参加する資格が与えられます。 但し、この試練に失敗したときは、あなたの首をいただきます」 博士「その試練とは?」 村長「現在の村人の構成で作成できる首飾りの総数を求めることです。 過去に作ったことがあるかどうかは無視して下さい。 例えば、嘘つき2人、正直者2人の場合は、 赤赤白白と並んでいるものと赤白赤白と並んでいるものの2つになります。 もちろん、論理的に総数を決定するのに十分な手がかりは与えられますが、 過去にこの試練に成功した者はおりません」 博士「では私が最初の一人になってみせましょう」 村長「分かりました。それでは明朝、村の広場においで下さい。 そこで村人達からいくつかの手がかりが伝えられます。 手がかりが伝えられるのは一度だけ。質問等は受け付けません。 首飾りの総数が分かったら、私にその数を告げて下さい。 明日は一日中ここで待機しております。 期限は明日の日没です」 翌朝、マリーベル博士が広場を訪れると5人の村人がおりました。 首飾りの総数を求めて下さい。
|
![]() ![]() 必要ないとは思いますが、補足です。
首飾りは単純な円形とみなして下さい。結び目を作ったりはしません。 赤石、白石の並び順だけを考え、間隔等は無視します。 村人2が言っている「今喋っていた者」とは村人1のことで間違いありません。 5人が述べている嘘つき、正直者の人数は、 この村に住む嘘つきの人数、この村に住む正直者の人数のことです。 0は任意の整数の倍数です。 1は素数ではありません。 首飾りの総数を半角または全角で囁くとかってに君が判定してくれます。 正解者が出るのを首を長くして待っています ![]() ![]()
いはら
残念ながら不正解です。
首を切られることになります。 ふっかつのじゅもんを唱えて蘇りましょう ![]() ![]()
いはら
・・・博士の首はその村に飾られることになりました
不正解です。 まともなコメントも書いてありませんでしたので、この一つだけを残して 他の7つの投稿は削除させていただきました。 ![]()
いはら
それだと首飾りになりませんから!
それでは、飾らずに埋めることにしましょう ![]() 残念ながら不正解でした。 ![]() ![]() ![]()
いはら
問題を勘違いされているのではないでしょうか。
何種類の首飾りを作ることができるか? という問題です。 ![]()
いはら
よい覚悟ですね
![]() では遠慮なくばっさりと。 どちらも違っています。 納得いかない場合は、赤石何個、白石何個など詳細を囁いていただければ、 しっかりチェックします。 ![]()
いはら
うーむ。質問は囁きにしてほしかったですね
![]() 実は村長の存在を忘れさせて誤答を誘うという狙いが少しあったのです。 ついでなので明かしてしまいましょう。 村長の存在を無視すると、 村人1は嘘つき、 村人2は正直者、 村人3は正直者、 村人4は嘘つき、 村人5は正直者、 で、赤石2個、白石3個、首飾りの総数は2個、 というのが問題の条件を満たします。 が、もちろん村長も村人ですので、これは答えではありません。 ![]()
いはら
いえいえ。お気になさらず。
この問題は非常に難しくて、回答者なしという事態が予想されましたので、 ダミーの答えを用意しておいただけです。 囁きの回答ですが、この場合、 首飾りの総数が素数ですので村人1は嘘つき、 首飾りの総数が4未満ですので村人2は正直者、 首飾りの総数から1を引くと3の倍数になりませんので村人4は嘘つき、 正直者、嘘つきの人数はどちらも6でないので村人5は正直者、 となります。 村人3が正直者だとすると、正直者の人数は3の倍数になりませんので矛盾。 村人3が嘘つきだとすると、正直者の人数は3の倍数になりますので矛盾。 どちらにしても矛盾しますので答えにはなりません。 つまり、最初の○○なら、という前提が間違っていることになります。 ![]() ![]() 正解者が出る気配がありませんので、いくつかヒントを出したいと思います。
まずは、第一のヒントです。 赤石2個、白石4個の場合の、首飾りの総数について考えてみます。 石が6個ありますが、正六角形ABCDEFの各頂点に一個ずつ石があるものとみなします。 正六角形の中心をOとします。 回転して同じになるものとかも区別すると、総数は6C2=15個です。 首飾りの総数と区別するために、この数を配置数と書くことにします。 赤石を1,白石を0とし、A,B,C,D,E,Fの順に並べて書くと、 000011,000101,000110,001001,001010 001100,010001,010010,010100,011000 100001,100010,100100,101000,110000 のように表記できます。 回転やひっくり返すといった操作により、ある配置は別の配置に移ります。 (同じ配置になることもあります) 何種類の操作が考えられるのでしょうか。 回転の場合、Oを中心とした60度の整数倍(0〜5)の回転の6種類が考えられます。 それぞれ、AをA,B,C,D,E,Fに移します。 ひっくり返すのは、Oを通るある直線についての対称移動と考えられます。 以後この操作を反転と書くことにします。 Aは反転により、A,B,C,D,E,Fのどれかに移ります。 対称軸として考えられるのは移動前後の2つの頂点の中点とOを結ぶ直線ただ一つですので、 反転も6種類考えられます。 どのような回転、反転を組み合わせても、 それは上記の12個の操作のどれかと実質的に同じものになります。 この12個の操作は群になっています。 000011は、 回転によって、000011,100001,110000,011000,001100,000110に移り、 反転によって、011000,001100,000110,000011,100001,110000に移ります。 同じものが2回ずつ、6種類の配置が現れています。 同じものが2回現れるのは、 000011を同じ000011に移す操作が0度の回転とOAについての反転の2つあるからです。 このような操作が一つだけ(0度の回転)のときは12種類現れます。 このような操作が3つあれば、12/3=4種類となります。 つまり、ある配置を同じ配置に移す操作の個数と、 その配置に対してすべての操作を施してできる配置の個数の積は、操作の個数と等しくなります。 さらに考察を深めると面白いことがいえるのですが、それは次のヒントで。 すべての場合を調べると、 000011,100001,110000,011000,001100,000110の6個は同じ首飾り、 000101,100010,010001,101000,010100,001010の6個は同じ首飾り、 001001,100100,010010の3個は同じ首飾りで、合計15個となります。 このように3つのグループに分かれますので、首飾りの総数は3個です。 ![]()
いはら
ご参加ありがとうございます
![]() ここまでは正しいです。 ![]() ![]() それでは、第二のヒントです。
まずは、前回のヒントを記号で表してみましょう。 赤石、白石の個数が与えられているとします。 回転や反転で同じになるものも区別した配置の集合をH、 考えられる操作の集合をGとします。 a∈H、g∈Gに対して、配置aに操作gを施して得られる配置をg(a)と書くことにします。 O(a)={g(a)|g∈G}とすると、O(a)はHの部分集合であり、 首飾りの総数は、集合{O(a)|a∈H}の要素の個数と等しくなります。 G[a]={g∈G|g(a)=a}とすると、|O(a)|×|G[a]|=|G|であり、|G[a]|=|G|/|O(a)|です。 (||は集合の要素の個数を表すものとします) N(g)={a∈H|g(a)=a}とします。 g(a)=aとなる(a,g)の組の個数は、 すべてのg∈Gについて|N(g)|を合計したものであり、 すべてのa∈Hについて|G[a]|を合計したものでもあります。 b∈O(a)のとき、|G[b]|=|G|/|O(b)|=|G|/|O(a)|=|G(a)|ですので、 すべてのb∈O(a)についての|G[b]|の合計は、|G|/|O(a)|×|O(a)|=|G|です。 つまり、同じ首飾りのグループ1個につき、|G|個です。 よって、すべてのa∈Hについての|G[a]|の合計は、首飾りの総数×|G|です。 これが、すべてのg∈Gについての|N(g)|の合計に等しいので、 首飾りの総数×|G|=Σ|N(g)| であり、首飾りの総数=1/|G|×Σ|N(g)| となります。 つまり、回転及び反転の実質の操作の個数を数え、 各操作において配置が変わらない首飾りの配置の数を合計し、 操作の個数で割れば、首飾りの総数が求められます。 この方法を使えば、首飾りの総数を(割と)簡単に計算することができるのです。 先ほどの赤石2個、白石4個の場合をもう一度考えてみます。 操作の個数は回転6個、反転6個の計12個。 AをAに移す回転で変化しない配置は全配置数と等しく15個、 AをBに移す回転で変化しない配置は0個。 AをCに移す回転で変化しない配置は0個。 AをDに移す回転で変化しない配置は001001,010010,100100の3個。 AをEに移す回転で変化しない配置は0個。 AをFに移す回転で変化しない配置は0個。 AをAに移す反転で変化しない配置は001010,010001,100100の3個。 AをBに移す反転で変化しない配置は000110,001001,100100の3個。 他の反転についても同じ個数ですので、 6個の反転についての合計は、6×3=18個。 回転によって変化しない配置が18個、反転によって変化しない配置が18個ですので、 首飾りの総数=(18+18)/12=3 となり、当然ながら前回数えたものと一致します。 参考までに赤石6個、白石6個の場合は総数50個になります。 とりあえずヒントはここまでにしておきます。 ![]()
いはら
残念でした!
赤石5個、白石6個の場合、首飾りの総数は26です。 ![]()
いはら
正解!首がつながりました。
素晴らしい!正解者第一号です! おめでとうございます ![]() あめゆじゅとてちて賢者! ![]() ![]() ようやく正解者が現れました。めでたしめでたしです。
前回のヒントから日が経ちましたので、またヒントを出したいと思います。 赤石または白石の個数が0個のとき、首飾りの総数は1です。 赤石または白石の個数が1個のときも首飾りの総数は1です。 村長の発言「今年は去年の首飾りをばらして組み替えるだけでよい」から、 首飾りの総数は1ではないことが分かりますので、赤石、白石ともに2個以上です。 赤石と白石の合計個数をnとします。 個数の少ない方の石を礎石と呼ぶことにします。 同数のときはどちらでも好きな方とします。 礎石の個数をkとします。 このとき、首飾りの総数を計算する方法を考えてみます。 全操作は、回転n個と反転n個の2n個です。 各々の操作において変化しない配置の個数を調べます。 まずは回転について考えます。 0度の回転の場合、すべての配置が不変です。 1個隣にずらす回転の場合、すべての石が同じ色であればすべての配置が不変、 異なる色がある場合は、どのような配置も不変ではありません。 2個隣にずらす回転の場合、一つおきに並んだすべての石の色が同じである必要があります。 もちろん、nは2の倍数でなくてはいけません。 n個の回転を、1個ずらす回転からn個ずらす回転までのn個と考えます。 mを1以上n以下の自然数とし、m個ずらす回転に対する不変配置の個数を考えます。 mとnの最大公約数をgcd(m,n)、s=n/gcd(m,n)とします。 n/s=gcd(m,n)です。 n個の石を連続するn/s個の石のグループs個に分けたとき、 それぞれのグループ内の赤石、白石の配置がすべて等しいときに不変となります。 kもsで割り切れなくてはいけませんので、sはnとkの公約数です。 各グループの石の総数はn/s個、礎石の数はk/s個ですので、 グループ内の石の配置の総数はC(n/s,k/s)個です。 (C(n,k)=nCkです) つまり、m個ずらす回転に対する不変配置の個数は、s=n/gcd(m,n)として、 C(n/s,k/s)個です。 nとkの公約数sに対してmとnの最大公約数がn/sになるようなmがいくつあるのか考えてみます。 mとnの最大公約数がn/sということは、 m÷(n/s)とn÷(n/s)が互いに素ということです。 t=m÷(n/s)=ms/nとすると、tとsが互いに素です。 0<m≦nですので、0<ms/n≦n×s/n=sであり、0<t≦sです。 tの個数は、1以上s以下の自然数でsと互いに素なもののの個数、すなわちφ(s)個です。 (φはオイラーのトーティエント関数。詳しくは新マオークエスト第三幕参照) tとmは一対一に対応しますので、mの個数も同じです。 よって、回転に対する不変配置の個数の総計は、 Σφ(s)C(n/s,k/s) [sはn,kの公約数] となります。 例えばn=12,k=6のとき、 12と6の公約数は1,2,3,6の4つですので、回転に対する不変配置の個数の総計は、 φ(1)C(12/1,6/1)+φ(2)C(12/2,6/2)+φ(3)C(12/3,6/3)+φ(6)C(12/6,6/6) =C(12,6)+C(6,3)+2C(4,2)+2C(2,1)=960 となります。 反転に対する不変配置についてはまた後日。 ![]() ![]() では、反転に対する不変配置を考えてみましょう。
正n角形の中心を通る直線を対称軸とする対称変換で、 ある頂点をn個の頂点のどれかに移すn通りのものが考えられます。 n,kの偶奇によって、場合分けします。 ・n,kがともに偶数の場合 反転の対称軸が2つの頂点を通るものと、頂点を通らないものの2種類があります。 それぞれはn/2個ずつです。 反転の対称軸が2つの頂点を通るとき、 残りのn-2個の石の配置が対称になりますので、 そのn-2個に含まれる礎石の数は偶数。 よって、対称軸上の2点に含まれる礎石の数も偶数であり、0個または2個です。 対称軸上の礎石が2個であれば、 対称軸上の石の配置は1通り、 対称軸外の石の配置は、C(n/2-1,k/2-1)通りとなります。 対称軸上の礎石が0個であれば、 対称軸上の石の配置は1通り、 対称軸外の石の配置は、C(n/2-1,k/2)通りとなります。 よって、この反転に対して不変な配置の個数は、 C(n/2-1,k/2-1)+C(n/2-1,k/2)=C(n/2,k/2) です。 対称軸が頂点を通らないとき、 不変配置の個数は、C(n/2,k/2)個です。 それぞれの反転はn/2個ずつありますので、不変配置の個数の総計は、 n×C(n/2,k/2) となります。 ・nが偶数で、kが奇数の場合 反転の対称軸が2つの頂点を通るとき、 対称軸上の礎石の個数は奇数でないといけないので、1個です。 対称軸上の石の配置は2通り、 対称軸外の石の配置は、C(n/2-1,(k-1)/2)となります。 反転の対称軸が頂点を通らないとき、 kは奇数ですので、不変となる配置はありません。 よって、不変配置の個数の総計は、 n/2×2×C(n/2-1,(k-1)/2)=n×C(n/2-1,(k-1)/2) となります。 ・nが奇数でkが偶数の場合 任意の反転の対称軸は1つの頂点を通ります。 kが偶数なので、その頂点は礎石ではありません。 よって、石の配置の個数はC((n-1)/2,k/2) これがn個あるので不変配置の個数の総計は、n×C((n-1)/2,k/2)個です。 ・n,kがともに奇数の場合 任意の反転の対称軸は1つの頂点を通ります。 kが奇数なので、その頂点は礎石です。 よって、石の配置の個数はC((n-1)/2,(k-1)/2) これがn個あるので不変配置の個数の総計は、n×C((n-1)/2,(k-1)/2)個です。 以上をあえて一つの式で表すと、kを2で割ったときの余りをrとして、 n×C([(n-r)/2],(k-r)/2) と書けます。 ([]はガウス記号。[x]はxを超えない最大の整数) これが反転に対する不変配置の個数の総計です。 例えばn=12,k=6のとき、 r=0ですので、反転に対する不変配置の個数の総計は、 12×C(6,3)=240 回転に対する不変配置の個数の総計は960でしたので、 首飾りの総数は、(960+240)/24=50個、となります。 これで、赤石、白石の個数が具体的に与えられたとき、 首飾りの総数を計算することができるようになりましたね。 ここまでヒントを出すと、難易度は★★★★といったところでしょう。 ![]()
いはら
数え間違えているようです。
正直者12人、嘘つき4人の場合、首飾りの総数は、 (φ(1)C(16,4)+φ(2)C(8,2)+φ(4)C(4,1)+16C(8,2))/32 =(C(16,4)+17C(8,2)+2C(4,1))/32=72 となり、72個です。 ![]() ![]() 今までのヒントを整理します。
回転に対する不変配置の個数を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が正直者だと仮定します。 α<4です。 α≠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が嘘つきであることが分かります。 ![]() ![]() 村人1,2は嘘つきであることが分かりました。
よって、首飾りの総数は4以上の素数です。 村人4が正直者だと仮定します。 嘘つきまたは正直者のどちらかは4人です。 よって、gcd(n,k)は1,2,4のいずれか。 4のときは、正直者、嘘つきの人数がともに4の倍数となり、 村人1が嘘つきであることに矛盾します。 よって、gcd(n,k)は1または2です。 gcd(n,k)=1の場合 nが偶数のときはgcd(n,k)=1とはならないのでnは奇数です。 よって、ある自然数mを使ってn=2m+1と書けます。 n≧4ですのでm≧2です。 このとき、 P=φ(1)C(n,k)=C(2m+1,4)=(2m+1)×2m×(2m-1)(2m-2)/24 Q=n×C([(n-r)/2],(k-r)/2)=(2m+1)C(m,2)=(2m+1)m(m-1)/2 α=(P+Q)/2n=(m-1)m(m+1)/6 m≧7のとき、m-1,m,m+1はいずれも6以上なのでαが素数となることはありません。 m=2,3,4,5,6のとき、α=1,4,10,20,35となりいずれも素数ではありません。 gcd(n,k)=2の場合 ある自然数mを使ってn=4m+2と書けます。m≧1です。 このとき、 P=φ(1)C(4m+2,4)+φ(2)C(2m+1,2) Q=(4m+2)C(2m+1,2) α=m(4m^2+3m+2)/3 です。 f(m)=4m^2+3m+2とすると、α=f(m)×m/3です。 m≧4のとき、f(m)≧78ですのでαは素数にはなりません。 m=1のとき、α=3で不適。 m=2のとき、α=16で不適。 m=3のとき、α=47。47-1=46は3の倍数ではありませんので不適です。 結局、条件を満たす場合はないことが分かりました。 よって、仮定は誤りであり、村人4は嘘つきです。 ![]() ![]() 今までに村人1,2,4が嘘つきであることが判明しています。
村人5が正直者と仮定します。 嘘つきは4人以下となりますが、村人4が嘘つきなので嘘つきは4人ではありません。 村人1,2,4の3人が嘘つきなので、嘘つきはこの3人のみと確定。 よって、村人3は正直者であり、正直者の人数は3の倍数。 村人の人数nも3の倍数となります。 nが偶数の場合 ある自然数mがあって、n=6mと書けます。 このとき、 P=φ(1)C(6m,3)+φ(3)C(2m,1)=6m(6m-1)(6m-2)/6+4m Q=6m×C(3m-1,1)=6m(3m-1) α=3m^2 αが素数になるのはm=1のときのα=3だけなので不適。 nが奇数の場合 ある自然数mがあって、n=3(2m+1)と書けます。 このとき、 P=φ(1)C(6m+3,3)+φ(3)C(2m+1,1)=(6m+3)(6m+2)(6m+1)/6+2(2m+1) Q=(6m+3)×C(3m+1,1)=(6m+3)(3m+1) α=3m^2+3m+1 α-1=3m^2+3m=3(m^2+m) なのでα-1は3の倍数であり、村人4が嘘つきであることに矛盾します。 結局条件を満たす場合はなく、仮定は誤りであることが分かりました。 よって、村人5は嘘つきです。 ![]() ![]() 村人5が嘘つきですので、正直者または嘘つきのどちらかは6人です。
よって、gcd(n,k)は1,2,3,6のいずれかです。 gcd(n,k)=1の場合 nは奇数ですので、ある自然数mを使ってn=2m+1と書けます。 n≧6ですので、m≧3です。 P=φ(1)C(2m+1,6)=(2m+1)×2m(2m-1)(2m-2)(2m-3)(2m-4)/720 Q=nC(m,3)=(2m+1)m(m-1)(m-2)/6 α=m(2m^4-10m^3+25m^2-35m+18)/90 です。 f(m)=2m^4-10m^3+25m^2-35m+18とすると、α=mf(m)/90です。 f(0)=18,f(1)=0,f(2)=0,f(3)=30,f(4)=150,f(5)=468 はすべて6の倍数ですので、f(m)≡0 (mod 6)です。 m=3のとき、α=1で不適。 m=4のとき、n=9でありgcd(n,k)=3となるので不適。 m=5のとき、α=26で不適。 m>5のときを調べます。 f(m)=2m^3×(m-5)+5m(5m-7)+18 なのでm>5のときにはf(m)≧f(5)=468です。 f(m)/6は整数であり、f(m)/90>2なので、 α=m/15×f(m)/6が素数であるためには、mが15の約数である必要があります。 m>5ですので、m=15です。 このとき、α=12103=7×1729なので不適です。 gcd(n,k)=2の場合 ある自然数mを使ってn=2mと書けます。 m≧3で、mは3の倍数ではありません。 P=φ(1)C(2m,6)+φ(2)C(m,3)=2m(2m-1)(2m-2)(2m-3)(2m-4)(2m-5)/720+m(m-1)(m-2)/6 Q=nC(m,3)=2m×m(m-1)(m-2)/6 α=m(2m^4-15m^3+50m^2-75m+38)/90 f(m)=2m^4-15m^3+50m^2-75m+38とすると、α=mf(m)/90です。 m=4のとき、α=4で不適。 m=5のとき、α=16で不適。 m=7のとき、α=126で不適。 m≧8のときを調べます。 f(1)=f(2)=0なのでf(m)≡0 (mod 2)であり、f(m)/2は整数です。 f(m)=m^3×(2m-15)+25m(2m-3)+38ですので、f(m)≧f(8)=3150です。 f(m)/90>1ですので、α=m/45×f(m)/2が素数であるためには、 mが45の約数である必要があります。 よって、m=9,15,45です。 これらはすべて3の倍数ですので不適です。 gcd(n,k)=3の場合 ある自然数mを使ってm=3(2m+1)と書けます。 m≧1です。 P=φ(1)C(6m+3,6)+φ(3)C(2m+1,2)=(6m+3)(6m+2)(6m+1)×6m(6m-1)(6m-2)/720+2(2m+1)×2m/2 Q=nC(3m+1,3)=3(2m+1)(3m+1)×3m(3m-1)/6 α=m(54m^4+15m^2+1)/10 f(m)=54m^4+15m^2+1とすると、α=mf(m)/10です。 f(m)≧f(1)=70ですので、f(m)/10>1であり、mは10の約数である必要があります。 よって、m=1,5,10です。 m=1のとき、α=7。α-1=6は3の倍数ですので不適。 m=5のとき、α=17063=113×151ですので不適。 m=10のとき、α=541501。α-1は3の倍数ですので不適。 gcd(n,k)=6の場合 ある自然数mを使ってn=6mと書けます。 m≧1です。 P=φ(1)C(6m,6)+φ(2)C(3m,3)+φ(3)C(2m,2)+φ(6)C(m,1) Q=6mC(3m,3) α=m(54m^4-135m^3+150m^2-75m+16)/10 f(m)=54m^4-135m^3+150m^2-75m+16とすると、α=mf(m)/10です。 m=1のとき、α=1で不適。 m=2のとき、α=50で不適。 m≧3のときを調べます。 f(m)=9m^3(6m-15)+75m(2m-1)+16ですので、f(m)≧f(3)=1870 f(m)/10>1ですので、mは10の約数である必要があります。 よって、m=5,10 m=5のとき、α=10133で素数となります。 m=10のとき、α=419266で不適です。 以上より、答えになる可能性があるのは、 (n,k)=(30,6),α=10133のときのみです。 村人1の発言より正直者の人数は4の倍数ではありませんので、 嘘つきが24人、正直者が6人です。 正直者の人数が3の倍数ですので村人3は正直者となります。 赤石24個、白石6個の首飾りで、ある白石の両隣が赤石となるものは 簡単に作れますので、もう一つの発言も矛盾しません。 村人1,2,4,5は嘘つき、村長と村人3は正直者です。 この村には他に嘘つきが20人、正直者が4人いるわけです。 問題の条件をすべて満たしますので、首飾りの総数は10133です。 |