ケータイのメニュー画面

質問

私のケータイのメニュー画面には３×３＝９個の中から選択できるようになっています。そして、選択移動するには、「↑」、「↓」、「←」、「→」の４個のボタンを使います。このとき、ボタンを高々２回使えば、あるメニューから別のメニューへ進むことができることを発見しました。

ケータイのメニューの数が９個で、４個のボタンを２回まで使ってできましたが、（４個のボタンを２回までという条件をそのままにして）メニューの数をもっと増やすことを考えました。すると、メニューの数は１２個から１７個程度まで増やせるのでないかと予測できました。ただ、厳密に何個であるかというところまではわかりません。メニューの個数の最大数はいくつになるでしょうか。教えてください。

回答No.3

rabbit_cat

＞「グラフの最大次数が４であり、任意の頂点から任意の頂点への移動が最大で２回で到達可能であるときの、グラフの頂点の最大個数はいくつか」

ムーアグラフのことか。
http://en.wikipedia.org/wiki/Moore_graph
この場合、次数d=4、直径k=2として、頂点の最大数は17ですね。

もし、無向グラフではなくて、
「出次数の最大値が4で、直径が２以下の有向グラフの頂点の最大個数」とすると、もうちょっと増やせる気がしないでもないです。

補足

私の勘違いでなければ、最大個数というのが誤解を生んでいると思います。「最大でも頂点の数は１７個までである、しかし、現実には頂点数が１７個であるグラフが存在するとは限らない」という意味と「現実に１７個の頂点を持つグラフが具体的にある、そして、１８個の頂点を持つグラフは存在し得ない」という意味があると思います。私は英語が得意でないので、参考URLの記事はよく理解できていないのですが、前者の意味であると思いました。私が知りたいのは後者の意味です。具体的なグラフを知りたいのです。

回答No.2

noname#77845

「ボタンを高々２回使えば、あるメニューから別のメニューへ進むことができる」
これは、「左上」のメニューを選択されているときに「右下」に移動するには「↑」・「←」で移動する、ということでしょうか？
そういう条件では、例えば横３×縦４のメニューを考えたとき１段目真ん中から３段目左（又は右）に移動するには３回のキー操作が必要になります。
なので、９個が最大ではないかと…。

補足

「左上」から「右下」へは「↑」一度で行けますよ。「←」一度でも行けます。私の質問の仕方が悪かったせいか、長方形にこだわっているようですけれど、それは無視してください。No.1の方の補足のところで問題を作り変えてみましたので、そちらもご覧になってください。

回答No.1

rabbit_cat

うーん。どういう問題なのかはっきりわかりません。

１．４個のボタンが矢印ボタンで、現在、どのメニューを選択していても、２回ボタン操作すれば、任意のメニューに移れる。
っていこうことなら、最大は９個だと思います。（上端で↑を押すと下端に、左端で←を押すと右端に移るとして。）
↑↓ボタンを操作しても横位置は変化なし、←→ボタンを押しても縦位置に変化なし、なので、横位置・縦位置とも１回のボタン操作で目的の
位置に行ける必要がありますので。

２. 現在のメニュー位置が決まっていて（例えば真ん中）、そこから矢印ボタン２回で移れる、
ってことなら、移動可能な範囲は十字形になって、最大12個だと思います。

３．ボタンは矢印ではなくて、とにかく何でもいいから２回のボタン操作で任意のメニューに移れる
ってことなら、最大のメニュー個数は4^2+1=17個 だと思います。＋１は現在のメニューを、再び選択する必要はないとしたので。

補足

問題を変えます。ケータイのメニュー画面のことはとりあえず忘れてください。

「グラフの最大次数が４であり、任意の頂点から任意の頂点への移動が最大で２回で到達可能であるときの、グラフの頂点の最大個数はいくつか」ということです。

１番目の解釈「４個のボタンが矢印ボタンで...」というのは、ケータイのメニュー画面を

イロハ
ニホヘ
トチリ

とすると、トからハに移動するのにはロを経由して↓→で行けます。ですから、↑↓だけで、左右へ移動できないということはありません。現実にトからロへの移動は↓ですが、右方向への移動があります。

２番目の解釈「現在のメニュー位置が決まっていて...」というのが私の意図しいていた問題に近いと思うのですが、その説明をもう少しお願いします。十字型ということはどういうことでしょうか。興味があります。

３番目の解釈「ボタンは矢印ではなくて...」というのは実は一つの固定したところから任意のところへ移動することと同じではないかと思います。私が最大で１７個程度と言ったのは、その意味からでした。矢印ではないいう想定が私には十分わかっていないかもしれません。矢印でないというのは互いに往復できないという意味と解釈しました。違っていたら教えてください。

しかし、一気にこれだけの想定ができるのはすごいですね。私には到底できないことです。感謝しています。