◆静岡県 ヨッシーさんからの解答。
【問題２】
ある状態（ａ，ｂ，ｃ）が１回の出会いで（ａ1，ｂ1，ｃ1）になるとする。
よって、ｂ−ｃ≡ｂ1−ｃ1（mod ３）
このあと、（ａ2，ｂ2，ｃ2）、（ａ3，ｂ3，ｃ3）・・・と変化しても、
ｂ−ｃ≡ｂ1−ｃ1≡ｂ2−ｃ2≡ｂ3−ｃ3≡・・・・ (mod 3)
が成り立つ。
よって、出会いを何度か繰り返したのちの（ａ’，ｂ’，ｃ’）についても、
ｂ−ｃ≡ｂ’−ｃ’（mod ３）
例えば、ｂ＝ｃ＝０とすると、たとえａ＞０であっても、
状態（ａ，ｂ，ｃ）＝（ａ，０，０）は違う色が出会わないので、変化しない。
よって、（ａ，ｂ，ｃ）≠（ａ’，ｂ’，ｃ’）に反する。
ｃ＝ａ＝０，ａ＝ｂ＝０の場合も同様である。
よって、ａｂ＋ｂｃ＋ｃａ≠０が成り立つ。
【問題１】
黄色、灰色、青色のカメレオンがそれぞれａ匹、ｂ匹、ｃ匹いる状態を
（ａ，ｂ，ｃ）として表します。
全てのカメレオンが同じ色になるのは、どれかの色のカメレオンが４５匹で、他の２色のカメレオンが０匹の状態である。
このとき、ａ−ｂ≡ｂ−ｃ≡ｃ−ａ≡０ (mod 3) である。
一方、
１５−１３≡１７−１５≡２ (mod 3)
１７−１３≡１ (mod 3)
であるので、状態（１３，１５，１７）が
状態(４５，０，０)，(０，４５，０)，(０，０，４５)のいずれかになることはない。
【コメント】
大変わかりやすい証明ですね。
問題１の方は完璧です。
問題２は必要条件であることは、これでＯＫですね。
十分条件であることを証明してください。
（例えばａ＋ｂ＋ｃ＝ＰとしてＰに関する帰納法が利用できます。）
◆広島県 清川 育男さんからの解答。
【問題１】
答え ありえない。
２進法の問題に還元された「三山くずし」を連想しました。
今回の問題は３で割ったときの剰余の問題に還元されます。
共通していることは、「同数の法則」でしょうか。
（１３，１５，１７）はどのような遭遇があっても、少なくとも２種類のカメレオンを同数にすることが出来ません。
遭遇するとそれぞれはマイナス１で遭遇していないものはプラス２で出入りは３となります。
初期状態のそれぞれの差が２または４あるので、不可能であることがわかります。
（１３，１５，１７）＞＞＞（１，０，２）。
１３＋１５＋１７＝４５。
１種類に出来る場合。
３で割ったときの剰余で考える。
以上の場合はどの１種類にもなりうる。
順序を無視すれば基本的には９通り。
４５が３の倍数なので、
（０，０，０）、（１，１，１）、（２，２，２）のパターンしかありません。
２進法、３進法の問題はよくありますが、４進法に還元されるおもしろい問題はないのでしょうか。
◆山梨県 Footmark さんからの解答。
【問題１】
(総数が４５とは限らない)一般形で示します。
すべてのカメレオンが１種類になれるための必要十分条件は次の通り。
(１) ａ＋ｂ＋ｃ≧１
かつ
(２)
[ ａ mod ３ ＝ ｂ mod ３ ] または [ ｂ mod ３ ＝ ｃ mod ３ ] または [ ｃ mod ３ ＝ ａ mod ３ ]
つまり、ａ,ｂ,ｃ のそれぞれを３で割った余りが３つとも異なれば不可能で、それ以外は可能。
（ただし、ａ,ｂ,ｃ は初期状態での３種類のカメレオンのそれぞれの数）
問題の初期状態(１３,１５,１７)では、３で割った余りはそれぞれ(１,０,２)とすべて異なるので不可能。
【必要十分条件の証明】
初期状態が(０,０,０)なら不可能なのは明らか。
よって、条件(１)を満たさねばならない。
ここで、ｍ,ｎは正整数、ｋは非負整数であるものとする。
初期状態が(ｍ,０,０)または(０,ｍ,０)または(０,０,ｍ)ならば既に条件を満たしている。
また、初期状態が(ｋ,ｍ,ｍ)または(ｍ,ｋ,ｍ)または(ｍ,ｍ,ｋ)ならば、同数の２種類同士がｍ回出会えば可能。
・・・（仮必要条件）
そこで、すべてのカメレオンがある１種類になったものとする。
すると、その直前の状態では出会いの定義より、必ずその種類とは別な１匹ずつの２種類が存在する。
そこで、直前の状態に戻し１匹ずついる２種類を取り除いてみる。
やはり、その直前の状態では出会いの定義より、必ずその種類とは別な１匹ずつの２種類が存在する。
このように可能な限り手前の状態に戻すと、結局その種類とは別な２種類はｍ匹ずつになる。
それ故、逆にどの２種類も同数になれないなら、すべてのカメレオンを１種類にはできない。
・・・（仮十分条件）
ここで、同数になれる２種類の初期状態の数を考えてみる。
初期状態で同数なら、前述したように可能なのは明白で、その差は０となる。
そうでなければ、それらとは別な種類と多い方の種類が何回(≧１)か出会い、多い方を減らし少ない方を増やす必要がある。
出会いの定義より、多い方のカメレオンの増分を −ｎ とすると
少ない方のカメレオンの増分は ＋２ｎ である。
そこで、上のような出会いが何回かあり、多い方と少ない方のカメレオンがｍ匹ずつになったものとする。
すると、上のような出会いが何回かある前の２種類のカメレオンの数は
(ｍ＋ｎ,ｍ−２ｎ)の筈であり、その差は３ｎとなる。
これらの２つのケースを一緒にすると、その差は３ｋとなる。
２種類の差が３で割り切れるなら、その２種類の数を３で割ったそれぞれの余りは等しく条件(２)を満たす。
・・・（必要条件）
逆に条件(２)を満たさないなら、どの２種類の差も３で割り切れず結局どの２種類も同数になれないので不可能。
・・・（十分条件）
証明は終わり。
【問題２】
移行のための最少置換を示すのに都合がよいので、便宜上、
(ａ'−ａ),(ｂ'−ｂ),(ｃ'−ｃ)を大きい順に(ｐ'−ｐ),(ｑ'−ｑ),(ｒ'−ｒ)と置き換えるものとする。
（ただし、ｐ'−ｐ≧ｑ'−ｑ≧ｒ'−ｒ）
また、その時のそれぞれのカメレオンをＰ,Ｑ,Ｒとする。
さらに、
[出会いＰ]：１匹のＱと１匹のＲが出会い２匹のＰに変化する出会い。
[出会いＱ]：１匹のＲと１匹のＰが出会い２匹のＱに変化する出会い。
[出会いＲ]：１匹のＰと１匹のＱが出会い２匹のＲに変化する出会い。
置換[ｘ,ｙ,ｚ]：[出会いＰ]がｘ(≧０)回、[出会いＱ]がｙ(≧０)回、[出会いＲ]がｚ(≧０)回の置換。
（Ｐ,Ｑ,Ｒの定義より明らかに ｘ≧ｙ≧ｚ≧０）
と定義する。
【証明】
証明では 与えられた ａ,ｂ,ｃ,ａ',ｂ',ｃ' の替わりに、
定義した ｐ,ｑ,ｒ,ｐ',ｑ',ｒ' を使用する。
（ただし、ｐ'−ｐ≧ｑ'−ｑ≧ｒ'−ｒ）
このことによって一般性が失われることがないのは明らかである。
状態(ｐ,ｑ,ｒ)は[出会いＰ]が起こると
出会いの定義より状態(ｐ＋２,ｑ−１,ｒ−１)となる。
（[出会いＰ]を例にしているが、[出会いＱ]や[出会いＲ]でも同様）
３組ある２数の差は
(ｐ＋２)−(ｑ−１)＝(ｐ−ｑ)＋３
(ｑ−１)−(ｒ−１)＝(ｑ−ｒ)
(ｒ−１)−(ｐ＋２)＝(ｒ−ｐ)−３
いずれの２数の差も出会い前の２数の差に
３の倍数(３,０,−３)を加えたものである。
よって
ｐ−ｑ≡ｐ'−ｑ'（mod ３）かつ ｑ−ｒ≡ｑ'−ｒ'（mod ３）かつ ｒ−ｐ≡ｒ'−ｐ'（mod ３）
その後いろいろな出会いがいくつ起きようが、３の倍数が加えられるだけなのでこのことに変わりはない。
ところで、ｐ＋ｑ＋ｒ＝ｐ'＋ｑ'＋ｒ' なので、
ｑ−ｒ≡ｑ'−ｒ'（mod ３）を満たすと、
−２(ｑ−ｒ)−(ｐ＋ｑ＋ｒ)≡−２(ｑ'−ｒ')−(ｐ'＋ｑ'＋ｒ') (mod ３)
∴ (ｒ−ｐ)−３ｑ≡(ｒ'−ｐ')−３ｑ' (mod ３)
３ｑ,３ｑ'は明らかに３で割り切れる。
∴ ｒ−ｐ≡ｒ'−ｐ' (mod ３)
同様にして、ｒ−ｐ≡ｒ'−ｐ' (mod ３) を満たすと、
ｐ−ｑ≡ｐ'−ｑ' (mod ３) も満たす。
よって、条件は ｑ−ｒ≡ｑ'−ｒ'（mod ３）だけでよい。（必要条件）
一方、出会いの定義より、
＋２ｘ−ｙ−ｚ＝ｐ'−ｐ
−ｘ＋２ｙ−ｚ＝ｑ'−ｑ
−ｘ−ｙ＋２ｚ＝ｒ'−ｒ
ところが、[出会いＰ],[出会いＱ],[出会いＲ]が同数回ずつあると元に戻り、何も起きなかったのと一緒である。
（つまり、置換[ｍ,ｍ,ｍ]は置換[０,０,０]と同等）
それ故、状態(ｐ,ｑ,ｒ)から状態(ｐ',ｑ',ｒ')に移行する置換は無限にある。
そこで、総出会い回数(ｘ＋ｙ＋ｚ)が最少である置換だけを考える。
移行可能な１つの置換[ｘ,ｙ,ｚ]のｚはｘ,ｙ,ｚの最少値(≧０)である。
すると、ｚの数だけ[出会いＰ]も[出会いＱ]も[出会いＲ]もあることになる。
同数回ずつの[出会いＰ],[出会いＱ],[出会いＲ]は省略できるので、ｘ,ｙ,ｚの各値からｚを引いてやる。
すると、最少置換での新しいｘ,ｙ,ｚの最少値ｚは０になる。
それ故、どのような移行も２種類以下の出会いだけで可能である。
ｚ＝０ を上の式に代入すると、
２ｘ−ｙ＝ｐ'−ｐ
２ｙ−ｘ＝ｑ'−ｑ
−ｘ−ｙ＝ｒ'−ｒ
１番目の式の両辺から３番目の式の両辺を引いてｘを求めると、
| ｘ＝ | (ｐ'−ｐ)−(ｒ'−ｒ) ３ |
| ｙ＝ | (ｑ'−ｑ)−(ｒ'−ｒ) ３ |
| 置換[ | 増分ｐ−増分ｒ ３ | ， | 増分ｑ−増分ｒ ３ | ， | ０]である。 |
また、ｘ,ｙを変形すると、
| ｘ＝ | (ｐ'−ｐ)−(ｒ'−ｒ) ３ | ＝ | (ｐ'−ｒ')−(ｐ−ｒ) ３ |
| ｙ＝ | (ｑ'−ｑ)−(ｒ'−ｒ) ３ | ＝ | (ｑ'−ｒ')−(ｑ−ｒ) ３ |
{(ｐ'−ｒ')−(ｐ−ｒ)} mod ３ ＝ {(ｑ'−ｒ')−(ｑ−ｒ)} mod ３ ＝ ０
でなければならない。
２数の差が３で割り切れることと、２数を３で割った余りが等しいこととは同等なので、
ｒ−ｐ≡ｒ'−ｐ'（mod ３）かつ ｑ−ｒ≡ｑ'−ｒ'（mod ３）
これも、必要条件で示したように、ｑ−ｒ≡ｑ'−ｒ'（mod ３）さえ満たしさえすればおのずと、
ｒ−ｐ≡ｒ'−ｐ'（mod ３）も ｐ−ｑ≡ｐ'−ｑ'（mod ３）も満たすことになる。
よって、条件は ｑ−ｒ≡ｑ'−ｒ'（mod ３）だけでよい。（十分条件）
また、ｐｑ＋ｑｒ＋ｒｐ＝０ ならカメレオンは１種類しかなく、[出会いＰ]も[出会いＱ]も[出会いＲ]も起きず元のままである。
ところが、状態(ｐ,ｑ,ｒ)と状態(ｐ',ｑ',ｒ')は同一でないので矛盾する。
よって、ｐｑ＋ｑｒ＋ｒｐ≠０
証明は終わり。
[ Ｐ・Ｓ ]
とても面白い問題ですね。
興味があったので、一般形での初期状態と最終状態における最少置換も求めてみました。
そんな問題もあってもよかったですね。