◆宮城県 甘泉法師 さんからの解答。
【問題１】
多面体を４面体に分割する。
ｍ個の各頂点に４つの色から１色をえらんで割り当て、すべての４面体が４色の頂点をもつようにすることができる。
参考 「防犯カメラの問題」でのヒントの多角形の三角形への分割説明図
| 少なくとも一色の頂点の個数は[ | ｍ ４ | ]以下である。 |
| なぜならば、もしすべての色の頂点の数が[ | ｍ ４ | ]より大きいとすると |
| ｍ≧４｛[ | ｍ ４ | ]＋１｝＝４ｋ＋４＞ｍ となり矛盾する。 |
４面体の任意の頂点から内部を監視できることと、各４面体はすべての色の頂点をもつことから、 カメラを設置する頂点を色によりきめることにすれば、
| 題意の防犯カメラは[ | ｍ ４ | ]台あれば十分である。 |
【問題３】
多面体を(n+1)面体に分割する。
ｍ個の各頂点に(n+1)とおりの色から１色をえらんで割り当て、すべての(n+1)面体が(n+1)色の頂点をもつようにすることができる。
| 少なくとも一色の頂点の個数は[ | ｍ n+1 | ]以下である。 |
| なぜならば、もしすべての色の頂点の数が[ | ｍ n+1 | ]より大きいとすると |
| ｍ≧(n+1)｛[ | ｍ n+1 | ]＋１｝＝(n+1)ｋ＋(n+1)＞ｍ |
(n+1)面体の任意の頂点から内部を監視できることと、各(n+1)面体はすべての色の頂点をもつことから、 カメラを設置する頂点を色によりきめることにすれば
| 題意の防犯カメラは[ | ｍ n+1 | ]台あれば十分である。 |
【問題２の例】
４面体
| [ | ４ ４ | ]＝１ 頂点の任意のひとつにカメラを置く。 |
５面体
| [ | ５ ４ | ]＝１ 頂点の任意のひとつにカメラを置く。 |
６面体
| [ | ６ ４ | ]＝１ 凹部頂点の任意のひとつにカメラを置く。 |