数学の部屋へもどる◆大阪府 Non さんからの解答。
【問題１】
できる。
３，４，１，６，２，５
【問題２】
できない。
順に回転させていくと、
３，５，２，４，１
１，３，５，２，４
４，１，３，５，２
２，４，１，３，５
５，２，４，１，３
アンダーラインの部分が、番号が重なる。
【おまけ】
ツトム君の番号とメダルの番号が全て異なるようにすることができない並び方を考えると、
初期状態で一致する数字が１つ、
１個回転した状態で一致する数字が１つ、
...
n-1個回転した状態で一致する数字が１つ
存在することになる。
ここで、初期状態でのメダルの並びを(a(1),a(2),...,a(n))とすると、
a(k)-k≡0 (mod n)となるkが１つ、
a(k)-k≡1 (mod n)となるkが１つ、
...
a(k)-k≡n-1 (mod n)となるkが１つ
存在することになる。
よって、
Σ(a(k)-k)≡n(n-1)/2 (mod n)
一方、明らかに、Σa(k)=Σkなので、
n(n-1)/2≡0 (mod n)
となる。
n(n-1)/2がnの倍数となるためには、(n-1)/2が整数となる、すなわちnが奇数であることが必要。
よって、nが偶数の時には、ツトム君の番号とメダルの番号が全て異なるようにすることができない並び方は存在しない。
すなわち、ツトム君の番号とメダルの番号が全て異なるようにすることが必ずできる。
一方、nが奇数の時には、
たとえば、(1,3,5,...,n,2,4,...,n-1)と並べると、
初期状態では1が一致、
１個回転すると、3が一致、
２個回転すると、5が一致、
...
(n-1)/2個回転すると、nが一致、
(n+1)/2個回転すると、2が一致、
(n+3)/2個回転すると、4が一致、
...
n-1個回転すると、n-1が一致
するので、ツトム君の番号とメダルの番号が全て異なるようにすることができない。
つまり、
【おまけ１】の解答はnが偶数の時
【おまけ２】の解答はnが奇数の時で、
並べ方の例は(1,3,5,...,n,2,4,...,n-1)となる。
◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】
(1) 3，4，1，6，2，5
(2) 5，3，4，1，6，2
【問題２】
できない。
【おまけ１】
ｎが偶数
【おまけ２】
ｎが奇数
∵ つとむ君の集合を
Ｔ＝{つとむ１、つとむ２、〜つとむｎ}とします。
また つとむ君の位置を時計まわりの位置：０〜ｎ-1で表すこととし、
Ｐ[i] Ｔ∋i とします。
つまり Ｐ[つとむI]=I-1
さらにメダルの位置を同様に Ｍ[i] Ｔ∋i とします。
するとＤ[i]=Ｍ[i]-Ｐ[i] ( mod n、Ｔ∋i) は つとむI君のメダルを一致させる回転移動量になります。
集合 Ｄ＝{Ｄ[i]|Ｔ∋i} が 集合Ｕ＝[0,1,〜n-1]に等しい場合にはどれだけ回転移動しても必ず一致するつとむ君がいます。
ところで、
Σ{Ｄ[i]}＝Σ{Ｍ[i]}−Σ{Ｐ[i]}＝Σ{Ｕ[i]}−Σ{Ｕ[i]}＝０ (mod n)
一方 Σ{Ｕ[i]}＝n(n-1)/2 であって ｎが偶数のとき Σ{Ｕ[i]}≠０(mod n)です。
〇即ちｎが偶数のときＤ＝Ｕにはできないので、
Ｕ−Ｄの集合がφでなく、それらが解答になります。
〇ｎが奇数の場合、Ｍ[つとむI]＝2*I-1 (mod n) は ２とｎが互いに素であることから
Ｍ＝Ｕ であってメダルの配置として妥当であり、
かつ Ｄ[つとむI]=I (mod n) であるから Ｄ＝Ｕ です。
よってこのＭは回転移動しても必ず一致するものがある例になります。
◆東京都 イ さんからの解答
【命名】
１〜ｎの場合、説明のためｎは０と表現する。
点０ 点１ … 点ｎー１
に対して、数０ 数１ 数２ … 数ｎ−１を適当に配置する。
数の並びは数０から順番に並べたものを配列と呼ぶことにする。
「ある数の配置された場所」から「その数の分」だけ戻った場所を「その数の零点」と呼ぶことにする。
例えば
点０１２３４５６
数２４６１３５０
は、配列０２４６１３５を配置したものであり、数６は点２に配置され、数６の零点は点３である。
【性質】
ある配列が、全ての数が点の名前と異なるような配置を持たない。
（どのような配置でも、どれかは必ず一致する）
⇔
その配列において零点はかぶらない。（全て異なる）
零点とは、もしある数の零点が点０にあったならば、その数は点の名前と一致するという性質をもつものであるからである。
【証明】
次のことを証明する。
１．奇数人ならば、うまい配列をとれば、いかなる配置においても、全ての数と点の名が異なるようにはできない。
２．偶数人ならば、いかなる配列においても、うまい配置をすれば、ある数と点の名が一致するようにできる。
１．そのような配列の作成方法を示せば十分である。
偶数を小さい順、その次に奇数を並べれば、零点は点の名前と逆順にまわる。
例えば
点０１２３４５６
数０２４６１３５
このとき、奇数個ならば数０の零点は点０、数２の零点は点６、数４の零点は点５、６→４、１→３…
よって、このような作成手順によれば零点は被らない。
２．まず、零点が点Ａにあるような、数Ｂは、点（Ａ＋Ｂ あるいはそれを、人数分で割ったもの）にあるべきである。
このことを
（零点の点の名前）＋（数）≡（その数の置かれる点の名前） mod （人数）
と表現する。
ここで仮定 「零点が被らない。」
このとき、０〜ｎ−１をそれぞれ一回ずつ使って
（０〜ｎ−１）＋（０〜ｎ−１）≡（０〜ｎ−１） mod ｎ
という式がｎ個できるはずである。
（もちろん、数もおかれる場所も被らないので）
点０１２３４５６
数０２４６１３５
ならば
０＋０≡０ mod７
１＋５≡６
２＋３≡５
３＋１≡４
４＋６≡３
５＋４≡２
６＋２≡１
これは偶数個の場合不可能である。
なぜならば、もし可能ならばｎ個の式を全て足した
（０＋１＋…＋ｎ−１）＋（０＋１＋…＋ｎ−１）≡（０＋１＋…＋ｎ−１） mod ｎ
が成立するはずである。
左辺＝（１＋ｎー１）＋（２＋ｎ−２）＋…＋（ｎ−１＋１）≡０
しかし偶数ならば、右辺≡ｎ／２
よって矛盾。
つまり偶数では不可能。
よって、偶数の場合零点は被る。
つまり「ある配列が、全ての数が点の名前と異なるような配置を持たない。」の否定が成り立つ。
◆東京都 明 さんからの解答
【問題１】
3，4，1，6，2，5
【問題２】
できません。
【おまけ１】
まず、 ツトム君の番号とメダルの番号が、メダルを回転しても常に一つは一致する場合を考える。
特定のツトム君とメダルの番号が一致するのは、メダルの１回転に１回のみ。
したがって１回転の間、常にいずれかのツトム君とメダルの番号が一致するためには、１回転のどの位置でもいずれか１人だけのツトム君と、対応する１つのメダルの番号が一致するようになっていなければならない。
最初、ツトム君とメダルの番号が一致しているツトム君の番号を「０」とし、メダルの回転方向の順にツトム君の番号を１，２，・・・，ｎ−１と付けます。
またこの時、各ツトム君に対応するメダルの番号を
Ｙ1，Ｙ2，・・・，Ｙn-1とし、さらに各メダルがツトム君の番号と一致するまでのメダル回転の数を順に
Ｘ1，Ｘ2，・・・，Ｘn-1とします。
ただし j≠k のとき
Ｘj≠Ｘk かつ Ｘj，Ｘk＝１〜ｎ−１
Ｙj≠Ｙk かつ Ｙj，Ｙk＝１〜ｎ−１
以上の条件でのみ１回転の間、常にいずれかのツトム君とメダルの番号が一致します。
以上の条件で下記式が成立します。
１＋Ｘ1 ＝ Ｙ1 （mod ｎ）
２＋Ｘ2 ＝ Ｙ2 （mod ｎ）
ｊ＋Ｘj ＝ Ｙj （mod ｎ）
ｎ-1＋Ｘn-1 ＝ Ｙn-1 （mod ｎ）
上の式を縦に加えることにより ΣＹj ＝ 1+2+・・+ｎ-1を考慮すると
ΣＸj ＝ ０ （mod ｎ）となっていなければならない。
また ΣＸj ＝ 1+2+・・+ｎ-1 であることから、
ｎが偶数の時 ΣＸj ＝ ｎ／２ （mod ｎ）
ｎが奇数の時 ΣＸj ＝ ０ （mod ｎ）
したがってｎが偶数のときはメダルの配置をどのようにしても、ツトム君の番号とメダルの番号を常に一致させておくことはできない。
一方ｎが奇数の時、Ｘj＝ｊとしてみると
メダルｊに対応するツトム君の番号はＹj＝２ｊ（mod ｎ）となるが、
ｊ≠k のとき Ｙj−Ｙk＝２（j-k）≠０ （mod ｎ）
より、確かに Ｙj≠Ｙk かつ Ｙj，Ｙk≠０を成立させることができる。
以上により、ｎが奇数の場合はツトム君の番号とメダルの番号を常に一致させておくメダル配置が構成できます。
【おまけ２】
以上により、ｎが奇数の時はツトム君の番号とメダルの番号が全て異なるようにすることができない場合があります。
「０」のツトム君はｎ番に対応します。
メダルの配置はｎの約数の最小値をｐとすると、
ｊのツトム君に対し２ｊ（mod ｎ）のメダルを対応させる配置以外に
３ｊ・・・，(ｐ-１)ｊ（mod ｎ）を対応させることができます。
計算機で総当りしたところ、これ以外にも配置がたくさん存在することを確認しました。
ちなみに、
ｎ＝３ １通り
ｎ＝５ ３通り
ｎ＝７ １９通り
ｎ＝９ ２２５通り
ｎ＝１１ ３４４１通り
これ以上は総当り式ではかなりの時間が必要になります。
論理的に洗い出す方法はわかりませんでした。
◆ 問題へもどる
◆ 今週の問題へ